树的建立、遍历等

待我称王封你为后i 2022-03-07 12:30 129阅读 0赞

#include<iostream> 
    using namespace std;
    typedef struct tree
    {
     char data;
     struct tree *lchild,*rchild;
    }bitree;
     
     void creattree(bitree *&T)
    {  
     char data;
     cin>>data;
     if(data=='#')
      T=NULL;
     else 
     { T=new(bitree);
       T->data=data;
       
       creattree(T->lchild);
       creattree(T->rchild);}
     }
     void preorder(bitree *T)
     {
      if(T)
      { 
          cout<<T->data<<" ";
          preorder(T->lchild);
          preorder(T->rchild);
      }
     } 
    void inorder(bitree *T)
    {if(T){
     inorder(T->lchild);
      cout<<T->data<<" ";
     inorder(T->rchild);}
    } 
    void fallorder(bitree *T)
    {if(T){
     fallorder(T->lchild);
     fallorder(T->rchild);
     cout<<T->data<<" ";}
    }
    int depth(bitree *T)
    {   int ldep,rdep;
     if(T==NULL)
      return 0;
     else 
     {
      ldep=depth(T->lchild);
      rdep=depth(T->rchild);
      return ldep>rdep?ldep+1:rdep+1;
    
     }
    }
    int sumleaf(bitree *T)
    {
     int sum=0,n,m;
     if(T ){
        if((!T->lchild )&&(!T->rchild ))
          sum++;
          n=sumleaf(T->lchild);
          sum+=n;
          m=sumleaf(T->rchild);
          sum+=m;
     }
     return sum;
    
    }
    int main()
    {
     bitree *T=NULL;
     creattree(T);
     cout<<"pre:";
     preorder(T);
     cout<<endl;
     cout<<"in :";
     inorder(T);
     cout<<endl;
     cout<<"fal:";
     fallorder(T);
     cout<<endl;
     cout<<"the depth:" ;
     cout<<depth(T);
     cout<<endl;
     cout<<sumleaf(T);
     return 0;
    }

c语言版

#include "stdio.h"
    #include "string.h"
    #define NULL 0
    typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    BiTree Create(BiTree T){
    char ch;
    ch=getchar();
    if(ch=='#')
    T=NULL;
    else{
    if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
    printf("Error!");
    T->data=ch;
    T->lchild=Create(T->lchild);
    T->rchild=Create(T->rchild);
    }
    return T;
    }
    void Preorder(BiTree T){
    if(T){
    printf("%c",T->data);
    Preorder(T->lchild);
    Preorder(T->rchild);
    }
    }
    int Sumleaf(BiTree T){
    int sum=0,m,n;
    if(T){
    if((!T->lchild)&&(!T->rchild))
    sum++;
    m=Sumleaf(T->lchild);
    sum+=m;
    n=Sumleaf(T->rchild);
    sum+=n;
    }
    return sum;
    }
    void zhongxu(BiTree T){
    if(T){
    zhongxu(T->lchild);
    printf("%c",T->data);
    zhongxu(T->rchild);
    }
    }
    void houxu(BiTree T){
    if(T){
    houxu(T->lchild);
    houxu(T->rchild);
    printf("%c",T->data);
    }
    }
    int Depth(BiTree T){
    int dep=0,depl,depr;
    if(!T) dep=0;
    else{
    depl=Depth(T->lchild);
    depr=Depth(T->rchild);
    dep=1+(depl>depr?depl:depr);
    }
    return dep;
    }
    main(){
    BiTree T;
    int sum,dep;
    T=Create(T);
    Preorder(T);
    printf("\n");
    zhongxu(T);
    printf("\n");
    houxu(T);
    printf("\n");
    sum=Sumleaf(T);
    printf("%d",sum);
    dep=Depth(T);
    printf("\n%d",dep);
    }
    在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列ABC##DE#G##F###（其中的“#”表示空，并且输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，但是输入完之后可以按回车退出），然后再按ALT+F5显示用户界面，这时候就能够看到结果了。
    另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入，按最后按多少回车程序也不会结束！