首页 > 代码库 > 二叉树的基础应用(建树+叶子数+深度+遍历 )

二叉树的基础应用(建树+叶子数+深度+遍历 )

#include <stdio.h>#include <string.h>#include <string>#include <iostream>#include <algorithm>using namespace std;typedef struct node{    char ch;    struct node *ll;    struct node *rr;}Binode, *Bitree;struct node *Creat_Bitree(struct node *root, char *s1, char *s2, int n){    if(n<=0)      return NULL;    else    {        root=new Binode;        root->ch=s1[0];        int p = strchr(s2, s1[0])- s2;  //在s2中查找s1[0]元素        root->ll= Creat_Bitree(root->ll, s1+1, s2, p);        root->rr= Creat_Bitree(root->rr, s1+1+p, s2+1+p, n-1-p );    }    return root;}void Post_order(Bitree p)//后序遍历{    if(p)    {        Post_order(p->ll);        Post_order(p->rr);        printf("%c", p->ch);    }}void In_order(Bitree p)//中序遍历{    if(p)    {        Post_order(p->ll);        printf("%c", p->ch);        Post_order(p->rr);    }}void Pre_order(Bitree p)//先序遍历{    if(p)    {        printf("%c", p->ch);        Post_order(p->ll);        Post_order(p->rr);    }}int Deep_Bitree(Bitree p)//求二叉树的深度{    int deep1, deep2;    if(p==NULL)      return 0;    else    {        deep1=Deep_Bitree(p->ll);        deep2=Deep_Bitree(p->rr);        if(deep1 > deep2)            return (deep1+1);        else            return (deep2+1);    }}void Leaf_num(Bitree p, int *cnt) //计算叶子节点的个数{    if(p==NULL)      return ;    else    {        Leaf_num(p->ll, cnt );        if(p->ll==NULL && p->rr==NULL )        {            (*cnt)++;        }        Leaf_num(p->rr, cnt );    }}int main(){    char s1[200];    char s2[200];    scanf("%s", s1);    scanf("%s", s2);    int len =strlen(s1);    Bitree root;    Bitree p;    root = Creat_Bitree(p, s1, s2, len );//root是已经建好二叉树的根节点    p=root;    Post_order(p); //从根点开始进行后序遍历    printf("\n");    p=root;    int deep=Deep_Bitree(p);    printf("%d\n", deep );    int a=0;    int *sum;    sum=&a;    p=root;    Leaf_num(p, sum);    printf("%d\n", *sum);    return 0;}

 

二叉树的基础应用(建树+叶子数+深度+遍历 )