随笔-126  评论-247  文章-5  trackbacks-0

          
二叉排序树 ( 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 阅读(1827) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: