## 2011年9月30日 星期五

### [C++ 考題] 求出 Binary Tree 的 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);

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!