二叉排序树，又叫二叉查找树，还叫二叉搜索树，所以既属于排序算法，也属于查找算法。
所以BSTree 可以理解为：Binary Sort Tree 或者是 Binary Search Tree。
二叉排序树的定义：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
数据结构：
|
1 2 3 4 5 6 |
typedef int KeyType; typedef struct Node{ KeyType val; struct Node *lChild; struct Node *rChild; }BSTNode, *BSTree; |
首先讲插入（InsertBST）：
二叉排序树的插入是很简单的。
步骤如下：
1.根结点判空，如果是空，则插入。
2.如果根结点不是空，与根结点判重，重复返回false（因为理论上不重复）
3.不是空，和根结点比较大小，小的插入到左边子树，大的插入到右边子树。
完了…代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
bool InsertBST(BSTree &root, KeyType key) { if(NULL == root) { root = new Node; root->val = key; root->lChild = root->rChild = NULL; return true; } if(key == root->val)//理论上不重复 { return false; } else if(key < root->val) { return InsertBST(root->lChild, key); } else { return InsertBST(root->rChild, key); } } |
然后讲创建（CreateBST）：
创建就简单了，先把根结点搞成空（不然就可能是野指针），然后开始一个个的插入。
|
1 2 3 4 5 6 7 8 9 |
void CreateBST(BSTree &root) { root = NULL;//不赋空值就是野指针... KeyType temp; while(scanf("%d",&temp) && (temp != -1)) { InsertBST(root, temp); } } |
查找（SearchBST）：
一样的，先判断根结点，相对返回，比根小找左边，大就找右边…SoEazy…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
BSTree SearchBST(BSTree root, KeyType key) { if(NULL == root) return root; if(root->val == key) { return root; } else if(key < root->val) { return SearchBST(root->lChild,key); } else { return SearchBST(root->rChild,key); } } |
最后是删除（DeleteBST）：删除是比较复杂的，但是也很好理解。
算法思路如下：
1. 查找关键字为Key的结点（即找到删除的结点）。
PS. 这里查找的时候不能用SearchBST，因为我们还要找到要删除的结点的父结点。
2. 找不到key直接返回即可。假设找到的结点名字是p，父节点是f那么有如下几种情况。
没有左子树的情况：
3.1 如果p没有左子树，判断p是不是根，如果是根，则让root变为p的右子树，然后删除p
3.1.1 如果不是根，p是f的左子树，则把p的右子树给f的左子树。删除p.
3.1.2 如果不是根，p是f的右子树，则把p的右子树给f的右子树。删除p.
有左子树的情况：
4.2 如果p有左子树，则找到p的左子树里的最大值（即一直往右下），假设找到s，同时用q记录s的父节点。
4.2.1 然后把s的左子树链接到s的父节点q.
4.2.2 如果q==p 即：p的左子树没有右子树，即找到的s是p（待删除节点）的左子树，则把s的左子树放到q的左子树.
4.2.3 否则 将s的左子树放到q的右子树（替代原来s的位置）。
4.2.4 将s的值赋给p，删除s（即值交换）。
画图理解吧…把几个情况画一下，还是蛮好搞的…（因为太长，所以最小化了）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
BSTree DeleteBST(BSTree root, KeyType key) { BSTree p = NULL; BSTree f = NULL; BSTree s = NULL; BSTree q = NULL; p = root; //查找关键字为Key的待删除节点 while(p) { if(p->val == key)break; f = p; if(p->val > key) { p = p->lChild; } else { p = p->rChild; } } //如果找不到，返回原来的二叉树？ if(NULL == p) return root; //如果p没有左子树 if(NULL == p->lChild) { //p是原二叉树的根 if(NULL == f) { root = p->rChild; } //p是f的左子树，则把p的右子树放到f的左子树 else if(f->lChild == p) { f->lChild = p->rChild; } //p是f的右子树，则把p的右子树放到f的右子树 else { f->rChild = p->rChild; } //删除P free(p); } //p有左子树 else { q = p; s = p->lChild; //在p的左子树中查找最右下的结点 while(s->rChild) { q = s; s = s->rChild; } //将s的左子树链到q上 if(q == p) { q->lChild = s->lChild; } else { q->rChild = s->lChild; } //将s的值赋给p p->val = s->val; free(s); } return root; } |
最后是二叉排序树的应用：对于经常做插入、删除、查找运算的表，宜采用二叉排序树结构。
中序遍历：递增有序。逆中序遍历：递减有序。
然后附上我全部的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
#include<iostream> #include<cstdio> using namespace std; typedef int KeyType; typedef struct Node{ KeyType val; struct Node *lChild; struct Node *rChild; }BSTNode, *BSTree; bool InsertBST(BSTree &root, KeyType key) { if(NULL == root) { root = new Node; root->val = key; root->lChild = root->rChild = NULL; return true; } if(key == root->val)//理论上不重复 { return false; } else if(key < root->val) { return InsertBST(root->lChild, key); } else { return InsertBST(root->rChild, key); } } void CreateBST(BSTree &root) { root = NULL;//不赋空值就是野指针... KeyType temp; while(scanf("%d",&temp) && (temp != -1)) { InsertBST(root, temp); } } BSTree SearchBST(BSTree root, KeyType key) { if(NULL == root) return root; if(root->val == key) { return root; } else if(key < root->val) { return SearchBST(root->lChild,key); } else { return SearchBST(root->rChild,key); } } BSTree DeleteBST(BSTree root, KeyType key) { BSTree p = NULL; BSTree f = NULL; BSTree s = NULL; BSTree q = NULL; p = root; //查找关键字为Key的待删除节点 while(p) { if(p->val == key)break; f = p; if(p->val > key) { p = p->lChild; } else { p = p->rChild; } } //如果找不到，返回原来的二叉树？ if(NULL == p) return root; //如果p没有左子树 if(NULL == p->lChild) { //p是原二叉树的根 if(NULL == f) { root = p->rChild; } //p是f的左子树，则把p的右子树放到f的左子树 else if(f->lChild == p) { f->lChild = p->rChild; } //p是f的右子树，则把p的右子树放到f的右子树 else { f->rChild = p->rChild; } //删除P free(p); } //p有左子树 else { q = p; s = p->lChild; //在p的左子树中查找最右下的结点 while(s->rChild) { q = s; s = s->rChild; } //将s的左子树链到q上 if(q == p) { q->lChild = s->lChild; } else { q->rChild = s->lChild; } //将s的值赋给p p->val = s->val; free(s); } return root; } int main() { BSTree BST; CreateBST(BST); BSTree ans = SearchBST(BST,10); if(ans != NULL) { cout << ans->val << endl; } else { cout << "Not Exist" << endl; } DeleteBST(BST,10); ans = SearchBST(BST,10); if(ans != NULL) { cout << ans->val << endl; } else { cout << "Not Exist" << endl; } } |
如有疑问，请留言.From TK-Xiong