二叉排序树的删除操作

算法思想

二叉排序树,删除操作主要针对三种情况。

1 叶子节点-直接删除就可以了

2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树就可以了)

3 如果左右子树都存在,则寻找删除节点的直接前驱(即左子树里面的最右的节点)

编程时需要注意,函数时针对指针的操作,因此为了修改指针,要使用二级指针传参才可以

例如:

void delete(BinaryTree **b){

  ....

}

int main(){

  BinaryTree *b = (BinaryTree *)malloc(sizeof(BinaryTree));

  delete(&b);

}

函数代码:

bool deleteTree(BTree **b,int key){
    if(!*b)
        return false;
    else{
        if((*b)->data == key){
            return deleteNode(&(*b));
        }
        else if((*b)->data > key)
            return deleteTree(&(*b)->lchild,key);
        else
            return deleteTree(&(*b)->rchild,key);
    }
}
bool deleteNode(BTree **b){
    BTree *p,*s;
    if((*b)->lchild == NULL ){
        p = (*b);
        (*b) = (*b)->rchild;
        free(p);
    }else if((*b)->rchild == NULL){
        p = (*b);
        (*b) = (*b)->lchild;
        free(p);
    }else{
        p = (*b);
        s = (*b)->lchild;
        while(s->rchild != NULL){
            p = s;
            s = s->rchild;
        }
        (*b)->data = s->data;
        if(p != (*b))
            p->rchild = s->lchild;
        else
            p->lchild = s->lchild;
        free(s);
        return true;
    }
}

全部代码:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 typedef struct bTree{
  4     int data;
  5     struct bTree *lchild,*rchild;
  6 }BTree;
  7 
  8 void initialTree(BTree *b);
  9 bool insertTree(BTree *b,int key);
 10 int searchTree(BTree *b,int key,BTree *f,BTree *&p);
 11 void InOrderTree(BTree *b);
 12 bool deleteTree(BTree **b,int key);
 13 bool deleteNode(BTree **b);
 14 
 15 int main(){
 16     BTree *b = (BTree *)malloc(sizeof(BTree));
 17     b->data = 5;
 18     b->lchild = b->rchild = NULL;
 19     initialTree(b);
 20     InOrderTree(b);
 21     deleteTree(&b,4);
 22     InOrderTree(b);
 23     getchar();
 24     return 0;
 25 }
 26 bool deleteTree(BTree **b,int key){
 27     if(!*b)
 28         return false;
 29     else{
 30         if((*b)->data == key){
 31             return deleteNode(&(*b));
 32         }
 33         else if((*b)->data > key)
 34             return deleteTree(&(*b)->lchild,key);
 35         else
 36             return deleteTree(&(*b)->rchild,key);
 37     }
 38 }
 39 bool deleteNode(BTree **b){
 40     BTree *p,*s;
 41     if((*b)->lchild == NULL ){
 42         p = (*b);
 43         (*b) = (*b)->rchild;
 44         free(p);
 45     }else if((*b)->rchild == NULL){
 46         p = (*b);
 47         (*b) = (*b)->lchild;
 48         free(p);
 49     }else{
 50         p = (*b);
 51         s = (*b)->lchild;
 52         while(s->rchild != NULL){
 53             p = s;
 54             s = s->rchild;
 55         }
 56         (*b)->data = s->data;
 57         if(p != (*b))
 58             p->rchild = s->lchild;
 59         else
 60             p->lchild = s->lchild;
 61         free(s);
 62         return true;
 63     }
 64 }
 65 void InOrderTree(BTree *b){
 66     if( !b )
 67         return;
 68     InOrderTree(b->lchild);
 69     printf("%d ",b->data);
 70     InOrderTree(b->rchild);
 71 }
 72 
 73 void initialTree(BTree *b){
 74     insertTree(b,5);
 75     insertTree(b,3);
 76     insertTree(b,4);
 77     insertTree(b,6);
 78     insertTree(b,2);
 79     insertTree(b,1);
 80     insertTree(b,8);
 81 }
 82 int searchTree(BTree *b,int key,BTree *f,BTree *&p){
 83     if(!b){
 84         p = f;
 85         printf("++%d\n",p->data);
 86         return 0;
 87     }
 88     else if( key == b->data){
 89         p = b;
 90         printf("--%d \n",p->data);
 91         printf("找到元素key:%d\n",key);
 92         return 1;
 93     }
 94     else if(key > b->data)
 95         return searchTree(b->rchild,key,b,p);
 96     else
 97         return searchTree(b->lchild,key,b,p);
 98 }
 99 bool insertTree(BTree *b,int key){
100     BTree *p,*s;
101     if(!searchTree(b,key,NULL,p)){
102         printf("%d 没有出现在树中,可以插入在%d之后\n",key,p->data);
103         s = (BTree *)malloc(sizeof(BTree));
104         s->data = key;
105         s->lchild = s->rchild = NULL;
106         if(!b){
107             b = s;
108         }
109         else if(key < p->data){
110             p->lchild = s;
111         }else{ 
112             p->rchild = s;
113         }
114         return true;
115     }else
116         return false;
117 }

运行示例:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2608
来自专栏kevindroid

leetcode257 Binary Tree Paths

1485
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

2016
来自专栏Micro_awake web

python二叉树递归算法之后序遍历,前序遍历,中序遍历

1 #!/usr/bin/env python 2 # -*- coding: utf-8 -*- 3 # @Date : 2016-11-18 0...

2465
来自专栏海天一树

二叉树的建立和遍历

二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

933
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

64611
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

7682
来自专栏吴伟祥

Java Calendar 类的时间操作 原

Calendar 的 month 从 0 开始,也就是全年 12 个月由 0 ~ 11 进行表示。

1233
来自专栏Android相关

二叉查找树(Binary Search Tree)

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜...

2563
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1834

扫码关注云+社区