問題的提出
??? 經常會遇到關于二叉樹的算法問題，雖然比較簡單，不過我覺得還是有必要總結一下．順便寫了個sample程序，以供參考．本文中主要討論關于二叉樹的以下3個問題,都是用遞歸來實現，Divide and conquer也就是所謂的分冶策略．
??? 1.二叉樹的高度
??? 2.二叉樹的寬度
??? 3.比較兩個二叉樹是否相等
此文對應的參考程序可以在 http://shaohui.zheng.googlepages.com/bst.c 下載。
數據結構的定義
??? 先定義一個簡單的二叉樹，由于只是演示，所以定義得比較簡單．
?1
#include
<stdio.h>
?2
?3
#define MAX(x,y) ((x)>(y)?(x):(y))
?4
?5
//define a binary search tree
?6
typedef
struct
BNode
?7 {
?8 ??? int val;
?9 ??? struct BNode *left, *right;
10 }BNode,*BTree;
二叉樹節點的值為val,另外為了比較方便還定義了一個宏MAX.
12
// insert a node to binary tree
13
// we assume that no duplicated elements
14
void
BTreeInsert(BTree *bt, int val)
15 {
16 ??? BNode *p = *bt,*cur = *bt;//p is a parent node of cur
17 ??? while (cur != NULL)
18 ??? {//find the position to insert node val
19 ??????? p = cur;
20 ??????? if ( val < cur->val )
21 ??????????? cur = cur->left;
22 ??????? else
23 ??????????? cur = cur->right;
24 ??? }
25 ??? BNode *n = malloc(sizeof(BNode));
26 ??? n->val = val;
27 ??? n->left = n->right = NULL;
28 ??? if (p == NULL)
29 ??????? *bt = n;// the tree is empty
30 ??? else
31 ??? {
32 ??????? if (val < p->val)
33 ??????????? p->left = n;
34 ??????? else
35 ??????????? p->right = n;
36 ??? }
37 }
//BTreeInsert
還定義了一個函數BTreeInsert用來幫助創建二叉樹．
二叉樹的高度
基本方法：二叉樹，分別求出左右子數的高度，然后取左右子樹高度的最大數值，再加上１，就是二叉樹的高度．
由于該問題又被劃分為兩個性質一樣的子問題，因此很容易導致遞歸．
39
//get the depth of a BST
40
int
BTreeDepth(BTree bt)
41 {
42 ??? if (bt != NULL)
43 ??? {
44 ??????? int dep_left = BTreeDepth(bt->left);
45 ??????? int dep_right = BTreeDepth(bt->right);
46 ??????? return MAX(dep_left,dep_right)+1;
47 ??? }
48 ??? return0;
49 }
//BTreeDepth
二叉樹的寬度
基本方法：左右子樹的寬度相加，于是就得到二叉樹的寬度．
66
//get the width of a BST
67
int
BTreeWidth(BTree bt)
68 {
69 ??? if (bt != NULL)
70 ??? {
71 ??????? if ((bt->left == bt->right) && (bt->left == NULL))
72 ??????????? return1;// bt is a leaf
73 ??????? else
74 ??????????? return BTreeWidth(bt->left) + BTreeWidth(bt->right);
75 ??? }
76 ??? else
77 ??????? return0;
78 }//BTreeWidth
79
二叉樹的比較
??? 如果我們認為左右子樹位置很重要，也就是說把左右子樹交換以后，我們認為它和原來的子樹不一樣了，那么只需要比較一次就可以了。
51
//compare 2 binary tree, if bt1 is equal bt2
52
//return 1, or return 0
53
int
BTreeCompare(BTree bt1, BTree bt2)
54 {
55 ??? if ((bt1==bt2) && (bt1==NULL)) // both bt1 and bt2 are empty
56 ??????? return1;
57 ??? elseif ((bt1 != NULL) && (bt2 != NULL)) // none of bt1 and bt2 is empty
58 ??? {
59 ??????? return BTreeCompare(bt1->left, bt2->left)
60 ??????????? && BTreeCompare(bt1->right, bt2->right);
61 ??? }
62 ??? else// one of bt1 and bt2 is empty
63 ??????? return0;
64 }
??? 如果我們認為左右子樹位置不重要，也就是說把左右子樹交換以后，我們認為它和原來的子樹還是一樣的，那么我們還好多加判斷．把其中一個子樹左右位置交換以后再比較．那么原來的程序需要有一些改動．
59-60行需要改成以下內容就可以了。
59 ??????? return (BTreeCompare(bt1->left, bt2->left) && BTreeCompare(bt1->right, bt2->right))
60 ??????????? || (BTreeCompare(bt1->left, bt2->right) && BTreeCompare(bt1->right, bt2->left));