二叉树

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -1 

typedef int Status;
typedef char TElemType;

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;




Status CreateBiTree(BiTree &T){
    char ch;
    scanf("%c",&ch);        //这是个坑，记住这个scanf会接收字符，包括回车，所以创建树的时候字符要连着输，不要按回车，否则第二次输入字符的时候scanf会接收上一次输入结束时按的回车

    if (ch =='#')
    T = NULL;
    else{
    if (!(    T = (BiTNode *)malloc(    sizeof(BiTNode)    )     )    ){
        exit(OVERFLOW);
    }
    T->data = ch;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
    }
    return OK;
}


Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e)){
    if (T){
    Visit(T->data);
    PreOrderTraverse(T->lchild, Visit);
    PreOrderTraverse(T->rchild, Visit);
    }
    return OK;
}

Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
    if (T){
    InOrderTraverse(T->lchild, Visit);
    Visit(T->data);
    InOrderTraverse(T->rchild, Visit);
    }
    return OK;
}

Status PostOrderTraverse  (BiTree T, Status (* Visit)(TElemType e)){
    if (T){
    PostOrderTraverse(T->lchild, Visit);
    PostOrderTraverse(T->rchild, Visit);
    Visit(T->data);
    }
    return OK;
}

Status Visit(TElemType e){
    printf("%c  ", e);
    return OK;
}




int BiTreeDepth(BiTree T){     //返回二叉树的深度
    int i,j;
    if(!T)
        return 0;
        
    if(T->lchild)
        i=BiTreeDepth(T->lchild);
    else
        i=0;
        
        
    if(T->rchild)
        j=BiTreeDepth(T->rchild);
    else
        j=0;
        
        
    return i>j?++i:++j;
}
int Leaf(BiTree T){           // 求二叉树叶子结点数目
    int n,m;
    if (T==NULL)
        return 0;
    else if ((T->lchild == NULL) && (T->rchild == NULL))
        return 1;         // 如果二叉树的左孩子和右孩子均为空，则返回 1
    else{            // 如果二叉树的左孩子或右孩子不为空
        n = Leaf (T->lchild);         // 求 T 的左子树的叶子结点数目
        m = Leaf (T->rchild);         // 求 T 的右子树的叶子结点数目
        return n+m;              // 返回总的叶子结点数目
    }
}






int main(){
    BiTree T;
    printf("请手动创建二叉树\n\t");       //ABM##CD###E#FGH##K###
    CreateBiTree(T);    //注意创建的时候 每个叶子结点都没有子树  所以都需要输入#
    printf("\n二叉树创建成功！\n");
    
    printf("\n\n\n二叉树深度\n");
    
    printf("%d\n",BiTreeDepth(T));

    printf("\n\n\n叶子结点个数\n");
    printf("%d\n",Leaf(T));
    
    
    
//PreOrder
    printf("\n\n\n先序遍历\n");
    PreOrderTraverse(T, Visit);
//InOrder
    printf("\n\n\n中序遍历\n");
    InOrderTraverse(T, Visit);
//PostOrder
    printf("\n\n\n后序遍历\n");
    PostOrderTraverse(T, Visit);
    

    printf("\n\n\n\n");
    system("pause");
    return 0;
}