数据结构实验之二叉树的建立与遍历

偏执的太偏执、 2022-08-10 06:11 169阅读 0赞

## 数据结构实验之二叉树的建立与遍历 ##

##### Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。

## 输入 ##

输入一个长度小于50个字符的字符串。

## 输出 ##

输出共有4行：  
第1行输出中序遍历序列；  
第2行输出后序遍历序列；  
第3行输出叶子节点个数；  
第4行输出二叉树深度。

## 示例输入 ##

abc,,de,g,,f,,,

## 示例输出 ##

cbegdfacgefdba
    3
    5

## 提示 ##

## 来源 ##

ma6174

## 示例程序 ##

#include<stdio.h>  
    #include<string.h>  
    #include<stdlib.h>  
    int l=0;  
    struct node  
    {  
    int data;  
    struct node *lchild,*rchild;  
    };  
    struct node *creat(struct node *root,int k)  
    {  
    char c;  
    struct node *p;  
    p=(struct node *)malloc(sizeof(struct node));  
    c=getchar();  
    if(c!=',')  
    {  
    p->lchild=NULL;  
    p->rchild=NULL;  
    p->data=c;  
    if(k==0)  
    root=p;  
    if(k==1)  
    root->lchild=p;  
    if(k==2)  
    root->rchild=p;  
    creat(p,1);  
    creat(p,2);  
    }  
    return root;  
    }  
    void houxu(struct node *root)  
    {  
    if(root!=NULL)  
    {  
    houxu(root->lchild);  
    houxu(root->rchild);  
    printf("%c",root->data);  
    }  
    }  
    void zhongxu(struct node *root)  
    {  
    if(root!=NULL)  
    {  
    zhongxu(root->lchild);  
    printf("%c",root->data);  
    zhongxu(root->rchild);  
    }  
    }  
    int leave(struct node *root)  
    {  
    if(root==NULL)  
    return 0;  
    if(root->lchild==NULL&&root->rchild==NULL)  
    return 1;  
    else  
    return leave(root->rchild)+leave(root->lchild);  
    }  
    int deep(struct node *root)  
    {  
    int d=0;  
    if(root!=NULL)  
    {  
    int d1=deep(root->lchild);  
    int d2=deep(root->rchild);  
    d=d1>d2?d1+1:d2+1;  
    }  
    return d;  
    }  
    int main()  
    {  
    int i,j,n,m,k,t;  
    struct node *root;  
    root=(struct node *)malloc(sizeof(struct node));  
    root=creat(root,0);  
    zhongxu(root);  
    printf("\n");  
    houxu(root);  
    printf("\n");  
    printf("%d\n",leave(root));  
    printf("%d\n",deep(root));  
    }