二叉排序树 ( Binary Sort Tree ) 又称 二叉查找树 ( Binary Search Tree )。
它或者是一棵空树，或者是具有下列性质的二叉树：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
3. 它的左、右子树也分别为二叉排序树
二叉排序树的查找算法
在二叉排序树 T 中查找 V 的过程为：
1. 若 T 是空树，则搜索失败
2. 若 V 等于 T 的根节点的数据域之值，则查找成功
3. 若 V 小于 T 的根节点的数据域之值，则搜索 T 的左子树，否则查找 T 的右子树
二叉排序树查找算法代码片段
//查找结点
//如果找不到,see 指向最后一个结点,并返回false; 如果找到,see 指向该结点,并返回true
bool search(Tree root, TNode parent, TNode &see, Element key){
if(!root){
see = parent;
return false;
}
if(root->data == key){
see = root;
return true;
}
if(root->data > key){
return search(root->lchild, root, see, key);
}else{
return search(root->rchild, root, see, key);
}
}
//重载函数
//如果找不到,则返回NULL; 如果找到,则返回该结点
TNode search(Tree root, TNode parent, Element key){
if(!root){
return NULL;
}
if(root->data == key){
return root;
}
if(root->data > key){
return search(root->lchild, root, key);
}else{
return search(root->rchild, root, key);
}
}
//重载函数
TNode search(Tree root, Element e){
return search(root, NULL, e);
}
二叉排序树插入结点的算法
向一个二叉查找树 T 中插入一个结点 S 的过程为：
1. 若 T 是空树，则将 S 所指结点作为根结点插入
2. 若 S 的数据域的值等于 T 的根结点的数据域之值，说明该结点已经存在，不进行插入操作
3. 若 S 的数据域的值小于 T 的根结点的数据域之值，则把 S 所指结点插入到左子树中，否则插入到右子树中
二叉排序树插入结点的算法代码片段
//二叉排序树插入结点
bool insertNode(Tree &root, Element e){
TNode parent;
bool isFound = search(root, NULL, parent, e); //查找该结点
if(isFound){ //已经存在
printf("该结点已经存在,插入操作失败!");
return false;
}
TNode node = (TNode)malloc(sizeof(Node));
node->data = e;
node->lchild = node->rchild = NULL;
if(!parent){ //空树
root = node;
}else{
if(parent->data > e){
parent->lchild = node;
}else{
parent->rchild = node;
}
}
return true;
}
二叉排序树删除结点的算法
分三种情况讨论：
1. 若 *current 结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可
2. 若 *current 结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点 *cparent 的左子树（当 *current 是左子树）
或右子树（当 *current 是右子树）即可，作此修改也不破坏二叉排序树的特性
3. 若 *current 结点的左子树和右子树均不空。在删去 *current 之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，
可以有两种做法：
其一是令 *current 的左子树为 *cparent 的左/右(依 *current 是 *cparent 的左子树还是右子树而定)子树，
*precursor 为 *current 左子树的最右下的结点，而 *current 的右子树为 *precursor 的右子树
其二是令 *current 的直接前驱（或直接后继）替代 *current ，然后再从二叉排序树中删去它的直接前驱（或直接后继）
二叉排序树删除结点的算法代码片段
//删除二叉排序树结点
void deleteNode(Tree &root, Element key){
Node *current, *cparent, *del;
current = root; //当前结点
cparent = NULL; //当前结点的双亲结点
del = NULL; //删除的结点
while(current && current->data != key){ //查找被删除的结点,可直接调用上面的search函数
cparent = current;
if(current->data > key){
current = current->lchild;
}else{
current = current->rchild;
}
}
if(!current){ //没找到
printf("删除的结点不存在!");
return ;
}
del = current; //找到了
if(!current->lchild){ //被删结点无左子树,重接右子树
if(current == cparent->lchild)
cparent->lchild = current->rchild;
else
cparent->rchild = current->rchild;
}else if(!current->rchild){ //被删结点无右子树,重接左子树
if(current == cparent->lchild)
cparent->lchild = current->lchild;
else
cparent->rchild = current->lchild;
}else{ //被删结点同时存在左子树和右子树
Node *precursor, *parent;
precursor = current->lchild; //被删结点的直接前驱结点
parent = current; //前驱结点的双亲结点
while(precursor->rchild){ //查找前驱结点(中序遍历到最后)
parent = precursor;
precursor = precursor->rchild;
}
current->data = precursor->data; //前驱结点替换被删结点
if(parent != current){ //重接右子树
parent->rchild = precursor->lchild;
}else{ //重接左子树
parent->lchild = precursor->lchild;
}
del = precursor;
}
free(del); //释放被删结点内存空间
}
完整代码:
/**
* <!--
* File : binarysorttree.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-04
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Element char
#define format "%c"
typedef struct Node {
Element data;
struct Node *lchild;
struct Node *rchild;
} *Tree, *TNode;
int index = 0; //全局索引变量
//二叉树构造器,按先序遍历顺序构造二叉树
//无左子树或右子树用'#'表示
void treeNodeConstructor(Tree &root, Element data[]){
Element e = data[index++];
if(e == '#'){
root = NULL;
}else{
root = (Node *)malloc(sizeof(Node));
root->data = e;
treeNodeConstructor(root->lchild, data);
treeNodeConstructor(root->rchild, data);
}
}
//查找结点
//如果找不到,see 指向最后一个结点,并返回false; 如果找到,see 指向该结点,并返回true
bool search(Tree root, TNode parent, TNode &see, Element key){
if(!root){
see = parent;
return false;
}
if(root->data == key){
see = root;
return true;
}
if(root->data > key){
return search(root->lchild, root, see, key);
}else{
return search(root->rchild, root, see, key);
}
}
//重载函数
//如果找不到,则返回NULL; 如果找到,则返回该结点
TNode search(Tree root, TNode parent, Element key){
if(!root){
return NULL;
}
if(root->data == key){
return root;
}
if(root->data > key){
return search(root->lchild, root, key);
}else{
return search(root->rchild, root, key);
}
}
//重载函数
TNode search(Tree root, Element e){
return search(root, NULL, e);
}
//删除二叉排序树结点
void deleteNode(Tree &root, Element key){
Node *current, *cparent, *del;
current = root; //当前结点
cparent = NULL; //当前结点的双亲结点
del = NULL; //删除的结点
while(current && current->data != key){ //查找被删除的结点,可直接调用上面的search函数
cparent = current;
if(current->data > key){
current = current->lchild;
}else{
current = current->rchild;
}
}
if(!current){ //没找到
printf("删除的结点不存在!");
return ;
}
del = current; //找到了
if(!current->lchild){ //被删结点无左子树,重接右子树
if(current == cparent->lchild)
cparent->lchild = current->rchild;
else
cparent->rchild = current->rchild;
}else if(!current->rchild){ //被删结点无右子树,重接左子树
if(current == cparent->lchild)
cparent->lchild = current->lchild;
else
cparent->rchild = current->lchild;
}else{ //被删结点同时存在左子树和右子树
Node *precursor, *parent;
precursor = current->lchild; //被删结点的直接前驱结点
parent = current; //前驱结点的双亲结点
while(precursor->rchild){ //查找前驱结点(中序遍历到最后)
parent = precursor;
precursor = precursor->rchild;
}
current->data = precursor->data; //前驱结点替换被删结点
if(parent != current){ //重接右子树
parent->rchild = precursor->lchild;
}else{ //重接左子树
parent->lchild = precursor->lchild;
}
del = precursor;
}
free(del); //释放被删结点内存空间
}
//二叉排序树插入结点
bool insertNode(Tree &root, Element e){
TNode parent;
bool isFound = search(root, NULL, parent, e); //查找该结点
if(isFound){ //已经存在
printf("该结点已经存在,插入操作失败!");
return false;
}
TNode node = (TNode)malloc(sizeof(Node));
node->data = e;
node->lchild = node->rchild = NULL;
if(!parent){ //空树
root = node;
}else{
if(parent->data > e){
parent->lchild = node;
}else{
parent->rchild = node;
}
}
return true;
}
//先序遍历
void preorderTraversal(Tree root){
if(root){
printf(format, root->data);
preorderTraversal(root->lchild);
preorderTraversal(root->rchild);
}
}
//中序遍历二叉树
void inorderTraversal(Tree root){
if(root){
inorderTraversal(root->lchild);
printf(format, root->data);
inorderTraversal(root->rchild);
}
}
//后序遍历二叉树
void postorderTraversal(Tree root){
if(root){
postorderTraversal(root->lchild);
postorderTraversal(root->rchild);
printf(format, root->data);
}
}
/**
* <!--
* File : BinarySortTree.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-04
* --!>
*/
#include "binarysorttree.h"
int main() {
//上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树
Element data[27] = {'M', 'J', 'E', 'C', '#', '#', 'G', 'F', '#', '#', 'I', 'H',
'#','#', '#', 'L', '#', '#', 'R', 'P', '#', '#', 'S', '#', 'T', '#', '#'};
Tree tree;
treeNodeConstructor(tree, data);
printf("先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
//TEST 搜索
TNode node = search(tree, 'F');
if(node){
printf("Found it : %c\n", node->data);
}else{
printf("NOT FOUND\n");
}
//TEST 插入结点
insertNode(tree, 'K');
printf("插入K结点后,先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
//TEST 删除无左右子树的结点
deleteNode(tree, 'P');
printf("删除P结点后,先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
//TEST 删除无左子树的结点
deleteNode(tree, 'S');
printf("删除S结点后,先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
//TEST 删除无右子树的结点
deleteNode(tree, 'I');
printf("删除I结点后,先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
//TEST 删除有左右子树的结点
deleteNode(tree, 'J');
printf("删除J结点后,先序遍历结果: ");
preorderTraversal(tree);
printf("\n");
/**
* 控制台输出结果:
*
* 先序遍历结果: MJECGFIHLRPST
* Found it : F
* 插入K结点后,先序遍历结果: MJECGFIHLKRPST
* 删除P结点后,先序遍历结果: MJECGFIHLKRST
* 删除S结点后,先序遍历结果: MJECGFIHLKRT
* 删除I结点后,先序遍历结果: MJECGFHLKRT
* 删除J结点后,先序遍历结果: MHECGFLKRT
*/
return 0;
}
posted on 2013-02-04 10:21
fancydeepin 阅读(1839)
评论(0) 编辑 收藏