程式扎記: [C++ 考題] 求出 Binary Tree 的 depth

標籤

2011年9月30日 星期五

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

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

  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 代碼 :
  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 代碼 :
  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. }  
* 執行範例代碼 :
  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


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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!