樹的深度是指樹中最大的結點層。
要計算二叉樹的深度， 最直觀的方法就是找出二叉樹中最底層葉子結點的嘗試， 因此可以通過深度優先遍歷二叉樹的每一個結點， 用變數n記錄每一個結點的的深度， 然後再用/用變數level記錄下二叉樹的最深結點的深度。
代碼：
運行效果：
附原代碼：
#include "stdio.h"
#include "malloc.h"
typedef struct BiTNode{
char data; /*結點的資料欄*/
struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/
} BiTNode , *BiTree;
/*創建一棵二叉樹*/
void CreatBiTree(BiTree *T)
{
char c;
scanf("%c",&c);
if(c == ' ') *T = NULL;
else{
*T = (BiTNode * )malloc(sizeof(BiTNode)); /*創建根結點*/
(*T)->data = c; /*向根結點中輸入資料*/
CreatBiTree(&((*T)->lchild)); /*遞迴地創建左子樹*/
CreatBiTree(&((*T)->rchild)); /*遞迴地創建右子樹*/
}
}
/*計算二叉樹的深度*/
//遞迴遍歷二叉樹， 用變數n記錄每一個結點的深度
//用變數level記錄下二叉樹的最深結點的深度
void getDepth(BiTree T,int n,int *level) //用指標帶出一個值
{
if(T!=NULL)
{
if(n> *level)
{
*level = n;
}
getDepth(T->lchild,n+1,level);
getDepth(T->rchild,n+1,level);
}
}
int getBitreeDepth(BiTree T)
{
int level = 0;
int n = 1;
getDepth(T,n,&level);
return level;
}
int getBitreeDepth2(BiTree T)
{
int leftHeight,rightHeiht,maxHeight;
if(T !=NULL)
{
leftHeight = getBitreeDepth2(T->lchild);
rightHeiht = getBitreeDepth2(T->rchild);
maxHeight = leftHeight > rightHeiht ? leftHeight:rightHeiht;
return maxHeight+1;
} else {
return 0;
}
}
main()
{
BiTree T = NULL; /*最開始T指向空*/
printf("如可以創建和遍歷如下的二叉樹： ");
printf(" A ");
printf(" / ");
printf(" B F ");
printf(" / ");
printf(" C D G ");
printf(" ");
printf(" E ");
printf("Input some characters to create a binary tree ");
printf("（按先序序列建立） ");
printf("例如， ABC##D#E##F#G##↙， #表示空格(空子樹),↙表示回車 ");
CreatBiTree(&T); /*創建二叉樹*/
printf(" The depth of the binary tree is %d ",getBitreeDepth(T));
printf(" The depth of the binary tree is(2nd method) %d ",getBitreeDepth2(T));
getchar() ;
getchar() ;
}
-END-