二叉の木は深さと葉数(20分)を求めます.

1926 ワード

編纂関数は、二叉樹の深さと葉っぱノード数を計算する.二叉樹は二叉リンクテーブル記憶構造を採用しています.
関数インターフェースの定義:
int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);
Tは、ユーザが着信したパラメータであり、二叉のツリー・ルート・ノードのアドレスを示す.関数は、二叉樹の深さ(高さとも呼ばれる)を返します.
審判試験手順の例:

//     
#include
#include
#include

//       
#define TRUE       1
#define FALSE      0
#define OK         1
#define ERROR      0
#define OVERFLOW   -1
#define INFEASIBLE -2
#define NULL  0
typedef int Status;

//          
typedef int TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

//          
Status CreateBiTree(BiTree &T){
   TElemType e;
   scanf("%d",&e);
   if(e==0)T=NULL;
   else{
     T=(BiTree)malloc(sizeof(BiTNode));
     if(!T)exit(OVERFLOW);
     T->data=e;
     CreateBiTree(T->lchild);
     CreateBiTree(T->rchild);
   }
   return OK;  
}

//             
int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);
//      
int main()
{
   BiTree T;
   int depth, numberOfLeaves;
   CreateBiTree(T);
   depth= GetDepthOfBiTree(T);
	 numberOfLeaves=LeafCount(T);
   printf("%d %d
",depth,numberOfLeaves); } /* */
入力サンプル:
1 3 0 0 5 7 0 0 0
出力例:
3 2
int GetDepthOfBiTree(BiTree T)
{
    int d1 = 0, d2 = 0, d;
    if(!T)
        return 0;
    else
    {
       d1 = GetDepthOfBiTree(T->lchild) + 1;
       d2 = GetDepthOfBiTree(T->rchild) + 1;
    }
    d = d1 > d2 ? d1 : d2;
    return d;
}
int LeafCount(BiTree T)
{
    int n = 0;
    if(!T)
        return 0;
    else
    {
        if(T->lchild == NULL && T->rchild == NULL)
           n++;
        else
        {
            n = LeafCount(T->lchild) + LeafCount(T->lchild);
        }
    }
    return n;
}