二叉排序树(BST)的判定(其实不容易)

对于BST，一定要理解透彻，下面，我们给出一个有错误的BST判定程序：

[cpp] view plain copy

1. // 程序中的isBST函数的逻辑是有错误  
2.   
3. #include <iostream>  
4. #define N 7  
5. using namespace std;  
6.   
7. // BST的结点  
8. typedef struct node  
9. {  
10.     int key;  
11.     struct node *lChild, *rChild;  
12. }Node, *BST;  
13.   
14. // 在给定的BST插入element, 使之称为新的BST  
15. bool BSTInsert(Node * &p, int element)  
16. {  
17.     if(NULL == p) // 空树  
18.     {  
19.         p = new Node;  
20.         p->key = element;  
21.         p->lChild = p->rChild = NULL;  
22.         return true;  
23.     }  
24.   
25.     if(element == p->key) // BST中不能有相等的值  
26.         return false;  
27.   
28.     if(element < p->key)  // 递归  
29.         return BSTInsert(p->lChild, element);  
30.   
31.     return BSTInsert(p->rChild, element); // 递归  
32. }  
33.   
34. // 建立BST  
35. void createBST(Node * &T, int a[], int n)  
36. {  
37.     T = NULL;   
38.     int i;  
39.     for(i = 0; i < n; i++)  
40.     {  
41.         BSTInsert(T, a[i]);  
42.     }  
43. }  
44.   
45. // 生成一个结点  
46. Node *createNode(int i)  
47. {  
48.     Node * q = new Node;  
49.     q->lChild = NULL;  
50.     q->rChild = NULL;  
51.     q->key = i;  
52.   
53.     return q;  
54. }  
55.   
56. // 建立一棵非BST树(这是之前的代码，直接复制过来的)  
57. Node *createNotBST()  
58. {  
59.     Node *p[N] = {NULL};  
60.     int i;  
61.     for(i = 0; i < N; i++)  
62.         p[i] = createNode(i + 1);  
63.   
64.     for(i = 0; i < N/2; i++)  
65.     {  
66.         p[i]->lChild = p[i * 2 + 1];  
67.         p[i]->rChild = p[i * 2 + 2];  
68.     }  
69.   
70.     return p[0];  
71. }  
72.   
73. // 判断是否为BST  
74. bool isBST(BST T)  
75. {  
76.     // 空树是BST  
77.     if(NULL == T)  
78.         return true;  
79.   
80.     // 只有一个结点的数是BST树  
81.     if(NULL == T->lChild && NULL == T->rChild)  
82.         return true;  
83.   
84.     // 左子树为空(右子树不为空)  
85.     if(NULL == T->lChild)  
86.     {  
87.         if(T->key < T->rChild->key && isBST(T->rChild))  
88.             return true;  
89.   
90.         return false;  
91.     }  
92.           
93.     // 右子树为空(左子树不为空)  
94.     if(NULL == T->rChild)  
95.     {  
96.         if(T->key > T->lChild->key && isBST(T->lChild))  
97.             return true;  
98.   
99.         return false;  
100.     }  
101.       
102.     // 左右子树都非空  
103.     if(T->lChild->key < T->key &&  
104.         T->key < T->rChild->key &&  
105.         isBST(T->lChild) &&  
106.         isBST(T->rChild)  
107.         )  
108.         return true;  
109.   
110.     return false;  
111. }  
112.   
113. void printJudge(Node *T)  
114. {  
115.     if(isBST(T))  
116.         cout << "yes" << endl;  
117.     else  
118.         cout << "no" << endl;  
119. }  
120.   
121. int main()  
122. {  
123.     int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};  
124.     int n = 10;  
125.   
126.     BST T = NULL;  
127.     printJudge(T); // yes  
128.   
129.     // 并非所有的a[]都能构造出BST,所以，最好对createBST的返回值进行判断  
130.     createBST(T, a, n);  
131.     printJudge(T); // yes  
132.   
133.     T = createNotBST();  
134.     printJudge(T); // no  
135.   
136.     return 0;  
137. }  

       运行程序，发现结果是对的，但isBST函数在逻辑上是有硬伤的，不信请看isBST对下面这棵树的验证(结果为这棵非BST判为BST)：

[cpp] view plain copy

1. // 程序中的isBST函数的逻辑是有错误  
2.   
3. #include <iostream>  
4. using namespace std;  
5.   
6. // BST的结点  
7. typedef struct node  
8. {  
9.     int key;  
10.     struct node *lChild, *rChild;  
11. }Node, *BST;  
12.   
13.   
14. // 生成一个结点  
15. Node *createNode(int i)  
16. {  
17.     Node * q = new Node;  
18.     q->lChild = NULL;  
19.     q->rChild = NULL;  
20.     q->key = i;  
21.   
22.     return q;  
23. }  
24.   
25. /* 
26.     * 下面这棵树并非BST, 但程序中的isBST将其判为BST, 故isBST函数逻辑有误 
27.     * 该树为： 
28.          3        // 根节点为3 
29.        2          // 3的左孩子结点为2, 没有右孩子结点 
30.       1 4         // 2的左孩子结点为1, 右孩子结点为4 
31. */  
32. Node *createTree()  
33. {  
34.     Node *p1 = createNode(1);  
35.     Node *p2 = createNode(2);  
36.     Node *p3 = createNode(3);  
37.     Node *p4 = createNode(4);  
38.   
39.     p3->rChild = NULL;  
40.     p3->lChild = p2;  
41.   
42.     p2->lChild = p1;  
43.     p2->rChild = p4;  
44.   
45.     p1->lChild = p1->rChild = NULL;  
46.     p4->lChild = p4->rChild = NULL;  
47.   
48.     return p3;  
49. }  
50.   
51. // 判断是否为BST  
52. bool isBST(BST T)  
53. {  
54.     // 空树是BST  
55.     if(NULL == T)  
56.         return true;  
57.   
58.     // 只有一个结点的数是BST树  
59.     if(NULL == T->lChild && NULL == T->rChild)  
60.         return true;  
61.   
62.     // 左子树为空(右子树不为空)  
63.     if(NULL == T->lChild)  
64.     {  
65.         if(T->key < T->rChild->key && isBST(T->rChild))  
66.             return true;  
67.   
68.         return false;  
69.     }  
70.           
71.     // 右子树为空(左子树不为空)  
72.     if(NULL == T->rChild)  
73.     {  
74.         if(T->key > T->lChild->key && isBST(T->lChild))  
75.             return true;  
76.   
77.         return false;  
78.     }  
79.       
80.     // 左右子树都非空  
81.     if(T->lChild->key < T->key &&  
82.         T->key < T->rChild->key &&  
83.         isBST(T->lChild) &&  
84.         isBST(T->rChild)  
85.         )  
86.         return true;  
87.   
88.     return false;  
89. }  
90.   
91. void printJudge(Node *T)  
92. {  
93.     if(isBST(T))  
94.         cout << "yes" << endl;  
95.     else  
96.         cout << "no" << endl;  
97. }  
98.   
99. int main()  
100. {  
101.   
102.     BST T = NULL;  
103.     printJudge(T); // yes  
104.   
105.     T = createTree();  
106.     printJudge(T); // yes (isBST将该树错判为BST)  
107.   
108.     return 0;  
109. }  

       上述程序之所以有错，主要是因为对BST的定义理解有误，看看isBST函数就知道错在何方。

        下面，我们给出正确的程序（该程序没有考虑结点值为INT_MIN的情形）：

[cpp] view plain copy

1. #include <iostream>  
2. #define N 7  
3. using namespace std;  
4.   
5. int g_min = INT_MIN;  
6.   
7. // BST的结点  
8. typedef struct node  
9. {  
10.     int key;  
11.     struct node *lChild, *rChild;  
12. }Node, *BST;  
13.   
14. // 生成一个结点  
15. Node *createNode(int i)  
16. {  
17.     Node * q = new Node;  
18.     q->lChild = NULL;  
19.     q->rChild = NULL;  
20.     q->key = i;  
21.   
22.     return q;  
23. }  
24.   
25.   
26. /* 
27.     * 下面这棵树并非BST, 但程序中的isBST将其判为BST, 故isBST函数逻辑有误 
28.     * 该树为： 
29.          3        // 根节点为3 
30.        2          // 3的左孩子结点为2, 没有右孩子结点 
31.       1 4         // 2的左孩子结点为1, 右孩子结点为4 
32. */  
33. Node *createTree()  
34. {  
35.     Node *p1 = createNode(1);  
36.     Node *p2 = createNode(2);  
37.     Node *p3 = createNode(3);  
38.     Node *p4 = createNode(4);  
39.   
40.     p3->rChild = NULL;  
41.     p3->lChild = p2;  
42.   
43.     p2->lChild = p1;  
44.     p2->rChild = p4;  
45.   
46.     p1->lChild = p1->rChild = NULL;  
47.     p4->lChild = p4->rChild = NULL;  
48.   
49.     return p3;  
50. }  
51.   
52.   
53. // 建立一棵非BST树  
54. Node *createNotBST()  
55. {  
56.     Node *p[N] = {NULL};  
57.     int i;  
58.     for(i = 0; i < N; i++)  
59.         p[i] = createNode(i + 1);  
60.   
61.     for(i = 0; i < N/2; i++)  
62.     {  
63.         p[i]->lChild = p[i * 2 + 1];  
64.         p[i]->rChild = p[i * 2 + 2];  
65.     }  
66.   
67.     return p[0];  
68. }  
69.   
70.   
71. // 在给定的BST插入element, 使之称为新的BST  
72. bool BSTInsert(Node * &p, int element)  
73. {  
74.     if(NULL == p) // 空树  
75.     {  
76.         p = new Node;  
77.         p->key = element;  
78.         p->lChild = p->rChild = NULL;  
79.         return true;  
80.     }  
81.   
82.     if(element == p->key) // BST中不能有相等的值  
83.         return false;  
84.   
85.     if(element < p->key)  // 递归  
86.         return BSTInsert(p->lChild, element);  
87.   
88.     return BSTInsert(p->rChild, element); // 递归  
89. }  
90.   
91.   
92. // 建立BST  
93. void createBST(Node * &T, int a[], int n)  
94. {  
95.     T = NULL;   
96.     int i;  
97.     for(i = 0; i < n; i++)  
98.     {  
99.         BSTInsert(T, a[i]);  
100.     }  
101. }  
102.   
103.   
104. // 判断是否为BST  
105. bool isBST(BST T)  
106. {  
107.     if(NULL != T)  
108.     {  
109.         isBST(T->lChild);  
110.   
111.         if(T->key <= g_min)  
112.             return false;  
113.   
114.         g_min = T->key;  
115.         isBST(T->rChild);  
116.     }  
117.   
118.     return true;  
119. }  
120.   
121. void printJudge(Node *T)  
122. {  
123.     if(isBST(T))  
124.         cout << "yes" << endl;  
125.     else  
126.         cout << "no" << endl;  
127. }  
128.   
129. int main()  
130. {  
131.     int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};  
132.     int n = 10;  
133.   
134.     BST T = NULL;  
135.     g_min = INT_MIN;  
136.     printJudge(T); // yes  
137.   
138.     T = createTree();  
139.     g_min = INT_MIN;  
140.     printJudge(T); // no  
141.   
142.     T = createNotBST();  
143.     g_min = INT_MIN;  
144.     printJudge(T); // no  
145.   
146.     createBST(T, a, n);  
147.     g_min = INT_MIN;  
148.     printJudge(T); // yes  
149.   
150.     return 0;  
151. }  

       上面这个程序的原理是什么呢？怎么感觉有点类似于中序遍历呢？确实如此，其实就是中序遍历，原理是：

       (1) 空二叉树是BST

       (2) 对于非空二叉树而言：中序遍历为严格递增数列 《==》该树为BST.