美文网首页
二叉搜索树的节点删除(c实现)

二叉搜索树的节点删除(c实现)

作者: pengtoxen | 来源:发表于2018-07-13 09:35 被阅读0次

BST节点删除的情况可以细分为6种情况

  1. 根节点的删除
    1.1 根节点没有左右孩子
    1.2 根节点只有左孩子
    1.3 根节点只有右孩子
    1.4 根节点有左右孩子
  2. 子节点的删除
    2.1 子节点没有左右孩子
    2.2 子节点只有左孩子
    2.3 子节点只有右孩子
    2.4 子节点有左右孩子

现在配合图例来分别描述这六种情况.

创建后的BST结构如下:


BST.png

1 根节点的删除

1.1 根节点没有左右孩子
很好理解,只有一个根节点,删除就好了
1.2 根节点只有左孩子
这种情况就是把根节点删除,把左孩子节点当做新的根节点

001.png
1.3 根节点只有右孩子同1.2
1.4 根节点有左右孩子(这里只考虑操作左子树的情况,右子树同理)
根据BST的特性,左子树的右叶子<根节点<右子树的左叶子,所以当删除根节点的时候,确保BST的特性,可以将
左子树的右叶子或者右子树的左叶子的值来代替根节点,并将该节点删除.
1.4.1 根节点的左孩子有左右子树
002.png
1.4.2 根节点的左孩子只有右子树(同1.4.1)
1.4.3 根节点的左孩子只有左子树
003.png
1.4.4 根节点的左右孩子都没有孩子(这里只考虑左子树的操作)
004.png

2 子节点的删除

2.1 子节点没有左右孩子
删除节点既可
2.2 子节点只有左孩子
这种情况与1.4.3的情况类似,只是不用交换节点值,将子节点指向子节点的左孩子既可
2.3 子节点只有右孩子
这种情况与2.3相同.只是操作右节点
2.4 子节点有左右孩子
2.4.1 要删除的子节点在根节点的左边
与1.4.1的请相同,例如我们如果要删除5节点


004.png
006.png

2.4.2 要删除的子节点在根节点的右边
与上面相同,只是操作右子树
2.4.3 要删除的子节点有左右两个孩子,但是左孩子没有右孩子
这种情况不满足2.4.1或者2.4.2的条件,需要特别考虑


007.png 008.png 
#include<stdio.h>
#include<stdlib.h>

typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} Node;

Node *newNode(int data);
Node *insert(Node *node, int data);
Node *getParent(Node *node, Node *parent, int target);
void printPreorder(Node *node);
void printInorder(Node *node);
void printPostorder(Node *node);
Node *lookup(Node *node, int target);
Node *leftLeaf(Node *node);
Node *rightLeaf(Node *node);
Node *delNode(Node *root, int target);

int main(void) {
    Node *root = newNode(10);
    /* following is the tree after above statement
            10
          /   \
         NULL  NULL
    */
    insert(root, 5);
    insert(root, 15);
    /* 2 and 3 become left and right children of 1
               10
             /   \
            5      15
         /    \    /  \
        NULL NULL NULL NULL
    */
    insert(root, 3);
    /* 4 becomes left child of 2
                  10
               /      \
              5        15
            /   \     /  \
           3   NULL NULL  NULL
          /  \
        NULL NULL
    */
    insert(root, 7);
    insert(root, 8);
    insert(root, 6);
    // insert(root, 4);
    insert(root, 2);
    insert(root, 20);
    /* 4 insert some node
                 10
               /    \
              5      15
            /   \      \
           3     7     20
          / \   / \
         2   4  6  8
    */
    delNode(root, 5);
    printf("\n");
    printf("preorder:");
    printPreorder(root);//前序遍历:10--5--3--2--4--7--6--8--20
    free(root);
    return 0;
}

//创建新节点
Node *newNode(int data) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
};

//插入节点
Node *insert(Node *node, int data) {
    // 1. If the tree is empty, return a new, single node
    if(node == NULL) {
        return newNode(data);
    }
    // 2. Otherwise, recur down the tree
    if(data < node->data) {
        node->left = insert(node->left, data);
    } else {
        node->right = insert(node->right, data);
    }
    //return the (unchanged) node pointer
    return node;
}

//获取指定值的父亲节点
Node *getParent(Node *node, Node *parent, int target) {
    if(node == NULL) {
        return NULL;
    }
    if(target == node->data) {
        return parent;
    }
    parent = node;
    if(target < node->data) {
        return getParent(node->left, parent, target);
    } else {
        return getParent(node->right, parent, target);
    }
}

//前序遍历
void printPreorder(Node *node) {
    if(node == NULL) {
        return;
    }
    printf("%d--", node->data);
    printPreorder(node->left);
    printPreorder(node->right);
}

//中序遍历
void printInorder(Node *node) {
    if(node == NULL) {
        return;
    }
    printInorder(node->left);
    printf("%d--", node->data);
    printInorder(node->right);
}

//后序遍历
void printPostorder(Node *node) {
    if (node == NULL) return;
    // first recur on both subtrees
    printPostorder(node->left);
    printPostorder(node->right);
    // then deal with the node
    printf("%d--", node->data);
}

//左叶子节点
Node *leftLeaf(Node *node) {
    if(node->left == NULL) {
        return node;
    }
    return leftLeaf(node->left);
}

//右叶子节点
Node *rightLeaf(Node *node) {
    if(node->right == NULL) {
        return node;
    }
    return rightLeaf(node->right);
}

//查找指定值的节点
Node *lookup(Node *node, int target) {
    if(node == NULL) {
        return NULL;
    }
    if(target == node->data) {
        return node;
    }
    if(target < node->data) {
        return lookup(node->left, target);
    } else {
        return lookup(node->right, target);
    }
}

//删除指定值的节点
Node *delNode(Node *root, int target) {
    Node *node = lookup(root, target);
    Node *ret = NULL;
    if(node == NULL) {
        return ret;
    }
    Node *parent = getParent(root, NULL, target);
    //根节点的情况
    if(parent == NULL) {
        //没有左右孩子
        if(node->left == NULL && node->right == NULL) {
            ret = NULL;
        }
        //只有左孩子
        if(node->left && node->right == NULL) {
            ret = node->left;
        }
        //只有右孩子
        if(node->right && node->left == NULL) {
            ret = node->right;
        }
        //有左右孩子
        if(node->left && node->right) {
            //左子树的最右边叶子节点
            Node *leaf = rightLeaf(node->left);
            //node->left没有右子树
            if(leaf == node->left) {
                node->data = leaf->data;
                node->left = leaf->left;
            } else {
                //找到叶子节点的父亲
                Node *leafParent = getParent(root, NULL, leaf->data);
                //交换叶子节点的值
                node->data = leaf->data;
                //叶子节点父亲就是操作节点
                if(leafParent == node) {
                    //删除左子树
                    leafParent->left = NULL;
                } else {
                    //删除右子树
                    leafParent->right = NULL;
                }
            }
            ret = node;
        }
    } else {
        //非根节点的情况
        //没有左右孩子
        if(node->left == NULL && node->right == NULL) {
            //节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
            if(node->data > parent->data) {
                parent->right = NULL;
            } else {
                parent->left = NULL;
            }
            ret = parent;
        }
        //只有左子树
        if(node->left && node->right == NULL) {
            //节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
            if(node->data > parent->data) {
                parent->right = node->left;
            } else {
                parent->left = node->left;
            }
            ret = parent;
        }
        //只有右子树
        if(node->right && node->left == NULL) {
            //节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
            if(node->data > parent->data) {
                parent->right = node->right;
            } else {
                parent->left = node->right;
            }
            ret = parent;
        }
        //有左右子树
        if(node->left && node->right) {
            //节点值>操作节点值,说明是父节点的右孩子.反之是父节点的左孩子
            if(node->data < parent->data) {
                Node *leaf = rightLeaf(node->left);
                Node *leafParent = getParent(root, NULL, leaf->data);
                node->data = leaf->data;
                //父亲节点就是操作节点
                if(leafParent == node) {
                    leafParent->left = leaf->left;
                } else {
                    leafParent->right = NULL;
                }
            } else {
                Node *leaf = leftLeaf(node->right);
                Node *leafParent = getParent(root, NULL, leaf->data);
                node->data = leaf->data;
                //父亲节点就是操作节点
                if(leafParent == node) {
                    leafParent->right = leaf->right;
                } else {
                    leafParent->left = NULL;
                }
            }
            ret = node;
        }
    }
    return ret;
}

上面细分了6种删除节点的情况,可以总结成3种情况
1.删除节点是叶子节点
2.删除节点有左/右子树
3.删除节点有左右子树(相当于找左子树的最大值或者右子树的最小值)

//找到左子树的最大值
Node* findMax(Node* node){
    return node->right ? findMax(node->right) : node;
}

//找到右子树的最小值
Node* findMin(Node* node){
    return node->left ? findMax(node->left) : node;
}

Node *delNode3(Node *tree, Node *target) {
    if(tree == NULL || target == NULL) {
        return NULL;
    }
    //要删除的节点在左子树,递归删除
    if(target->data < tree->data) {
        tree->left = delNode3(tree->left, target);
    //要删除的节点在右子树,递归删除
    } else if(target->data > tree->data) {
        tree->right = delNode3(tree->right, target);
    } else {
        //1.待删除的节点有左右子树
        if(tree->left && tree->right) {
            //找到左子树的最大值节点或者找到右子树的最小值节点
            Node *temp = findMax(tree->left);
            // Node *temp = findMin(tree->right);
            //交换值
            tree->data = temp->data;
            //重建左子树
            tree->left = delNode3(tree->left, temp);
            free(temp);
        } else {
            //2.待删除的节点有左/右子树
            if(tree->left == NULL) {
                tree = tree->right;
            } else if(tree->right == NULL) {
                tree = tree->left;
            } else {
                //3.待删除的节点没有左右子树
                tree = NULL;
            }
        }
    }
    return tree;
}

进行测试打印输出是否是自己需要的结果

    /* 
                 10
               /    \
              5      15
            /   \      \
           3     7     20
          / \   / \
         2   4  6  8
    */
Node *t = lookup(root,10);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:8--5--3--2--4--7--6--15--20

Node *t = lookup(root,2);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:10--5--3--4--7--6--8--15--20

Node *t = lookup(root,5);
Node *ret = delNode3(root, t);
printPreorder(ret);//preorder:10--4--3--2--7--6--8--15--20

相关文章

网友评论

      本文标题：二叉搜索树的节点删除(c实现)

      本文链接：https://www.haomeiwen.com/subject/saklpftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|二叉搜索树的节点删除(c实现)|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！