二叉树的创建，遍历输出，求二叉树叶子节点，求二叉树深度

二叉树相关操作

关键点：利用递归操作
1.二叉树的创建
2.遍历算法（先序输出，中序输出，后序输出）
3.求二叉树的高度
4.求二叉树的叶子节点的个数

二叉树的创建

//二叉树的创建
typedef struct BiTnode
{
    char data;
    struct BiTnode *lchild,*rchild;
}BiNode,*Bitree;

输入先序遍历序列：
利用先序遍历输出序列建立二叉树
例如：
输入先序遍历序列：[email protected]@@@[email protected]@@

BiNode* creatBitree()
{
    Bitree T;
    char ch；scanf("%c",&ch);
    if(ch=='@') T=NULL;
    else{
        T=(BiNode*)malloc(sizeof(BiNode));
        T->data=ch;
        T->lchild=creatBitree();
        T->rchild=creatBitree();
    }
    return T;
}

二叉树的输出

先序遍历序列输出：
void output(Bitree T)
{
    if(T)
    {
        printf("%c",T->data);
        output(T->lchild);
        output(T->rchild);
        
    }
}
中序遍历序列输出
void output(Bitree T)
{
    if(T)
    {
        output(T->lchild);
        printf("%c",T->data);
        output(T->rchild);
        
    }
}
后序遍历序列输出
 void output(Bitree T)
 {
   if(T)
   {
    output(T->lchild);
    output(T->rchild);
    printf("%c",T->data);
   }
 }

求二叉树的深度

int Depth(Bitree T)
{
    int depl,depr;
    if(T==NULL) return 0;
    else {
        depl=Depth(T->lchild);
        depr=Depth(T->rchild);
        if(depl>=depr) return(depl+1);
        else return(depr+1);
    }
}

求二叉树叶子节点的个数

int LeafCount(Bitree T)
{
    if(!T) return 0;
    else
        if(T->lchild==NULL&&T->rchild==NULL) return 1;
        else return LeafCount(T->lchild)+LeafCount(T->rchild);
}

全代码

#include <bits/stdc++.h>
using namespace std;
typedef struct BiTnode
{
    char data;
    struct BiTnode *lchild,*rchild;
}BiNode,*Bitree;
BiNode* creatBitree()
{
    Bitree T;
    char ch;
    scanf("%c",&ch);
    if(ch=='@') T=NULL;
    else{
        T=(BiNode*)malloc(sizeof(BiNode));
        T->data=ch;
        T->lchild=creatBitree();
        T->rchild=creatBitree();
    }
    return T;
}
int Depth(Bitree T)
{
    int depl,depr;
    if(T==NULL) return 0;
    else {
        depl=Depth(T->lchild);
        depr=Depth(T->rchild);
        if(depl>=depr) return(depl+1);
        else return(depr+1);
    }
}
void output(Bitree T)
{
    if(T)
    {
        output(T->lchild);
        output(T->rchild);
        printf("%c",T->data);
    }
}
int LeafCount(Bitree T)
{
    if(!T) return 0;
    else
        if(T->lchild==NULL&&T->rchild==NULL) return 1;
        else return LeafCount(T->lchild)+LeafCount(T->rchild);
}
void output1(Bitree T)
{
    
}
int main()
{
    Bitree T;
    int depth,sum;
    T=creatBitree();
    depth=Depth(T);
    printf("%d\n",depth);
    //遍历二叉树求树的高度
    output(T);
    //遍历输出二叉树

     sum=LeafCount(T);
    printf("%d\n",sum);
    //求二叉树的叶子节点个数
      return 0;
}