二叉树

#include<stdio.h> //‘ ‘空格代表树的元素为空
#include<stdlib.h>
#define OVERFLOW -1
typedef char TElemType;
typedef struct BitNode
{
    TElemType data;
    struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
typedef struct QNode
{
    BitNode data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
void BinTreeInit(BitNode **BT)  //初始化二叉树
{
    *BT=NULL;
}
BitNode *BinTreeCreat(BitNode *BT) //按先序次序构造二叉树
{
    char c;
    scanf("%c",&c);
    if(c==‘ ‘)BT=NULL;
    else
    {
        if(!(BT=(BitTree)malloc(sizeof(BitNode))))
            exit(OVERFLOW);
        BT->data=http://www.mamicode.com/c;"%c",BT->data);    
}
void PreOrderTraverse(BitNode *BT)//先序遍历树
{
    if(BT)
    {
    visit(BT);
    PreOrderTraverse(BT->lchild);
    PreOrderTraverse(BT->rchild);
    }
}
void InOrderTraverse(BitNode *BT)//中序遍历树
{
    if(BT)
    {
    InOrderTraverse(BT->lchild);
    visit(BT);
    InOrderTraverse(BT->rchild);
    }
}
void PostOrderTraverse(BitNode *BT)//后序遍历树
{    
    if(BT)
    {
    PostOrderTraverse(BT->lchild);
    PostOrderTraverse(BT->rchild);
    visit(BT);
    }
}
void InitQueue(LinkQueue *Q) //构造一个空的队列
{
    Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
    if(!Q->front)exit(OVERFLOW);
    Q->front->next=NULL;
}
int QueueEmpty(LinkQueue *Q)
{
    if(Q->rear==Q->front)return 1;
    else return 0;
}
void EnQueue(LinkQueue *Q,BitNode e) //入队
{
    QNode *p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)exit(OVERFLOW);
    p->data=http://www.mamicode.com/e;"执行创建树操作后: ");
    if(BinTreeEmpty(BT))printf("树空\n");//判空
    else printf("树不空\n");
    printf("先序遍历二叉树: ");
    PreOrderTraverse(BT);printf("\n");
    printf("中序遍历二叉树: ");
    InOrderTraverse(BT);printf("\n");
    printf("后序遍历二叉树: ");
    PostOrderTraverse(BT);printf("\n");
    printf("层次遍历二叉树: ");
    BFSTraverse(BT);printf("\n");
    printf("二叉树的深度为:%d\n",BinTreeDepth(BT));//求二叉树的深度
    BinCountleaf(BT,&count);//求二叉树中的节点个数
    printf("二叉树的叶子节点个数为:%d\n",count);
    BinTreeClear(&BT);//清空树
    printf("执行清空树操作后: ");
    if(BinTreeEmpty(BT)==1)printf("树空\n");//判空
    else printf("树不空\n");

    return 0;
}　　　　　　　　　　


 或者将构造二叉树的操作改为，main函数里对此函数的调用扫做修改即可：

void BinTreeCreat(BitNode **BT) //按先序次序构造二叉树
{
	char c;
	scanf("%c",&c);
	if(c==‘ ‘)*BT=NULL;//此处曾把‘*‘漏掉
	else
	{
		if(!((*BT)=(BitTree)malloc(sizeof(BitNode))))
			exit(OVERFLOW);
		(*BT)->data=http://www.mamicode.com/c;"%c",(*BT)->data);
		BinTreeCreat(&(*BT)->lchild); 
		BinTreeCreat(&(*BT)->rchild);
	}
}

#include "string.h"  
#include "stdio.h"      
#include "stdlib.h"     
#include "io.h"    
#include "math.h"    
#include "time.h"  
  
#define OK 1  
#define ERROR 0  
#define TRUE 1  
#define FALSE 0  
#define MAXSIZE 100                             /* 存储空间初始分配量 */  
  
typedef int Status;                             /* Status是函数的类型,其值是函数结果状态代码，如OK等 */  
  
/**********定义二叉树的存储结构************/  
typedef char TElemType;  
TElemType Nil=‘ ‘;                              /* 字符型以空格符为空 */  
  
typedef struct BinTreeNode                      /* 结点结构 */  
{  
    TElemType data;                             /* 结点数据 */  
    struct BinTreeNode *lchild,*rchild;         /* 左右孩子指针 */  
}BinTreeNode,*BinTree;  
/*****************************************/  
  
/***********用于构造二叉树************** */  
int index=1; 
//自定义了一个字符数组类型 
typedef char charArray[24];                     /*声明一个char类型数组,charArray是数组名也是一个指针*/  
charArray str;									//str字符数组类型的数组名，charArray等价于char *  
  
Status AssignStr(charArray T,char *chars)		//char *chars是字符类型的指针变量
{   
    int i;  
    if(strlen(chars)>MAXSIZE) return ERROR;     /*输入字符的长度超过存储空间最大值*/  
    else  
    {  
        T[0]=strlen(chars);                     /*0号单元存放字符串长度*/  
        for(i=1;i<=T[0];i++)  
        {  
            T[i]=*(chars+i-1);					//先将数据进行存储               
        }   
        return OK;
    }  
}  
/* ************************************* */  
  
/*构造二叉树*/  
void CreateBinTree(BinTree *T)  
{   
    TElemType ch;  
    ch=str[index++];  

    if(ch==‘#‘)   
        *T=NULL;  
    else  
    {  
        *T=(BinTree)malloc(sizeof(BinTreeNode));  
        if(!*T)  
            exit(OVERFLOW);  
        (*T)->data=http://www.mamicode.com/ch;                            /* 生成根结点 */  "%c ",T->data);                           /* 显示结点数据，可以更改为其它对结点操作 */  
    PreOrderTraverse(T->lchild);                     /* 再先序遍历左子树 */  
    PreOrderTraverse(T->rchild);                     /* 最后先序遍历右子树 */  
}  
  
/*中序遍历 
思路：中序遍历左子树--->访问根节点--->中序遍历右子树 
*/  
void InOrderTraverse(BinTree T)  
{   
    if(T==NULL) return;  
  
    InOrderTraverse(T->lchild);                       /* 中序遍历左子树 */  
    printf("%c ",T->data);                            /* 显示结点数据，可以更改为其它对结点操作 */  
    InOrderTraverse(T->rchild);                       /* 最后中序遍历右子树 */  
}  
  
/*后序遍历 
思路：后序遍历左子树--->后序遍历右子树--->访问根节点 
*/  
void PostOrderTraverse(BinTree T)  
{  
    if(T==NULL) return;  
  
    PostOrderTraverse(T->lchild);                      /* 先后序遍历左子树  */  
    PostOrderTraverse(T->rchild);                      /* 再后序遍历右子树  */  
    printf("%c ",T->data);                             /* 显示结点数据，可以更改为其它对结点操作 */  
}  
  
  
int main()  
{  
    int i;  
    BinTree T;  
    TElemType e1;  
  
    /*初始化二叉树为一棵空树*/  
    InitBinTree(&T);  
  
    /*设置字符数组用于构造二叉树*/  
    AssignStr(str,"ABDH#K###E##CFI###G#J##"); 
	
    /*创建二叉树*/  
    CreateBinTree(&T);  
    printf("创建二叉树后,树空否？%d(1:是 0:否) 树的深度为：%d\n",IsBinTreeEmpty(T),GetDepth(T));  
  
    /*获取二叉树的根节点*/  
    e1=GetRoot(T);  
    printf("\n二叉树的根为: %c\n",e1);  
  
    /*前序遍历*/  
    printf("\n前序遍历二叉树:");  
    PreOrderTraverse(T);  
  
    /*中序遍历*/  
    printf("\n中序遍历二叉树:");  
    InOrderTraverse(T);  
  
    /*后序遍历*/  
    printf("\n后序遍历二叉树:");  
    PostOrderTraverse(T);  
  
    /*清空二叉树*/  
    ClearBinTree(&T);  
    printf("\n\n清除二叉树后,树空否？%d(1:是 0:否) 树的深度为：%d\n",IsBinTreeEmpty(T),GetDepth(T));  
    i=GetRoot(T);  
    if(!i) printf("树空，无根\n");  
  
    getchar();  
}