BST二叉搜索树

二叉树:是一种特殊的树，二叉树的每个节点最多只能有2个子节点。如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：
1.左子树上的所有节点值均小于根节点值
2右子树上的所有节点值均不小于根节点值
3左右子树也满足上述两个条件

二叉搜索树通常有搜索，插入，删除，寻找最大最小节点等操作。
搜索：
在搜索元素x的时候，我们可以将x和根节点比较:

1. 如果x等于根节点，那么找到x，停止搜索 (终止条件)
2. 如果x小于根节点，那么搜索左子树
3. 如果x大于根节点，那么搜索右子树
   二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n，最少为log(n)
   二叉搜索树通常有搜索，插入，删除，寻找最大最小节点等操作。
   插入：
   1.若当前的二叉查找树为空，则插入的元素为根节点
   2.若插入的元素值小于根节点值，则将元素插入到左子树中
   3.若插入的元素值不小于根节点值，则将元素插入到右子树中。

删除：
对于二叉查找树的删除操作（这里根据值删除，而非结点）分三种情况：不过在此之前，我们应该确保根据给定的值找到了要删除的结点，如若没找到该结点不会执行删除操作！下面三种情况假设已经找到了要删除的结点。
1、如果结点为叶子结点（没有左、右子树），此时删除该结点不会破化树的结构直接删除即可，并修改其父结点指向它的引用为null.
如下图:
2、如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。

3、 当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据（容易找到）代替要删除的结点数据并递归删除该结点（此时为null），因为右子树的最小结点不可能有左孩子（因为左孩子比他大，它就不是最小数据了），所以第二次删除较为容易。
z的左子树和右子树均不空。找到z的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替z的值.
注：右子树最小数据，要么找到的是节点带给右节点(因为右节点比它父节点大)，如下图，把5那个节点删掉，不能直接把12节点带的子树顶替5节点的位置，这样就破坏力BST的结构，所有在要删除节点的右子树种找个最小值

z既有一个左孩子节点，又有一个右孩子节点
此时应该查找z的后继节点y，并用y来替换z。在上面已经介绍过，后继节点y一定在z的右子树里，且y没有左孩子。

此时又要分2种情况：
1）y是z的右孩子
此时应该用y替换z，并留下y的右子树。如下图

2）y不是z的右孩子，就是孙子辈的
此时应该先用y的右孩子替换y，然后再用y来替换z。如下图

完整代码：

#include
#include
#include
#define SIZE(a) ((sizeof(a)) / sizeof(a[0])) 
using namespace std;
static int arr[] = { 1,5,4,3,2,6 };
typedef int Type;  //只要修改此处，节点数据类型就改变了
typedef struct BST_Node {Type key;struct BST_Node *lchild;struct BST_Node *rchild;struct BST_Node *parent;
}Node, *BSTree;
void PreOrderTraverse(BSTree);//先序遍历 
void InOrderTraverse(BSTree);//中序遍历
void PostOrderTraverse(BSTree);//后序遍历
void bst_Destory(BSTree x);//从内存释放节点
void bst_Print(BSTree, Type, int);//输出整棵BST树
BSTree bst_Search(BSTree, Type);//递归查找 
BSTree bst_Search_iterative(BSTree, Type);//用循环查找
BSTree bst_minimum(BSTree);//找最小值
BSTree bst_maximum(BSTree);//找最大值
BSTree bst_pred(BSTree x);//找x的前驱节点
BSTree bst_succ(BSTree x);//找x的后继节点
BSTree bst_Delete(BSTree, Type);//删除节点 
BSTree bst_Insert(BSTree, Type);//插入
void PreOrderTraverse(BSTree T) {if (T) {cout << T->key;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}
void InOrderTraverse(BSTree T) {if (T) {InOrderTraverse(T->lchild);cout << T->key;InOrderTraverse(T->rchild);}
}
void PostOrderTraverse(BSTree T) {if (T) {PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout << T->key;}
}
//Search by recursion
BSTree bst_Search(BSTree T, Type key) {if (T == NULL || T->key == key)return T;if (key < T->key)return bst_Search(T->lchild, key);elsereturn bst_Search(T->rchild, key);
}
BSTree bst_Search_iterative(BSTree T, Type key) {while (T && T->key != key) {if (key < T->key) T = T->lchild;else T = T->rchild;}return T;
}
BSTree bst_minimum(BSTree T) {//搜索最小的只要在左子树找就可以if (!T) return NULL;while (T->lchild != NULL) T = T->lchild;return T;
}
BSTree bst_maximum(BSTree T) {//搜索最大的只要在右子树搜索就可以if (!T) return NULL;while (T->rchild != NULL) T = T->rchild;return T;
}
// 结点的后继结点等价于寻找BST中key大于该结点的最小结点
BSTree bst_succ(BSTree T) {// 若x存在右孩子，则x的后继结点为以其右孩子为根的子树的最小结点if (T->rchild)return bst_minimum(T->rchild);/*若节点没有右孩子 则有两种可能1:T为其父节点的左孩子，则其后继节点为其父亲2：T为其父节点的右孩子，则寻找其父节点的父节点*/BSTree P = T->parent;//while (P && (T == P->rchild)) {//2T = P;P = P->parent;}return P;
}
//节点的前驱和后继恰好相反
BSTree bst_pred(BSTree T) {if (T->lchild) return bst_maximum(T->lchild);BSTree P = T->parent;while ((P) && (T == P->lchild)) {T = P;P = P->parent;}return P;
}
static BSTree Create_BSTreeNode(Type key, BSTree parent, BSTree lchild, BSTree rchild) {BSTree t;if ((t = (Node *)malloc(sizeof(Node))) == NULL) return NULL;t->key = key;t->lchild = lchild;t->rchild = rchild;t->parent = parent;return t;
}
static BSTree Insert(BSTree T, BSTree  NODE) {BSTree X = T;BSTree Y = NULL;while (X) {Y = X;if (NODE->key < X->key)X = X->lchild;elseX = X->rchild;
}NODE->parent = Y;if (Y == NULL) T = NODE;else if (NODE->key < Y->key)Y->lchild = NODE;else Y->rchild = NODE;return T;
}
BSTree bst_Insert(BSTree T, Type key) {BSTree NODE;if ((NODE = Create_BSTreeNode(key, NULL, NULL, NULL)) == NULL) return T;return Insert(T, NODE);
}
static BSTree Delete(BSTree T, BSTree NODE) {BSTree X = NULL;   BSTree Y = NULL; //把要删除的节点保留到Y中 //删除节点只有左子树或只有右子树或是叶子节点（左右都没有）if ((NODE->lchild == NULL) || (NODE->rchild == NULL)) Y = NODE;else Y = bst_succ(NODE);//要删除节点既有左子树又有右子树，找后继节点 if (Y->lchild) X = Y->lchild;//判断是只有左子树还是右子树 else  X = Y->rchild;if (X) X->parent = Y->parent;/*X的父变成Y的父，相当于把Y先给取下来 Y的子树替代Y的位置*/ /*下一步决定Y的子树X是当成左子树还是右子树*/ if (!Y->parent) T = X; /*Y的父正好是根节点 ，把y的子树直接连到根上 X代表Y的子树，如果Y没有子树只不过X是NULL*/ else if (Y->parent->lchild==Y) Y->parent->lchild = X;else Y->parent->rchild = X;
/*Y->parent->lchild==Y表面Y是它父亲的左子树，所以就把Y的子树接到父节点的左子树上，否则，接到右子树上*/ if (Y != NODE) NODE->key = Y->key;/*如果Y！=NODE表示Y不是要删除节点的右孩子，而是孙子倍的，需要把y->key最后送给要删除的NODE->key*/ if (Y) free(Y);return T;
}
BSTree bst_Delete(BSTree T, Type key) {BSTree NODE;if ((NODE = bst_Search(T, key)) != NULL) T = Delete(T, NODE);return T;
}
void bst_Destory(BSTree T) {if (!T)return;if (T->lchild) bst_Destory(T->lchild);if (T->rchild) bst_Destory(T->rchild);free(T);
}
void bst_Print(BSTree T, Type key, int Direction) {if (T) {if (Direction == 0) cout << "root is " << T->key<<endl;else cout <<T->key<<" is "<<key<<" "<< Direction << " child"<<endl;bst_Print(T->lchild, T->key, -1);bst_Print(T->rchild, T->key, 1); }
}
int main() {int i, len;BSTree root = NULL;for(int i=0;i<6;i++)root=bst_Insert(root,arr[i]);PostOrderTraverse(root);  cout << "\nmax value is " << bst_maximum((root))->key << endl;cout << "\nmin value is " << bst_minimum((root))->key << endl;cout << "\nTraverse BST \n";bst_Print(root, root->key, 0);cout << "\nDelete root  " << arr[3];root = bst_Delete(root, arr[3]);cout<<endl;PostOrderTraverse(root);return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！