[C++ 考題] 求出 Binary Tree 的 depth

題目 :
請依照下面 Binary tree 的 Structure, 寫出函式API 傳入該 Binary tree 的資料結構後返回該 Binary tree 的 deepest depth.
* Binary Tree 資料結構 : 

view plaincopy to clipboardprint?

1. typedef struct BiTNode{  
2.     int data;  
3.     struct BiTNode *lchild, *rchild;  
4. }  

解題 :

1. 首先為測試目的, 撰寫函數 BiTNode* createBiTree() 建立測試用的 Binary tree.
2. 依據提議撰寫函數 int fetchDepthInBiTree(BiTree tree) 求出傳入 Binary tree 的 deepest depth.
3. 再求 Binary tree 的函數裡利用了 recursive 的方法分別求 binary tree 的 left tree 與 right tree 的 depth, 再回傳較大的值回去.

範例代碼 :
* BitTree.h 代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. typedef struct BiTNode{  
5.     int data;  
6.     struct BiTNode *lchild, *rchild;  
7. }BiTNode, *BiTree;  
8.   
9. BiTNode* createBiTree();  
10.   
11. int fetchDepthInBiTree(BiTree tree);  

* BitTree.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "BitTree.h"  
2.   
3. BiTNode* createBiTree() {  
4.     BiTree node;  
5.     printf("Please key in int to create BinaryTree (0 to exit): ");  
6.     int tmp = 0;  
7.     scanf("%d", &tmp);  
8.     //printf("tmp = %d\n",tmp);  
9.     if(tmp > 0) {  
10.         node = new BiTNode;  
11.         node->data = tmp;  
12.         printf("\tFor left node...");  
13.         node->lchild = createBiTree();  
14.         printf("\tFor right node...");  
15.         node->rchild = createBiTree();  
16.         return node;  
17.     } else {  
18.         return NULL;  
19.     }     
20. }  
21.   
22. int fetchDepthInBiTree(BiTree tree){  
23.     if(tree == NULL)  
24.         return 0;  
25.     int r = 1+ fetchDepthInBiTree(tree->rchild);  
26.     int l = 1+ fetchDepthInBiTree(tree->lchild);  
27.     if(r>l) {  
28.         return r;  
29.     } else {  
30.         return l;  
31.     }     
32. }  

* 執行範例代碼 :

view plaincopy to clipboardprint?

1. BiTree biTree = createBiTree();  
2. int depth = fetchDepthInBiTree(biTree);  
3. printf("Depth of Binary Tree= %d\n", depth);  

執行結果 :
首先建立 Binary tree 如下 :

執行過程 :

Please key in int to create BinaryTree (0 to exit): 1
For left node...Please key in int to create BinaryTree (0 to exit): 2
For left node...Please key in int to create BinaryTree (0 to exit): 3
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 4
For left node...Please key in int to create BinaryTree (0 to exit): 6
For left node...Please key in int to create BinaryTree (0 to exit): 5
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 7
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 8
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 9
For left node...Please key in int to create BinaryTree (0 to exit): 10
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 11
For left node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
For right node...Please key in int to create BinaryTree (0 to exit): 0
Depth of Binary Tree= 6

補充說明 :
* [ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的儲存方式