JZ-C-24

剑指offer第二十四题：二叉搜索树的后序遍历序列
  1 //============================================================================
  2 // Name        : JZ-C-24.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description : 二叉搜索树的后序遍历序列
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include <stdio.h>
 11 using namespace std;
 12 
 13 // BST：Binary Search Tree，二叉搜索树
 14 bool VerifySquenceOfBST(int sequence[], int length) {
 15     if (sequence == NULL || length <= 0) {
 16         return false;
 17     }
 18     int root = sequence[length - 1]; //后序遍历序列的最后一位为二叉搜索树的根结点
 19     // 在二叉搜索树中左子树的结点小于根结点
 20     int i = 0;
 21     for (; i < length - 1; i++) {
 22         if (sequence[i] > root) {
 23             break;
 24         }
 25     }
 26     // 在二叉搜索树中右子树的结点大于根结点
 27     int j = i;
 28     for (; j < length - 1; j++) {
 29         if (sequence[j] < root) {
 30             return false;
 31         }
 32     }
 33     // 递归判断左子树是不是二叉搜索树
 34     bool left = true;
 35     if (i > 0) {
 36         left = VerifySquenceOfBST(sequence, i);//结合长度i可只遍历数组中的左子树
 37     }
 38     // 递归判断右子树是不是二叉搜索树
 39     bool right = true;
 40     if (i < length- 1) {
 41         right = VerifySquenceOfBST(sequence+i,length-i-1);//sequence+i结合长度length-i-1可只遍历数组中的右子树★
 42     }
 43     return left&&right;
 44 
 45 }
 46 
 47 // ====================测试代码====================
 48 void Test(char* testName, int sequence[], int length, bool expected)
 49 {
 50     if(testName != NULL)
 51         printf("%s begins: ", testName);
 52 
 53     if(VerifySquenceOfBST(sequence, length) == expected)
 54         printf("passed.
");
 55     else
 56         printf("failed.
");
 57 }
 58 
 59 //            10
 60 //         /      
 61 //        6        14
 62 //       /        /
 63 //      4  8     12  16
 64 void Test1()
 65 {
 66     int data[] = {4, 8, 6, 12, 16, 14, 10};
 67     Test("Test1", data, sizeof(data)/sizeof(int), true);
 68 }
 69 
 70 //           5
 71 //          / 
 72 //         4   7
 73 //            /
 74 //           6
 75 void Test2()
 76 {
 77     int data[] = {4, 6, 7, 5};
 78     Test("Test2", data, sizeof(data)/sizeof(int), true);
 79 }
 80 
 81 //               5
 82 //              /
 83 //             4
 84 //            /
 85 //           3
 86 //          /
 87 //         2
 88 //        /
 89 //       1
 90 void Test3()
 91 {
 92     int data[] = {1, 2, 3, 4, 5};
 93     Test("Test3", data, sizeof(data)/sizeof(int), true);
 94 }
 95 
 96 // 1
 97 //  
 98 //   2
 99 //    
100 //     3
101 //      
102 //       4
103 //        
104 //         5
105 void Test4()
106 {
107     int data[] = {5, 4, 3, 2, 1};
108     Test("Test4", data, sizeof(data)/sizeof(int), true);
109 }
110 
111 // 树中只有1个结点
112 void Test5()
113 {
114     int data[] = {5};
115     Test("Test5", data, sizeof(data)/sizeof(int), true);
116 }
117 
118 void Test6()
119 {
120     int data[] = {7, 4, 6, 5};
121     Test("Test6", data, sizeof(data)/sizeof(int), false);
122 }
123 
124 void Test7()
125 {
126     int data[] = {4, 6, 12, 8, 16, 14, 10};
127     Test("Test7", data, sizeof(data)/sizeof(int), false);
128 }
129 
130 void Test8()
131 {
132     Test("Test8", NULL, 0, false);
133 }
134 
135 int main(int argc, char** argv)
136 {
137     Test1();
138     Test2();
139     Test3();
140     Test4();
141     Test5();
142     Test6();
143     Test7();
144     Test8();
145 
146     return 0;
147 }