首页 > 代码库 > 二叉搜索树
二叉搜索树
二叉搜索树
定义
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比，对于有n个结点的一棵完全二叉树来说，这些操作的最坏运行时间为Θ(lgn)，然而，如果这棵树是一条n个节点组成的线性链，那么同样的操作就要花费Θ(n)的最坏运行时间，一棵随机构造的二叉搜索树的期望高度为Ο(lgn)，因此这样一棵树上的动态集合的基本操作的平均运行时间为Θ(lgn)。
二叉搜索树的每个结点就是一个对象，除了key和卫星数据之外，每个结点还包含属性left, right和p，他们分别指向结点的左孩子，右孩子和双亲，如果某个孩子节点和父节点不存在，则相应属性的值为NIL，根结点是树中唯一父指针为NIL的结点。
在二叉搜索树中，对任何结点x，其左子树的关键字最大不超过x.key，其右子树的关键字最小不低于x.key。
遍历二叉搜索树
可以通过一个简单的递归算法来按序输出二叉搜索树中的所有关键字，例如中序遍历算法，先输出左子树的关键字的值，然后输出子树根的关键字，最后输出右子树的关键字的值。伪代码如下：
INORDER-TREE-WALK(x)ifx != NIL INORDER-TREE-WALK(x.left)print x.key INORDER-TREE-WALK(x.right)
查询二叉搜索树
定理：如果x是一棵有n个结点子树的根，那么调用INORDER-TREE-WALK(x)需要Θ(n)时间
查找某个关键字
使用下面的过程在一棵二叉树中查找一个具有给定关键字的结点，输入一个指向树根的指针和一个关键字k，如果这个结点存在，TREE-SEARCH返回一个指向关键字为k的结点的指针，否则返回NIL
递归版本TREE-SEARCH(x, k)if x == NIL or k == x.keyreturn xif k < x.keyreturn TREE-SEARCH(x. left, k)elsereturn TREE-SEARCH(x.right, k)
循环版本（效率更高）ITERATIVER-TREE-SEARCH(x, k) while x != NIL and k != x.key if k < x.key x = x.left else x = x.rightreturn x
查找最大最小值
查找最小值TREE-MINIMUM(x) while x.left != NIL x = x.leftreturn x
查找最大值TREE-MAXIMUM(x) while x.right != NIL x = x.rightreturn x
查找后继和前驱
给定一棵二叉搜索树中的一个结点，按照中序遍历的次序查找它的后继结点，如果所有的关键字都不相同，则一个节点的x的后继是大于x.key的最小关键字的结点。此时分两种情况：第一种是如果结点x的右子树非空，那么x的后继结点就是x的右子树中的最小的结点。第二种情况是x没有右子树，并且有一个后继结点y，那么从x开始沿树向上查找，直到遇到一个把x作为左孩子子树的结点。
查找后继结点TREE-SUCCESSOR(x) if x.right != NIL return TREE-MINIMUM(x.right) y = x.p while y != NIL and x == y.right x = y y = y.preturn y
查找前驱结点也分两种情况：第一种是x有左子树，此时x的前驱结点就是左子树的最大值。第二种情况是x没有左子树，那么从x开始沿树向上查找，直到找到一个把x作为右孩子子树的结点。
查找前驱结点Tree-PREDECESSOR(x) if x.left != NIL return Tree-MAXIMUM(x.left) y = x.p while y != NIL and x == y.left x = y y = y.preturn y
在一棵高度为h的树上，上面两个程序的运行时间都为Ο(h)，因为该过程或者遵循从一条简单路径沿树而上，或者沿树而下。
定理：在一棵高度为h的二叉搜索树上，动态集合上的操作SEARCH, MINIMUM, MAXIMUM, SUCCESSOR和PREDECESSOR, INSERT, DELETE可以在Ο(h)时间内完成。
插入和删除
插入和删除会引起二叉搜索树的动态集合的变化，一定要修改数据结构来反映这个变化，插入一个新结点带来的树修改相对简单，而删除的处理有些复杂。
插入
从树根开始，指针x记录一条向下的简单路径，并查找要替换的输入项z的NIL，该过程保持遍历指针y作为x的双亲，直到x变为NIL，这个NIL占据的位置就是输入项z要放置的地方。
TREE-INSERT(T, z) y = NIL x = T.root while x != NIL y = x if z.key < x.key y = y.left else y = y.right z.p = y if y == NIL T.root = z //原来的树为空 elseif z.key < y.key y.left = z else y.right = z
删除
从一棵二叉搜索树T中删除一个结点z的整个策略分为三个基本情况，但只有一种情况比较复杂
如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点，用NIL作为孩子来替换z
如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，并修改z的父结点，用z的孩子来替换z
如果z有两个孩子，那么找z的后继y（一定要在z的右子树中），并让y占据树中z的位置，z的原来右子树部分称为y的新的右子树，并且z的左子树称为y的新的左子树，这种情况如下所述，因为还与y是否为z的右孩子相关。（也就是说：2.如果后继结点为z的直接右孩子，此时把后继结点直接替换z结点；3.如果后继结点不是z的直接右孩子，就把后继结点换到直接右孩子的位置上，再替换z结点）
（对上图的解释）从一棵二叉搜索树中删除结点z，结点z可以是树根，可以是结点q的一个左孩子，也可以是q的一个右孩子。（a）结点z没有左孩子，用其右孩子r来替换z，其中r可以是NIL，也可以不是。（b）结点z有一个左孩子l但没有右孩子，用l来替换z。（c）结点z有两个孩子，其左孩子是结点l，右孩子y还是其后继，y的右孩子是结点x，用y替换z，修改使l成为y的左孩子，但保留x仍为y的右孩子。（d）结点z有两个孩子（左孩子l和右孩子r），并且z的后继y != r位于以r为根的子树中，用y自己的右孩子x来替换y，并且置y为r的双亲，然后，再置y为q的孩子和l的双亲。
//用一棵以v为根的子树来替换一棵以u为根的子树，注意该过程并没有处理v.left和v.right的更新，这些操作由调用者来负责TRANSPLANT(T, u, v) if u.p == NIL T.root = v elseif u == u.p.left u.p.left = v else u.p.right = v if v != NIL v.p = u.p
//从二叉搜索树T中删除结点zTREE-DELETE(T, z) if z.left == NIL TRANSPLANT(T, z, z.right) elseif z.right == NIL TRANSPLANT(T, z, z.left) else y = TREE-MINIMUM(z.right) if y.p != z TRANSPLANT(T, y, y.right) y.right = z.right y.right.p = y TRANSPLANT(T, z, y) y.left = z.left y.left.p = y
C代码实现(二叉搜索树的基本操作)
#include<stdio.h>#include<stdlib.h> #define NUM 7 typedef struct node{ int element; struct node *left; struct node *right; struct node *parent;} TreeNode; TreeNode *CreateTree(TreeNode *root, int *array);TreeNode *Insert(int element, TreeNode *treenode);void PreorderTravel(TreeNode *root);void MidorderTravel(TreeNode *root);TreeNode *FindMin(TreeNode *treenode);TreeNode *FindMax(TreeNode *treenode);TreeNode *FindNode(int element, TreeNode *root);TreeNode *Delete(int element, TreeNode *root); main(){ int i; int array[NUM] = { 12, 3, 43, 25, 31, 9, 14 }; TreeNode *root; root = NULL; printf("原始数组为：\n"); for (i = 0; i < NUM; i++) printf("%4d", array[i]); root = CreateTree(root, array); printf("\n中序遍历：\n"); MidorderTravel(root); printf("\n先序遍历：\n"); PreorderTravel(root); //删除结点值为12的结点 root = Delete(12, root); printf("\n中序遍历：\n"); MidorderTravel(root); printf("\n先序遍历：\n"); PreorderTravel(root); putchar(‘\n‘); putchar(‘\n‘);} TreeNode *CreateTree(TreeNode *root, int *array){ int i; for (i = 0; i < NUM; i++) root = Insert(array[i], root); return root;} TreeNode *Insert(int element, TreeNode *treenode){ if (treenode == NULL){ treenode = (TreeNode *) malloc (sizeof(TreeNode)); if (treenode == NULL) exit(EXIT_FAILURE); treenode->element = element; treenode->left = treenode->right = NULL; treenode->parent = NULL; } else if (element < treenode->element){ treenode->left = Insert(element, treenode->left); treenode->left->parent = treenode; } else if (element > treenode->element){ treenode->right = Insert(element, treenode->right); treenode->right->parent = treenode; } return treenode; } void PreorderTravel(TreeNode *root){ if (root != NULL){ printf("%4d", root->element); PreorderTravel(root->left); PreorderTravel(root->right); }} void MidorderTravel(TreeNode *root){ if (root != NULL){ MidorderTravel(root->left); printf("%4d", root->element); MidorderTravel(root->right); }} TreeNode *FindMin(TreeNode *treenode){ if (treenode != NULL){ while (treenode->left != NULL) treenode = treenode->left; } return treenode;} TreeNode *FindMax(TreeNode *treenode){ if (treenode != NULL){ while (treenode->right != NULL) treenode = treenode->right; } return treenode;} void Transparent(TreeNode *v, TreeNode *u){ //用子树u替换子树v，程序并没有更新u->left和u->right，需要调用者在程序中更新 if (v->parent != NULL){ //被替换的结点不是根结点 if (v == v->parent->left) v->parent->left = u; else if (v == v->parent->right) v->parent->right = u; if (u != NULL) u->parent = v->parent; } else { //这句语句非常重要 //当要被替换的结点为树的根结点时，此时只需要修改根结点的值为要替换的值即可，不需要改变树的结构 v->element = u->element; }} TreeNode *FindNode(int element, TreeNode *root){ if (root == NULL) return NULL; if (element < root->element) return FindNode(element, root->left); else if (element > root->element) return FindNode(element, root->right); else return root;} TreeNode *Delete(int element, TreeNode *root){ //tempnode指向要删除的结点，subsequent指向用来替换删除结点的后继结点 TreeNode *tempnode, *subsequent; tempnode = FindNode(element, root); printf("\n\n要删除的结点值为：%d",tempnode->element); if (tempnode->left == NULL) Transparent(tempnode, tempnode->right); else if (tempnode->right == NULL) Transparent(tempnode, tempnode->left); else { subsequent = FindMin(tempnode->right); printf("\n找到的后继结点值为：%d\n",subsequent->element); if (subsequent != tempnode->right){ Transparent(subsequent, subsequent->right); subsequent->right = tempnode->right; subsequent->right->parent = subsequent; } Transparent(tempnode, subsequent); subsequent->left = tempnode->left; subsequent->left->parent = subsequent; } return root;}
随机生成二叉搜索树
伪代码
Create-Random-Tree(T) //create a random array for i = 0 to NUM random = rand() % ARRANGE if temparray[random] != 1 //检查生成的随机数是否已经存在 array[i] = random temparray[random] = 1 Insert(T, array[i]) else i—
C代码实现（生成随机树）
#include<stdio.h>#include<stdlib.h>#include<time.h> #define NUM 15#define ARRANGE 50 struct node { int element; struct node *left; struct node *right;}; typedef struct node TreeNode; TreeNode *CreateTree(TreeNode *);TreeNode *Insert(int , TreeNode *);void PreorderTravel(TreeNode *);void MidorderTravel(TreeNode *); main(){ TreeNode *root; int i; root = NULL; printf("随机生成的数组：\n"); root = CreateTree(root); printf("\n先序遍历数组生成的树：\n"); PreorderTravel(root); printf("\n中序遍历生成的树：\n"); MidorderTravel(root); putchar(‘\n‘); putchar(‘\n‘);} TreeNode *CreateTree(TreeNode *root){ int temparray[ARRANGE] = {0}; int i, random; for (i = 0; i < NUM; i++){ srand((unsigned) time(NULL)); random = rand() % ARRANGE; if (temparray[random] == 0){ temparray[random] = 1; printf("%4d", random); root = Insert(random, root); } else { i--; } } return root;} TreeNode *Insert(int element, TreeNode *root){ if (root == NULL){ root = (TreeNode *) malloc (sizeof(TreeNode)); if (root == NULL) exit(EXIT_FAILURE); root->element = element; root->left = root->right = NULL; } else if (element < root->element){ root->left = Insert(element, root->left); } else if (element > root->element){ root->right = Insert(element, root->right); } return root;} void PreorderTravel(TreeNode *root){ //先序遍历 if (root != NULL){ printf("%4d", root->element); PreorderTravel(root->left); PreorderTravel(root->right); }} void MidorderTravel(TreeNode *root){ //中序遍历 if (root != NULL){ MidorderTravel(root->left); printf("%4d", root->element); MidorderTravel(root->right); }}