首页 > 代码库 > 二叉查找树
二叉查找树
树的介绍部分摘取自博文二叉查找树(一)、二叉查找树(二)。
1. 树的介绍
1.1 树的定义
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。
把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
(1) 每个节点有零个或多个子节点；
(2) 没有父节点的节点称为根节点；
(3) 每一个非根节点有且只有一个父节点；
(4) 除了根节点外，每个子节点可以分为多个不相交的子树。
2. 树的基本术语
若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。有相同双亲的结点互为"兄弟"。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度：结点拥有的子树的数目。
叶子：度为零的结点。
分支结点：度不为零的结点。
树的度：树中结点的最大的度。
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的高度：树中结点的最大层次。
无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。
有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。
2. 二叉树介绍
2.1 二叉树的定义
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
2.2 二叉树的性质
二叉树有以下几个性质：TODO(上标和下标)
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)
证明：下面用"数学归纳法"进行证明。
(01) 当i=1时，第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点，所以命题成立。
(02) 假设当i>1，第i层的节点数目为2{i-1}。这个是根据(01)推断出来的！
下面根据这个假设，推断出"第(i+1)层的节点数目为2{i}"即可。
由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目" 最多是 "第i层的结点数目的2倍"。即，第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。
故假设成立，原命题得证！
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)
证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故原命题得证！
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)
证明：根据"性质2"可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)="0度结点数(n0)" + "1度结点数(n1)" + "2度结点数(n2)"。由此，得到等式一。
(等式一) n=n0+n1+n2
另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！
2.3 满二叉树，完全二叉树和二叉查找树
1）满二叉树
定义：高度为h，并且由2{h} –1个结点的二叉树，被称为满二叉树。
2）完全二叉树
定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
3）二叉查找树
定义：二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。
在二叉查找树中：
(1) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(3) 任意节点的左、右子树也分别为二叉查找树。
(4) 没有键值相等的节点（no duplicate nodes）。
在实际应用中，二叉查找树的使用比较多。
3. 二叉查找树遍历
3.1 前序遍历
若二叉树非空，则执行以下操作：
(1) 访问根结点；
(2) 先序遍历左子树；
(3) 先序遍历右子树
3.2 中序遍历
若二叉树非空，则执行以下操作：
(1) 中序遍历左子树；
(2) 访问根结点；
(3) 中序遍历右子树。
3.3 后序遍历
若二叉树非空，则执行以下操作：
(1) 后序遍历左子树；
(2) 后序遍历右子树；
(3) 访问根结点。
看看下面这颗树的各种遍历方式：
对于上面的二叉树而言，
(1) 前序遍历结果： 3 1 2 5 4 6
(2) 中序遍历结果： 1 2 3 4 5 6
(3) 后序遍历结果： 2 1 4 6 5 3
4. 二叉查找树实现
我定义的类如下：
1 template < class T > 2 class BSTNode 3 { 4 public: 5 BSTNode() :left(NULL), right(NULL){ }; 6 ~BSTNode(){ }; 7 8 public: 9 int key;10 T data;11 BSTNode * left;12 BSTNode * right;13 };14 15 template<class T>16 class BSTree17 {18 public:19 typedef BSTNode<T> * NodePointer;20 21 public:22 BSTree();23 virtual ~BSTree();24 BSTree(const BSTree& orig);25 BSTree& operator=(const BSTree& orig);26 bool isEmpty();27 void creatBSTree(T * k, T * arr, unsigned len);28 bool addNode(T k, T val);29 bool deleteNode(T k);30 BSTNode<T> * searchNode(T k);31 void preOrder(); //先序遍历32 void inOrder(); //中序遍历33 void postOrder(); //后序遍历34 void destroy(); // 释放整棵树35 36 // 单元测试用37 T getTestData(int pos);38 39 private:40 NodePointer root;41 void destroy(NodePointer parentNode);42 void preOrder(NodePointer tree); 43 void inOrder(NodePointer tree); 44 void postOrder(NodePointer tree); 45 46 private:47 // 单元测试用48 int count;49 T testData[1024];50 51 };
完整实现程序：
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 template < class T > 6 class BSTNode 7 { 8 public: 9 BSTNode() :left(NULL), right(NULL){ }; 10 ~BSTNode(){ }; 11 12 public: 13 int key; 14 T data; 15 BSTNode * left; 16 BSTNode * right; 17 }; 18 19 template<class T> 20 class BSTree 21 { 22 public: 23 typedef BSTNode<T> * NodePointer; 24 25 public: 26 BSTree(); 27 virtual ~BSTree(); 28 BSTree(const BSTree& orig); 29 BSTree& operator=(const BSTree& orig); 30 bool isEmpty(); 31 void creatBSTree(T * k, T * arr, unsigned len); 32 bool addNode(T k, T val); 33 bool deleteNode(T k); 34 BSTNode<T> * searchNode(T k); 35 void preOrder(); //先序遍历 36 void inOrder(); //中序遍历 37 void postOrder(); //后序遍历 38 void destroy(); // 释放整棵树 39 40 // 单元测试用 41 T getTestData(int pos); 42 43 private: 44 NodePointer root; 45 void destroy(NodePointer parentNode); 46 void preOrder(NodePointer tree); 47 void inOrder(NodePointer tree); 48 void postOrder(NodePointer tree); 49 50 private: 51 // 单元测试用 52 int count; 53 T testData[1024]; 54 55 }; 56 57 template<class T> 58 BSTree<T>::BSTree() 59 { 60 root = NULL; 61 } 62 63 template<class T> 64 BSTree<T>::~BSTree() 65 { 66 destroy(root); 67 root = NULL; // 以防root成为“野指针” 68 } 69 70 template<class T> 71 BSTree<T>::BSTree(const BSTree& orig) 72 { 73 // leave blank 74 } 75 76 77 template<class T> 78 BSTree<T>& BSTree<T>::operator=(const BSTree& orig) 79 { 80 // leave blank 81 return *this; 82 } 83 84 template<class T> 85 bool BSTree<T>::isEmpty() 86 { 87 return root == NULL; 88 } 89 90 template<class T> 91 void BSTree<T>::creatBSTree(T * k, T * arr, unsigned len) 92 { 93 for (int i = 0; i < len; i++) 94 { 95 addNode(k[i], arr[i]); 96 } 97 } 98 99 template<class T>100 bool BSTree<T>::addNode(T k, T val)101 {102 bool isSuccess = true;103 // to allocate memory104 // method 1105 NodePointer ptr = new(nothrow)BSTNode<T>();106 if (ptr == NULL)107 {108 return false;109 }110 // method 2111 //NodePointer ptr;112 //try113 //{114 // ptr = new BSTNode<T>();115 //}116 //catch (bad_alloc* e)117 //{118 // return false;119 //}120 //catch (exception* e)121 //{122 // return false;123 //}124 ptr->key = k;125 ptr->data =http://www.mamicode.com/ val;126 if (root == NULL)127 {128 root = ptr;129 }130 else131 {132 NodePointer tmpPtr = root;133 while (tmpPtr != NULL)134 {135 if (k == tmpPtr->key)136 {137 isSuccess = false;138 break;139 }140 else if (k < tmpPtr->key)141 {142 if (tmpPtr->left == NULL)143 {144 tmpPtr->left = ptr;145 break;146 }147 else148 {149 tmpPtr = tmpPtr->left;150 }151 }152 else153 {154 if (tmpPtr->right == NULL)155 {156 tmpPtr->right = ptr;157 break;158 }159 else160 {161 tmpPtr = tmpPtr->right;162 }163 }164 }165 }166 167 return isSuccess;168 }169 170 // 删除某个节点，这时简单地删除包括该节点及其所有儿子171 template<class T>172 bool BSTree<T>::deleteNode(T k)173 {174 bool isSuccess = true;175 bool leftOrRight = true;176 NodePointer ptr = NULL, parentPtr = NULL, tmpPtr = root;177 while (tmpPtr != NULL)178 {179 if (k == tmpPtr->key)180 {181 ptr = tmpPtr;182 break;183 }184 else if (k < tmpPtr->key)185 {186 if (tmpPtr->left == NULL)187 {188 isSuccess = false;189 break;190 }191 else192 {193 parentPtr = tmpPtr;194 tmpPtr = tmpPtr->left;195 }196 }197 else198 {199 if (tmpPtr->right == NULL)200 {201 isSuccess = false;202 break;203 }204 else205 {206 parentPtr = tmpPtr;207 leftOrRight = false;208 tmpPtr = tmpPtr->right;209 }210 }211 }212 213 // 内存释放214 if (ptr != NULL)215 {216 if (ptr == root)217 {218 destroy(root);219 root = NULL; // 以防root成为“野指针”220 }221 else222 {223 if (leftOrRight)224 {225 parentPtr->left = NULL;226 }227 else228 {229 parentPtr->right = NULL;230 }231 destroy(ptr);232 ptr = NULL; // 以防ptr成为“野指针”233 }234 }235 236 return isSuccess;237 }238 239 template<class T>240 BSTNode<T> * BSTree<T>::searchNode(T k)241 {242 NodePointer ptr = NULL, tmpPtr = root;243 while (tmpPtr != NULL)244 {245 if (k == tmpPtr->key)246 {247 ptr = tmpPtr;248 break;249 }250 else if (k < tmpPtr->key)251 {252 if (tmpPtr->left == NULL)253 {254 break;255 }256 else257 {258 tmpPtr = tmpPtr->left;259 }260 }261 else262 {263 if (tmpPtr->right == NULL)264 {265 break;266 }267 else268 {269 tmpPtr = tmpPtr->right;270 }271 }272 }273 274 return ptr;275 }276 277 template<class T>278 void BSTree<T>::preOrder()279 {280 count = 0;281 preOrder(root);282 }283 284 template<class T>285 void BSTree<T>::preOrder(NodePointer tree)286 {287 if (tree != NULL) // 注意这里不是用while循环288 {289 // cout << tmpPtr->data << end;290 testData[count] = tree->data;291 count++;292 preOrder(tree->left);293 preOrder(tree->right);294 }295 }296 297 template<class T>298 void BSTree<T>::inOrder()299 {300 count = 0;301 inOrder(root);302 }303 304 template<class T>305 void BSTree<T>::inOrder(NodePointer tree)306 {307 if (tree != NULL)308 {309 inOrder(tree->left);310 // cout << tmpPtr->data << end;311 testData[count] = tree->data;312 count++;313 inOrder(tree->right);314 }315 }316 317 template<class T>318 void BSTree<T>::postOrder()319 {320 count = 0;321 postOrder(root);322 }323 324 template<class T>325 void BSTree<T>::postOrder(NodePointer tree)326 {327 if (tree != NULL)328 {329 postOrder(tree->left);330 postOrder(tree->right);331 // cout << tmpPtr->data << end;332 testData[count] = tree->data;333 count++;334 }335 }336 337 template<class T>338 void BSTree<T>::destroy()339 {340 destroy(root);341 root = NULL;342 }343 344 template<class T>345 void BSTree<T>::destroy(NodePointer parentNode)346 {347 NodePointer leftPtr = NULL, rightPtr = NULL;348 if (parentNode != NULL)349 {350 leftPtr = parentNode->left;351 rightPtr = parentNode->right;352 delete parentNode;353 parentNode = NULL; // 这一句十分重要。因为parentNode被释放后成为一个354 // “野指针”，即不是NULL指针，因此会让while循环355 // 在释放完所有的内存后再循环一次，而此时parentNode356 // 已经是一个“野指针”，对它再进行内存释放必然出错357 destroy(leftPtr);358 destroy(rightPtr);359 }360 361 }362 363 template<class T>364 T BSTree<T>::getTestData(int pos)365 {366 return testData[pos];367 }
Boost单元测试程序：
1 #define BOOST_TEST_MODULE BinaryTree_Test_Module 2 3 #include "stdafx.h" 4 #include "../BSTree/bstree.hpp" 5 6 struct BSTree_Fixture 7 { 8 public: 9 BSTree_Fixture() 10 { 11 testBSTree = new BSTree<int>(); 12 } 13 ~BSTree_Fixture() 14 { 15 delete testBSTree; 16 } 17 18 BSTree<int> * testBSTree; 19 }; 20 21 BOOST_FIXTURE_TEST_SUITE(BinTree_Test_Suite, BSTree_Fixture) 22 23 BOOST_AUTO_TEST_CASE( BinTree_Nomal_Test ) 24 { 25 // isEmpty ------------------------------------- 26 BOOST_REQUIRE(testBSTree->isEmpty() == true); 27 28 // addNode & searchNode --------------------------- 29 BOOST_REQUIRE(testBSTree->addNode(1, 1) == true); 30 BOOST_REQUIRE(testBSTree->searchNode(1) != NULL); 31 BOOST_REQUIRE((testBSTree->searchNode(1))->data =http://www.mamicode.com/= 1); 32 BOOST_REQUIRE(testBSTree->isEmpty() == false); 33 34 BOOST_REQUIRE(testBSTree->addNode(0, 0) == true); 35 BOOST_REQUIRE(testBSTree->searchNode(0) != NULL); 36 BOOST_REQUIRE((testBSTree->searchNode(0))->data =http://www.mamicode.com/= 0); 37 38 BOOST_REQUIRE(testBSTree->addNode(2, 2) == true); 39 BOOST_REQUIRE(testBSTree->searchNode(2) != NULL); 40 BOOST_REQUIRE((testBSTree->searchNode(2))->data =http://www.mamicode.com/= 2); 41 42 BOOST_REQUIRE(testBSTree->addNode(3, 3) == true); 43 BOOST_REQUIRE(testBSTree->searchNode(3) != NULL); 44 BOOST_REQUIRE((testBSTree->searchNode(3))->data =http://www.mamicode.com/= 3); 45 46 // deleteNode ---------------------------------- 47 BOOST_REQUIRE(testBSTree->deleteNode(0) == true); 48 BOOST_REQUIRE(testBSTree->searchNode(0) == NULL); 49 BOOST_REQUIRE(testBSTree->searchNode(1)->data =http://www.mamicode.com/= 1); 50 BOOST_REQUIRE(testBSTree->searchNode(2)->data =http://www.mamicode.com/= 2); 51 BOOST_REQUIRE(testBSTree->searchNode(3)->data =http://www.mamicode.com/= 3); 52 53 BOOST_REQUIRE(testBSTree->deleteNode(3) == true); 54 BOOST_REQUIRE(testBSTree->searchNode(3) == NULL); 55 BOOST_REQUIRE(testBSTree->searchNode(1)->data =http://www.mamicode.com/= 1); 56 BOOST_REQUIRE(testBSTree->searchNode(2)->data =http://www.mamicode.com/= 2); 57 58 BOOST_REQUIRE(testBSTree->deleteNode(1) == true); 59 BOOST_REQUIRE(testBSTree->searchNode(1) == NULL); 60 BOOST_REQUIRE(testBSTree->searchNode(2) == NULL); 61 62 // creatBSTree -------------------------------- 63 int key[] = { 1, 0, 2, 3 }; 64 int value[] = { 1, 0, 2, 3 }; 65 unsigned len = sizeof(key) / sizeof(int); 66 testBSTree->creatBSTree(key, value, len); 67 68 // preOrder ------------------------------------ 69 testBSTree->preOrder(); 70 BOOST_REQUIRE(testBSTree->getTestData(0) == 1); 71 BOOST_REQUIRE(testBSTree->getTestData(1) == 0); 72 BOOST_REQUIRE(testBSTree->getTestData(2) == 2); 73 BOOST_REQUIRE(testBSTree->getTestData(3) == 3); 74 75 // inOrder ------------------------------------- 76 testBSTree->inOrder(); 77 BOOST_REQUIRE(testBSTree->getTestData(0) == 0); 78 BOOST_REQUIRE(testBSTree->getTestData(1) == 1); 79 BOOST_REQUIRE(testBSTree->getTestData(2) == 2); 80 BOOST_REQUIRE(testBSTree->getTestData(3) == 3); 81 82 // postOrder ----------------------------------- 83 testBSTree->postOrder(); 84 BOOST_REQUIRE(testBSTree->getTestData(0) == 0); 85 BOOST_REQUIRE(testBSTree->getTestData(1) == 3); 86 BOOST_REQUIRE(testBSTree->getTestData(2) == 2); 87 BOOST_REQUIRE(testBSTree->getTestData(3) == 1); 88 89 // destroy ------------------------------------- 90 testBSTree->destroy(); 91 92 } 93 94 BOOST_AUTO_TEST_CASE(BinTree_CopyConstructor_Test) 95 { 96 // leave blank 97 } 98 99 BOOST_AUTO_TEST_CASE(BinTree_EqualOperator_Test)100 {101 // leave blank102 }103 104 BOOST_AUTO_TEST_SUITE_END()
另一可参考程序：http://www.2cto.com/kf/201311/259072.html
本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.
二叉查找树