欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-16 11:26:25
...

二叉树相关操作

关键点:利用递归操作
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;
}