二叉查找树

一、二叉查找树的定义

定义：二叉查找树(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）。

二、二叉查找树的C实现

1. 节点定义 1.1 节点定义

typedef int Type; typedef struct BSTreeNode{ Type key; // 关键字(键值) struct BSTreeNode *left; // 左孩子 struct BSTreeNode *right; // 右孩子 struct BSTreeNode *parent; // 父结点 }Node, *BSTree;

二叉查找树的节点包含的基本信息： (1) key – 它是关键字，是用来对二叉查找树的节点进行排序的。 (2) left – 它指向当前节点的左孩子。 (3) right – 它指向当前节点的右孩子。 (4) parent – 它指向当前节点的父结点。

1.2 创建节点

static Node* create_bstree_node(Type key, Node *parent, Node *left, Node* right) { Node* p; if ((p = (Node *)malloc(sizeof(Node))) == NULL) return NULL; p->key = key; p->left = left; p->right = right; p->parent = parent; return p; }

2 遍历 2.1 前序遍历

若二叉树非空，则执行以下操作： (01) 访问根结点； (02) 先序遍历左子树； (03) 先序遍历右子树。

前序遍历代码

void preorder_bstree(BSTree tree) { if(tree != NULL) { printf("%d ", tree->key); preorder_bstree(tree->left); preorder_bstree(tree->right); } }

2.2 中序遍历

若二叉树非空，则执行以下操作： (01) 中序遍历左子树； (02) 访问根结点； (03) 中序遍历右子树。

中序遍历代码

void inorder_bstree(BSTree tree) { if(tree != NULL) { inorder_bstree(tree->left); printf("%d ", tree->key); inorder_bstree(tree->right); } }

2.3 后序遍历

若二叉树非空，则执行以下操作： (01) 后序遍历左子树； (02) 后序遍历右子树； (03) 访问根结点。

后序遍历代码

void postorder_bstree(BSTree tree) { if(tree != NULL) { postorder_bstree(tree->left); postorder_bstree(tree->right); printf("%d ", tree->key); } }

通过以下例子介绍这些遍历方法 对于上面的二叉树而言， (01) 前序遍历结果： 3 1 2 5 4 6 (02) 中序遍历结果： 1 2 3 4 5 6 (03) 后序遍历结果： 2 1 4 6 5 3

注意：二叉搜索树的 中序遍历是有序的

3. 查找 递归版本的代码

Node* bstree_search(BSTree x, Type key) { if (x==NULL || x->key==key) return x; if (key < x->key) return bstree_search(x->left, key); else return bstree_search(x->right, key); }

非递归版本的代码

Node* iterative_bstree_search(BSTree x, Type key) { while ((x!=NULL) && (x->key!=key)) { if (key < x->key) x = x->left; else x = x->right; } return x; }

4.最大值和最小值

查找最大值的代码

Node* bstree_maximum(BSTree tree) { if (tree == NULL) return NULL; while(tree->right != NULL) tree = tree->right; return tree; }

查找最小值代码

Node* bstree_minimun(BSTree tree) { if(tree!=NULL) return NULL; while(tree->left!=NULL) tree=tree->left; return tree; }

5.前驱和后继 节点的前驱：是该节点的左子树中的最大节点。 节点的后继：是该节点的右子树中的最小节点。 查找前驱节点的代码

Node* bstree_predecessor(Node *x) { // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x->left != NULL) return bstree_maximum(x->left); // 如果x没有左孩子。则x有以下两种可能： // (1) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (2) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找 //到的这个"最低的父结点"就是"x的前驱结点"。 Node* y = x->parent; while ((y!=NULL) && (x==y->left)) { x = y; y = y->parent; } return y; }

查找后继节点的代码

Node* bstree_successor(Node *x) { // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。 if (x->right != NULL) return bstree_minimum(x->right); // 如果x没有右孩子。则x有以下两种可能： // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 Node* y = x->parent; while ((y!=NULL) && (x==y->right)) { x = y; y = y->parent; } return y; }

6.插入

插入节点的代码

static Node* bstree_insert(BSTree tree, Node *z) { Node *y = NULL; Node *x = tree; // 查找z的插入位置 while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y==NULL) tree = z; else if (z->key < y->key) y->left = z; else y->right = z; return tree; } Node* insert_bstree(BSTree tree, Type key) { Node *z; // 新建结点 // 如果新建结点失败，则返回。 if ((z=create_bstree_node(key, NULL, NULL, NULL)) == NULL) return tree; return bstree_insert(tree, z); }

bstree_insert(tree, z)是内部函数，它的作用是：将结点(z)插入到二叉树(tree)中，并返回插入节点后的根节点。 insert_bstree(tree, key)是对外接口，它的作用是：在树中新增节点，key是节点的值；并返回插入节点后的根节点。

注：本文实现的二叉查找树是允许插入相同键值的节点的！若用户不希望插入相同键值的节点，将bstree_insert()修改为以下代码即可。

static Node* bstree_insert(BSTree tree, Node *z) { Node *y = NULL; Node *x = tree; // 查找z的插入位置 while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else if (z->key > x->key) x = x->right; else { free(z); // 释放之前分配的系统。 return tree; } } z->parent = y; if (y==NULL) tree = z; else if (z->key < y->key) y->left = z; else y->right = z; return tree; }

7.删除 删除某个结点后依然要保持二叉查找树的特性。例子中的删除过程如下：

a、若删除点是叶子结点，则设置其双亲结点的指针为空。 b、若删除点只有左子树，或只有右子树，则设置其双亲结点的指针指向左子树或右子树。 c、若删除点的左右子树均不为空，则： 1）、查询删除点的右子树的左子树是否为空，若为空，则把删除点的右子树替换删除点 2）、若不为空，则继续查询左子树，直到找到最底层的左子树为止。

删除节点的代码

static Node* bstree_delete(BSTree tree, Node *z) { Node *x=NULL; Node *y=NULL; //z节点如果只有一个孩子或者没有孩子，直接删除让y=z if ((z->left == NULL) || (z->right == NULL) ) y = z; //如果有两个孩子，找到z的后继节点 else y = bstree_successor(z); //后继节点肯定是没有左孩子的 x = y->right; //后继节点的有右孩子，让右孩子移到y的位置 if (x != NULL) x->parent = y->parent; if (y->parent == NULL) tree = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; if (y != z) z->key = y->key; if (y!=NULL) free(y); return tree; } Node* delete_bstree(BSTree tree, Type key) { Node *z, *node; if ((z = bstree_search(tree, key)) != NULL) tree = bstree_delete(tree, z); return tree; }