二叉树结构、遍历和释放-自己写数据结构

二叉树构造、遍历和释放--自己写数据结构

    直接上代码

bitree.h文件如下：

#ifndef _BITREE_H_
#define _BITREE_H_

typedef  char TElemType;

typedef struct _BitNode
{
    TElemType data;
    struct _BitNode *lchild,*rchild;                
}BitNode,*pBitNode;

int bittree_creat(BitNode **T);
void pre_order(BitNode *T);
void mid_order(BitNode *T);
void post_order(BitNode *T); 
#endif

bittree.c文件如下

/***************************
时间：2014.12.16
作者：XIAO_PING_PING
编译环境：DEV-C++ 4.9.9.2 
内容：二叉树构造、遍历和释放 
功能： 学习写数据结构 

****************************/
/********************************
（1）scanf("%c",&ch);和 scanf("%d",&ch);
的区别在于前者是一次性输入，后者需要输入数字后回车才能返回 
（2）C语言指针作为函数的参数时，函数不能改变指针的值，
只能改变指针指向内容的值(只能用二级指针)，C++可以通过*(&p)引用达到在函数内部
改变参数指针的值 
（3）故也不可能实现将指针（包括结构体指针）作为函数参数，对其在
函数内部非配空间的任务(但是可以完成free操作)，另外一种解决的办法是在函数内部初始化一个
指针后分配空间，然后用返回值的形式传递给外部指针 
*********************************/
#include <string.h>
#include <stdio.h>

#include "bitree.h" 

/*创建二叉树*/
int bittree_creat(BitNode **T)//C语言函数内部不能改变作为参数的指针 
{
     char ch;
     scanf("%c",&ch);
     
     //*T = *(T)->lchild ;
     if('0' == ch)
     {
         *T = NULL;
         return 0;  
     }

     *T = (BitNode *)malloc(sizeof(BitNode)); 
     if(NULL == *T)
     {
         return -1;        
     }
     (*T)->data = ch;
     
     bittree_creat(&((*T)->lchild));   
     bittree_creat(&((*T)->rchild));       
     
     return 1;
} 
/*前序遍历二叉树*/
void pre_order(BitNode *T)
{
    if(NULL == T)
    {
        return;
    }
    
    printf("%c ",T->data); 
    pre_order(T->lchild);  
    pre_order(T->rchild);              
}
/*中序遍历二叉树*/
void mid_order(BitNode *T)
{
    if(NULL == T)
    {
        return;
    }
       
    mid_order(T->lchild);  
    printf("%c ",T->data); 
    mid_order(T->rchild);     
}
/*后序遍历二叉树*/
void post_order(BitNode *T)
{
    if(NULL == T)
    {
        return;
    }
    
    post_order(T->lchild);  
    post_order(T->rchild);     
    printf("%c ",T->data); 
}

/*释放二叉树*/ 
int free_btree(BitNode *T)
{
    if(NULL == T)
    {
        return 0;        
    }      
    
    free_btree(T->lchild);
    free_btree(T->rchild);
    free(T); 
    
    return 1;
} 

测试文件test.c如下：

/************************
*************************/ 
#include <string.h>
#include <stdio.h>
#include <conio.h>

#include "bitree.h"

int main()
{
    pBitNode btree;
    printf("Create binary tree:n");
    bittree_creat(&btree);
    
    printf("n前序：");
    pre_order(btree);
    printf("n中序：");
    mid_order(btree);
    printf("n后序：");
    post_order(btree);
    
    printf("n销毁二叉树");
    free_btree(btree); 
    
    getch();
    return 0;       
}

运行结果如下：