问题的提出
经常会遇到关于二叉树的算法问题，虽然比较简单，不过我觉得还是有必要总结一下．顺便写了个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));