一 二叉查找树的性质
二叉查找树(BinarySearchTree)是满足如下性质的一种二叉树：对于树中的每个节点n，它的左子树中所有节点的值不大于n的值，它的右子树中所有节点的值不小于n的值。
二 二叉查找树的节点
二叉查找树内封装了二叉查找树的节点，节点的域包括data, left, right, parent。
下面的代码是二叉树节点的结构体声明：
1 struct BinaryTreeNode2 {3 Comparable data;4 BinaryTreeNode *left;5 BinaryTreeNode *right;6 BinaryTreeNode *parent;7 8 BinaryTreeNode(Comparable d, BinaryTreeNode *l=NULL, BinaryTreeNode *r=NULL, BinaryTreeNode *p=NULL): data(d), left(l), right(r), parent(p) { }9 }; 其中，Comparable为模板类型，需要重载">"、"<"、"=="、"<<"等运算符。
三 二叉查找树应该具备的操作
public:
① 寻找最小数据 int findMin()
② 寻找最大数据 int findMax()
③ 是否包含数据 bool contains(int)
④ 寻找数据前趋数据 int findPredecessor(int)
⑤ 寻找数据后继数据 int findSuccessor(int)
⑥ 检测树是否为空 bool isEmpty()
⑦ 清空树的所有节点 void makeEmpty()
⑧ 插入数据 void insert(int)
⑨ 移除数据 void remove(int)
10 打印树 void printTree() 其他如构造函数、析构函数、操作符重载
private:
① 寻找最小数据节点 node findMinNode(node)
② 寻找最大数据节点 node findMaxNode(node)
③ 根据数据搜索节点 node searchNode(int)
④ 寻找节点的前趋节点 node findPredeNode(node)
⑤ 寻找节点的后继节点 node findSucNode(node)
⑥ 清空子树的所有节点 void makeEmpty(node) //注意，这边的参数应该为指针的引用类型 BinaryTreeNode *&n
⑦ 向子树中插入节点 void insertNode(int, node) ⑧ 从子树中移除节点 void removeNode(node)
⑨ 深拷贝并返回根节点 node deepClone(node)
10 中序遍历所有节点 void printLDR(node)
四 实现二叉查找树的操作
1 实现BinarySearchTree的构造函数、析构函数、"="运算符重载；以及插入数据、清空数据、打印数据等操作。
1 #include2 3 using namespace std; 4 5 //Comparable必须重载 ① '>' ② '<' ③ '==' ④ '<<' 6 template 7 class BinarySearchTree 8 { 9 public: 10 BinarySearchTree() { root = NULL; } 11 BinarySearchTree(const BinarySearchTree *bst) { root = deepClone(bst->root); } 12 ~BinarySearchTree() { makeEmpty(); } 13 14 BinarySearchTree* operator=(const BinarySearchTree *bst) 15 { 16 this->root = deepClone(bst->root); 17 return this; 18 } 19 20 void makeEmpty() 21 { 22 makeEmpty(root); 23 } 24 25 void insert(Comparable d) 26 { 27 //方法一 28 BinaryTreeNode *r = root; 29 BinaryTreeNode *p = NULL; 30 31 while (r) 32 { 33 p = r; 34 if (d < r->data) 35 r = r->left; 36 else if (d > r->data) 37 r = r->right; 38 else 39 return; //若数据相同则不插入 40 } 41 r = new BinaryTreeNode(d); 42 if (!p) 43 root = r; 44 else if (d < p->data) 45 p->left = r; 46 else 47 p->right = r; 48 r->parent = p; 49 //方法二 50 /* 51 if (root) 52 insertNode(d, root); 53 else 54 root = new BinaryTreeNode(d); 55 */ 56 } 57 58 void printTree() 59 { 60 if (root) 61 { 62 printTree(root); 63 cout << endl; 64 } 65 else 66 cout << "树中没有数据" << endl; 67 } 68 69 private: 70 struct BinaryTreeNode 71 { 72 Comparable data; 73 BinaryTreeNode *left; 74 BinaryTreeNode *right; 75 BinaryTreeNode *parent; 76 77 BinaryTreeNode(Comparable d, BinaryTreeNode *l=NULL, BinaryTreeNode *r=NULL, BinaryTreeNode *p=NULL): data(d), left(l), right(r), parent(p) { } 78 }; 79 80 BinaryTreeNode *root; 81 82 BinaryTreeNode* deepClone(BinaryTreeNode *n) 83 { 84 if (n) 85 { 86 BinaryTreeNode *p = new BinaryTreeNode(n->data, deepClone(n->left), deepClone(n->right)); 87 if (p->left) 88 p->left->parent = p; 89 if (p->right) 90 p->right->parent = p; 91 return p; 92 } 93 return NULL; 94 } 95 96 void makeEmpty(BinaryTreeNode *&n) // 需要改变指针参数 97 { 98 if (n) 99 {100 makeEmpty(n->left);101 makeEmpty(n->right);102 delete n;103 n = NULL;104 }105 return;106 }107 108 void insertNode(Comparable d, BinaryTreeNode *n)109 {110 if (d < n->data)111 {112 if (n->left)113 insertNode(d, n->left);114 else115 {116 n->left = new BinaryTreeNode(d);117 n->left->parent = n;118 }119 }120 else if (d > n->data)121 {122 if (n->right)123 insertNode(d, n->right);124 else125 {126 n->right = new BinaryTreeNode(d);127 n->right->parent = n;128 }129 }130 else131 ;132 return;133 }134 135 void printTree(BinaryTreeNode *r)136 {137 if (!r)138 return;139 printTree(r->left);140 cout << r->data << " ";141 printTree(r->right);142 }143 };
我们着重分析其中的四个操作：
1.1 insert插入数据
插入数据可以用两种方式实现：非递归方式、递归方式，但其实两种方式的思想是一样的：根据数值大小找到应该插入的位置。需要注意的是，插入时需要检测是否有根节点。
为了更简单地表达二叉查找树，可以使二叉树内数据各异，即若插入的数据在二叉树中已有，则不插入。
下面我用代码分别实现这两种方式：
1.1.1 非递归方式
1 void insert(Comparable d) 2 { 3 BinaryTreeNode *r = root; 4 BinaryTreeNode *p = NULL; 5 6 while (r) 7 { 8 p = r; 9 if (d < r->data)10 r = r->left;11 else if (d > r->data)12 r = r->right;13 else14 return; //若数据相同则不插入15 }16 r = new BinaryTreeNode(d);17 if (!p)18 root = r;19 else if (d < p->data)20 p->left = r;21 else22 p->right = r;23 r->parent = p;24 } 1.1.2 递归方式
1 void insert(Comparable d) 2 { 3 if (root) 4 insertNode(d, root); 5 else 6 root = new BinaryTreeNode(d); 7 } 8 9 void insertNode(Comparable d, BinaryTreeNode *n)10 {11 if (d < n->data)12 {13 if (n->left)14 insertNode(d, n->left);15 else16 {17 n->left = new BinaryTreeNode(d);18 n->left->parent = n;19 }20 }21 else if (d > n->data)22 {23 if (n->right)24 insertNode(d, n->right);25 else26 {27 n->right = new BinaryTreeNode(d);28 n->right->parent = n;29 }30 }31 else32 ;33 return;34 } 1.2 deepClone深拷贝
深拷贝采用了递归的方式实现。
1 BinaryTreeNode* deepClone(BinaryTreeNode *n) 2 { 3 if (n) 4 { 5 BinaryTreeNode *p = new BinaryTreeNode(n->data, deepClone(n->left), deepClone(n->right)); 6 if (p->left) 7 p->left->parent = p; 8 if (p->right) 9 p->right->parent = p;10 return p;11 }12 return NULL;13 } 1.3 printTree打印数据
由二叉查找树的性质可知，若我们中序遍历二叉树，会得到已排序好的数据。
1 void printTree() 2 { 3 if (root) 4 { 5 printTree(root); 6 cout << endl; 7 } 8 else 9 cout << "树中没有数据" << endl;10 }11 12 void printTree(BinaryTreeNode *r)13 {14 if (!r)15 return;16 printTree(r->left);17 cout << r->data << " ";18 printTree(r->right);19 } 1.4 makeEmpty清空树操作
清空树操作的思想采用递归思想，即首先递归删除该节点的左子树和右子树，然后再删除本节点。
需要注意的是，在清空树之后，需要把根节点root设置为NULL。
1 void makeEmpty() 2 { 3 makeEmpty(root); 4 } 5 6 void makeEmpty(BinaryTreeNode *&n) // 需要改变指针参数 7 { 8 if (n) 9 {10 makeEmpty(n->left);11 makeEmpty(n->right);12 delete n;13 n = NULL;14 }15 return;16 } 2 实现BinarySearchTree的删除数据操作
删除数据时需要找到对应的节点并删除，所以需要搜索操作。而由于删除节点需要寻找前趋节点或者后继节点，而寻找前趋/后继节点又需要需找子树的最大/最小数据节点，所以将这5个操作一并介绍。这些操作都可以分为非递归、递归的实现方式，就不分开讲了。
2.1 searchNode寻找节点
寻找节点与插入节点的思想一样，都是根据数据大小选择向左子树或右子树继续操作。搜索节点也可以递归的方式实现。
1 BinaryTreeNode* searchNode(Comparable d) 2 { 3 BinaryTreeNode *r = root; 4 while (r) 5 { 6 if (d < r->data) 7 r = r->left; 8 else if (d > r->data) 9 r = r->right;10 else11 return r;12 }13 return NULL;14 } 2.2 findMin寻找最小数据(节点)
没什么好说的，根据二叉搜索树的性质，一直向左子树寻找。
1 Comparable findMin() 2 { 3 // 方法一 4 BinaryTreeNode *r = root; 5 BinaryTreeNode *p = NULL; 6 while (r) 7 { 8 p = r; 9 r = r->left;10 }11 if (p)12 return p->data;13 else14 return -1;15 // 方法二16 //return findMinNode(root)->data;17 }18 19 BinaryTreeNode* findMinNode(BinaryTreeNode *n)20 {21 if (n->left)22 return findMinNode(n->left);23 return n;24 } 2.3 findMax寻找最大数据(节点)
也没什么好说的，根据二叉搜索树的性质，一直向右子树寻找。
1 Comparable findMax() 2 { 3 // 方法一 4 BinaryTreeNode *r = root; 5 BinaryTreeNode *p = NULL; 6 while (r) 7 { 8 p = r; 9 r = r->right;10 }11 if (p)12 return p->data;13 else14 return -1;15 // 方法二16 //return findMaxNode(root)->data;17 }18 19 BinaryTreeNode* findMaxNode(BinaryTreeNode *n)20 {21 if (n->right)22 return findMaxNode(n->right);23 return n;24 } 2.4 findPredecessor寻找前趋数据(节点)
寻找前趋数据时分两种情况。
我们假定该节点为n，前趋节点为p，则有
① 若节点n存在左子树，则显然n的左子树中数据最大的节点为前趋节点
② 若节点n不存在左子树，则需要向上搜索找到满足以下条件的节点p：节点n在节点p的右子树中。若向上搜索时，子节点n为父节点p的左子树，则继续向上搜索，直到节点p为NULL。
1 Comparable findPredecessor(Comparable d) 2 { 3 BinaryTreeNode *n = searchNode(d); 4 if (n) 5 { 6 BinaryTreeNode *pre = findPredeNode(n); 7 8 if (pre) 9 return pre->data;10 else11 return n->data;12 }13 else14 return d;15 }16 17 BinaryTreeNode* findPredeNode(BinaryTreeNode *n)18 {19 BinaryTreeNode *p = NULL;20 if (n->left)21 return findMaxNode(n->left);22 p = n->parent;23 while (p && n == p->left)24 {25 n = p;26 p = p->parent;27 }28 return p;29 } 2.5 findSuccessor寻找后继数据(节点)
寻找后继数据时分两种情况。
我们假定该节点为n，后继节点为p，则有
① 若节点n存在右子树，则显然n的右子树中数据最小的节点为后继节点
② 若节点n不存在右子树，则需要向上搜索找到满足以下条件的节点p：节点n在节点p的左子树中。若向上搜索时，子节点n为父节点p的右子树，则继续向上搜索，直到节点p为NULL。
1 Comparable findSuccessor(Comparable d) 2 { 3 BinaryTreeNode *n = searchNode(d); 4 if (n) 5 { 6 BinaryTreeNode *suc = findSucNode(n); 7 8 if (suc) 9 return suc->data;10 else11 return n->data;12 }13 else14 return d;15 }16 17 BinaryTreeNode* findSucNode(BinaryTreeNode *n)18 {19 BinaryTreeNode *p = NULL;20 if (n->right)21 return findMinNode(n->right);22 p = n->parent;23 while (p && n == p->right)24 {25 n = p;26 p = p->parent;27 }28 return p;29 } 2.6 删除数据(节点)
删除节点是分三种情况。
我们假定被删除的节点为n，n节点的父节点为p，则有：
① 被删除节点没有子节点，这个最简单，直接删了就可以，同时将p的相关子节点域left/right改为NULL
② 被删除节点只有一个子节点，这个也简单，将该节点的父节点与子节点相连即可，同时将p的相关子节点域left/right为NULL、子节点的父节点域parent为p。
③ 被删除节点有两个子节点，这个稍微有点麻烦，不过可以换个思路解决。即不是真正的删除这个节点，而是将节点n的前趋或后继节点的数据拷贝过来，然后转而删除节点n的前趋或后继节点，一般使用后继节点。若后继节点仍然有两个节点，则一直向下搜索，直到将情况③转换为情况①②。
情况①②的代码可以合并优化，同时还是需要特别注意根节点，若被删除的节点是根节点root，则直接将其子节点重新设置为root，不需要也不能够修改子节点域left/right和父节点域parent。
1 void remove(Comparable d) 2 { 3 BinaryTreeNode *n = searchNode(d); 4 5 if (n != NULL) 6 { 7 //方法一 8 while (n->left && n->right) 9 {10 n->data = findSucNode(n)->data;11 n = findSucNode(n);12 }13 14 BinaryTreeNode *x = (n->left) ? n->left : n->right;15 if (n == root)16 root = x;17 else18 {19 if (n == n->parent->left)20 n->parent->left = x;21 else22 n->parent->right = x;23 if (x)24 x->parent = n->parent;25 }26 delete n;27 //方法二28 //removeNode(n);29 }30 }31 32 void removeNode(BinaryTreeNode *n)33 {34 if (!n)35 return;36 if (n->left && n->right)37 {38 n->data = findPredeNode(n)->data;39 removeNode(findPredeNode(n));40 //n->data = findSucNode(n)->data;41 //removeNode(findSucNode(n));42 }43 else44 {45 BinaryTreeNode *x = (n->left) ? n->left : n->right;46 if (n == root)47 root = x;48 else49 {50 if (n == n->parent->left)51 n->parent->left = x;52 else53 n->parent->right = x;54 if (x)55 x->parent = n->parent;56 }57 delete n;58 }59 }
3 其他操作，如contains检测是否包含某数据、isEmpty检测是否为空。
检测是否包含数据，只要检测searchNode()返回的指针是否为空；检测是否为空，只要检测根节点root是否为空。
五 完整代码
5.1 BinarySearchTree.hpp
1 #include2 3 using namespace std; 4 5 //Comparable必须重载 ① '>' ② '<' ③ '==' ④ '<<' 6 template 7 class BinarySearchTree 8 { 9 public: 10 BinarySearchTree() { root = NULL; } 11 BinarySearchTree(const BinarySearchTree *bst) { root = deepClone(bst->root); } 12 ~BinarySearchTree() { makeEmpty(); } 13 14 BinarySearchTree* operator=(const BinarySearchTree *bst) 15 { 16 this->root = deepClone(bst->root); 17 return this; 18 } 19 20 Comparable findMin() 21 { 22 // 方法一 23 BinaryTreeNode *r = root; 24 BinaryTreeNode *p = NULL; 25 while (r) 26 { 27 p = r; 28 r = r->left; 29 } 30 if (p) 31 return p->data; 32 else 33 return -1; 34 // 方法二 35 //return findMinNode(root)->data; 36 } 37 38 Comparable findMax() 39 { 40 // 方法一 41 BinaryTreeNode *r = root; 42 BinaryTreeNode *p = NULL; 43 while (r) 44 { 45 p = r; 46 r = r->right; 47 } 48 if (p) 49 return p->data; 50 else 51 return -1; 52 // 方法二 53 //return findMaxNode(root)->data; 54 } 55 56 bool contains(Comparable d) 57 { 58 // 方法一 59 BinaryTreeNode *r = root; 60 while (r) 61 { 62 if (d < r->data) 63 r = r->left; 64 else if (d > r->data) 65 r = r->right; 66 else 67 return true; 68 } 69 return false; 70 // 方法二 71 //return searchNode(d) ? true : false; 72 } 73 74 Comparable findPredecessor(Comparable d) 75 { 76 BinaryTreeNode *n = searchNode(d); 77 if (n) 78 { 79 BinaryTreeNode *pre = findPredeNode(n); 80 81 if (pre) 82 return pre->data; 83 else 84 return n->data; 85 } 86 else 87 return d; 88 } 89 90 Comparable findSuccessor(Comparable d) 91 { 92 BinaryTreeNode *n = searchNode(d); 93 if (n) 94 { 95 BinaryTreeNode *suc = findSucNode(n); 96 97 if (suc) 98 return suc->data; 99 else100 return n->data;101 }102 else103 return d;104 }105 106 bool isEmpty()107 {108 return root ? false : true;109 }110 111 void makeEmpty()112 {113 makeEmpty(root);114 }115 116 void insert(Comparable d)117 {118 //方法一119 BinaryTreeNode *r = root;120 BinaryTreeNode *p = NULL;121 122 while (r)123 {124 p = r;125 if (d < r->data)126 r = r->left;127 else if (d > r->data)128 r = r->right;129 else130 return; //若数据相同则不插入131 }132 r = new BinaryTreeNode(d);133 if (!p)134 root = r;135 else if (d < p->data)136 p->left = r;137 else138 p->right = r;139 r->parent = p;140 //方法二141 /*142 if (root)143 insertNode(d, root);144 else145 root = new BinaryTreeNode(d);146 */147 }148 149 void remove(Comparable d)150 {151 BinaryTreeNode *n = searchNode(d);152 153 if (n != NULL)154 {155 //方法一156 while (n->left && n->right)157 {158 n->data = findSucNode(n)->data;159 n = findSucNode(n);160 }161 162 BinaryTreeNode *x = (n->left) ? n->left : n->right;163 if (n == root)164 root = x;165 else166 {167 if (n == n->parent->left)168 n->parent->left = x;169 else170 n->parent->right = x;171 if (x)172 x->parent = n->parent;173 }174 delete n;175 //方法二176 //removeNode(n);177 }178 }179 180 void printTree()181 {182 if (root)183 {184 printTree(root);185 cout << endl;186 }187 else188 cout << "树中没有数据" << endl;189 }190 191 private:192 struct BinaryTreeNode193 {194 Comparable data;195 BinaryTreeNode *left;196 BinaryTreeNode *right;197 BinaryTreeNode *parent;198 199 BinaryTreeNode(Comparable d, BinaryTreeNode *l=NULL, BinaryTreeNode *r=NULL, BinaryTreeNode *p=NULL): data(d), left(l), right(r), parent(p) { }200 };201 202 BinaryTreeNode *root;203 204 BinaryTreeNode* deepClone(BinaryTreeNode *n)205 {206 if (n)207 {208 BinaryTreeNode *p = new BinaryTreeNode(n->data, deepClone(n->left), deepClone(n->right));209 if (p->left)210 p->left->parent = p;211 if (p->right)212 p->right->parent = p;213 return p;214 }215 return NULL;216 }217 218 BinaryTreeNode* findMinNode(BinaryTreeNode *n)219 {220 if (n->left)221 return findMinNode(n->left);222 return n;223 }224 225 BinaryTreeNode* findMaxNode(BinaryTreeNode *n)226 {227 if (n->right)228 return findMaxNode(n->right);229 return n;230 }231 232 BinaryTreeNode* searchNode(Comparable d)233 {234 BinaryTreeNode *r = root;235 while (r)236 {237 if (d < r->data)238 r = r->left;239 else if (d > r->data)240 r = r->right;241 else242 return r;243 }244 return NULL;245 }246 247 BinaryTreeNode* findPredeNode(BinaryTreeNode *n)248 {249 BinaryTreeNode *p = NULL;250 if (n->left)251 return findMaxNode(n->left);252 p = n->parent;253 while (p && n == p->left)254 {255 n = p;256 p = p->parent;257 }258 return p;259 }260 261 BinaryTreeNode* findSucNode(BinaryTreeNode *n)262 {263 BinaryTreeNode *p = NULL;264 if (n->right)265 return findMinNode(n->right);266 p = n->parent;267 while (p && n == p->right)268 {269 n = p;270 p = p->parent;271 }272 return p;273 }274 275 void makeEmpty(BinaryTreeNode *&n) // 需要改变指针参数276 {277 if (n)278 {279 makeEmpty(n->left);280 makeEmpty(n->right);281 delete n;282 n = NULL;283 }284 return;285 }286 287 void insertNode(Comparable d, BinaryTreeNode *n)288 {289 if (d < n->data)290 {291 if (n->left)292 insertNode(d, n->left);293 else294 {295 n->left = new BinaryTreeNode(d);296 n->left->parent = n;297 }298 }299 else if (d > n->data)300 {301 if (n->right)302 insertNode(d, n->right);303 else304 {305 n->right = new BinaryTreeNode(d);306 n->right->parent = n;307 }308 }309 else310 ;311 return;312 }313 314 void removeNode(BinaryTreeNode *n)315 {316 if (!n)317 return;318 if (n->left && n->right)319 {320 n->data = findPredeNode(n)->data;321 removeNode(findPredeNode(n));322 //n->data = findSucNode(n)->data;323 //removeNode(findSucNode(n));324 }325 else326 {327 BinaryTreeNode *x = (n->left) ? n->left : n->right;328 if (n == root)329 root = x;330 else331 {332 if (n == n->parent->left)333 n->parent->left = x;334 else335 n->parent->right = x;336 if (x)337 x->parent = n->parent;338 }339 delete n;340 }341 }342 343 void printTree(BinaryTreeNode *r)344 {345 if (!r)346 return;347 printTree(r->left);348 cout << r->data << " ";349 printTree(r->right);350 }351 };
5.2 main.cpp
1 #include2 #include 3 #include 4 5 #include "BinarySearchTree.hpp" 6 7 using namespace std; 8 9 const int LENGTH = 8; 10 11 void generateTree(BinarySearchTree *tree) 12 { 13 srand((unsigned int)time(NULL)); 14 int i = LENGTH; 15 while(i--) 16 { 17 tree->insert(rand() % 100); 18 } 19 } 20 21 void checkDeepClone(BinarySearchTree *tree) 22 { 23 BinarySearchTree *newTree = tree; 24 //BinarySearchTree *newTree = new BinarySearchTree (tree); 25 cout << "数据拷贝完成" << endl; 26 newTree->printTree(); 27 } 28 29 void checkMinMax(BinarySearchTree *tree) 30 { 31 cout << "Min: " << tree->findMin() << endl; 32 cout << "Max: " << tree->findMax() << endl; 33 } 34 35 void checkContains(BinarySearchTree *tree) 36 { 37 int elem; 38 cout << "请输入用来测试是否包含的数据: "; 39 cin >> elem; 40 if (tree->contains(elem)) 41 cout << "存在" << endl; 42 else 43 cout << "不存在" << endl; 44 } 45 46 void checkPreSuc(BinarySearchTree *tree) 47 { 48 int elem; 49 cout << "请输入用来测试前趋后继的数据: "; 50 cin >> elem; 51 cout << elem << "的前趋为" << tree->findPredecessor(elem) << endl; 52 cout << elem << "的后继为" << tree->findSuccessor(elem) << endl; 53 } 54 55 void checkEmpty(BinarySearchTree *tree) 56 { 57 if (tree->isEmpty()) 58 cout << "树为空" << endl; 59 else 60 cout << "树不为空" << endl; 61 62 tree->makeEmpty(); 63 tree->printTree(); 64 65 if (tree->isEmpty()) 66 cout << "树为空" << endl; 67 else 68 cout << "树不为空" << endl; 69 } 70 71 void checkRemove(BinarySearchTree *tree) 72 { 73 if (tree->isEmpty()) 74 { 75 generateTree(tree); 76 tree->printTree(); 77 } 78 while (!tree->isEmpty()) 79 { 80 int elem; 81 cout << "请输入要移除的数据: "; 82 cin >> elem; 83 tree->remove(elem); 84 tree->printTree(); 85 86 } 87 } 88 89 int main() 90 { 91 BinarySearchTree *tree = new BinarySearchTree (); 92 generateTree(tree); 93 tree->printTree(); 94 95 checkDeepClone(tree); 96 97 checkMinMax(tree); 98 99 checkContains(tree);100 checkContains(tree);101 102 checkPreSuc(tree);103 checkPreSuc(tree);104 checkPreSuc(tree);105 checkPreSuc(tree);106 107 checkEmpty(tree);108 109 checkRemove(tree);110 111 system("pause");112 }
5.3 运行结果截图
另外，发现有的递归可以以非递归的方式实现，而有的递归不能转化为非递归方式。
可以将递归转化为非递归的递归称为"尾递归"。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器角度来说，亦容易优化成为普通循环。