首页 > 代码库 > 二叉树的建立

二叉树的建立

#include "stdio.h"
#include "string.h"
#include "BiTNode.h"




 //先序建立二叉树
BiTree ProCreate(BiTree T)
{
   char ch;
   scanf("%c", &ch);
   if(ch == ‘#‘)
   {
        T = NULL;
        return NULL;
   }


   else
   {
       T = (BiTNode *)malloc(sizeof(BiTNode));
       if(!T)
       {
            printf("Error!");
            return NULL;
       }


       T->data = http://www.mamicode.com/ch;
       T->lchild = ProCreate(T->lchild);
       T->rchild = ProCreate(T->rchild);
   }
   return T;
}
//先序遍历二叉树
void Preorder(BiTree T)
{
  if(T)
  {
       printf("%c", T->data);
       Preorder(T->lchild);
       Preorder(T->rchild);
  }
}


//中序遍历二叉树
void Inorder(BiTree T)
{
   if(T)
   {
       Inorder(T->lchild);
       printf("%c",T->data);
       Inorder(T->rchild);
   }
}
 //后序遍历二叉树
void Postorder(BiTree T)
{
    if(T)
    {
        Postorder(T->lchild);
        Postorder(T->rchild);
        printf("%c",T->data);
    }
}
 //求叶子节点的个数
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;
}
//求二叉树的深度
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;
}


int main()
{
    BiTree T;
    int sum, dep;
    printf("先序创建二叉树,请输入序列,空使用#代替 \n");
    T = ProCreate(T);
    printf("先序遍历的结果: ");
    Preorder(T);
    printf("\n中序遍历的结果: ");
    Inorder(T);
    printf("\n后序遍历的结果: ");
    Postorder(T);
    printf("\n叶子个数: ");
    sum=Sumleaf(T);
    printf("%d",sum);
    dep=Depth(T);
    printf("\n深度为:%d \n",dep);
    return 0;

}


BiTNode.h的内容

#ifndef BITNODE_H_INCLUDED
#define BITNODE_H_INCLUDED
#define ElemType char


 //定义数据结构
typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;






#endif // BITNODE_H_INCLUDED

二叉树的建立