二叉の木は深さと葉数(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;
}