【数据结构】64_二叉树中的结点删除与清除

算法漫游者
• 阅读 1929

二叉树中的结点删除

删除方式

  • 基于数据元素值的删除

    • SharedPointer<Tree<T>> remove(const T &value);

  • 基于结点的删除

    • SharedPointer<Tree<T>> remove(TreeNode<T> *node);

二叉树中结点的删除

【数据结构】64_二叉树中的结点删除与清除

删除操作功能的定义

  • void removeP(BTreeNode<T> node, Btree<T> *&ret);

    • 将 node 作为根结点的子树从原来的二叉树中删除
    • ret 作为子树返回 （ret 指向堆空间中的二叉树对象）

【数据结构】64_二叉树中的结点删除与清除

编程实验：二叉树结点的删除操作

#ifndef BTREE_H
#define BTREE_H

#include "Tree.h"
#include "BTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"

namespace DTLib
{

template <typename T>
class BTree : public Tree<T>
{
public:
    BTree() = default;

    bool insert(TreeNode<T> *node) override
    {
        return insert(node, ANY);
    }

    virtual bool insert(TreeNode<T> *node, BTNodePos pos)
    {
        bool ret = true;

        if (node != nullptr)
        {
            if (this->m_root == nullptr)
            {
                node->parent = nullptr;
                this->m_root = node;
            }
            else
            {
                BTreeNode<T> *np = find(node->parent);

                if (np != nullptr)
                {
                    ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
                }
                else
                {
                    THROW_EXCEPTION(InvalidParameterExcetion, "Invalid parent tree node ...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter can not be null ...");
        }

        return ret;
    }

    bool insert(const T &value, TreeNode<T> *parent) override
    {
        return insert(value, parent, ANY);
    }

    virtual bool insert(const T &value, TreeNode<T> *parent, BTNodePos pos)
    {
        bool ret = true;
        BTreeNode<T> *node = BTreeNode<T>::NewNode();

        if (node != nullptr)
        {
            node->value = value;
            node->parent = parent;

            ret = insert(node, pos);

            if (!ret)
            {
                delete node;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create node ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(const T &value) override
    {
        BTree<T> *ret = nullptr;

        BTreeNode<T> *node = find(value);

        if (node != nullptr)
        {
            remove(node, ret);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Can not find the tree node via value ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(TreeNode<T> *node) override
    {
        BTree<T> *ret = nullptr;

        node = find(node);

        if (node != nullptr)
        {
            remove(dynamic_cast<BTreeNode<T>*>(node), ret);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter node is invalid ...");
        }

        return ret;
    }

    BTreeNode<T>* find(const T &value) const override
    {
        return find(root(), value);
    }

    BTreeNode<T>* find(TreeNode<T> *node) const override
    {
        return find(root(), dynamic_cast<BTreeNode<T>*>(node));
    }

    BTreeNode<T>* root() const override
    {
        return dynamic_cast<BTreeNode<T>*>(this->m_root);
    }

    int degree() const override
    {
        return 0;
    }

    int count() const override
    {
        return 0;
    }

    int height() const
    {
        return 0;
    }

    void clear() override
    {
        this->m_root = nullptr;
    }

    ~BTree()
    {
        clear();
    }

protected:
    BTree(const BTree<T>&) = default;
    BTree<T>& operator = (const BTree<T>&) = default;

    virtual BTreeNode<T>* find(BTreeNode<T> *node, const T &value) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node != nullptr)
        {
            if (node->value == value)
            {
                ret = node;
            }
            else
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, value);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, value);
                }
            }
        }

        return ret;
    }

    virtual BTreeNode<T>* find(BTreeNode<T> *node, BTreeNode<T> *obj) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node == obj)
        {
            ret = node;
        }
        else
        {
            if (node != nullptr)
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, obj);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, obj);
                }
            }
        }

        return ret;
    }

    virtual bool insert(BTreeNode<T> *node, BTreeNode<T> *np, BTNodePos pos)
    {
        bool ret = true;

        if (pos == ANY)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == LEFT)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == RIGHT)
        {
            if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }

        return ret;
    }

    virtual void remove(BTreeNode<T> *node, BTree<T> *&ret)
    {
        ret = new BTree<T>();

        if (ret != nullptr)
        {
            if (root() == node)
            {
                this->m_root = nullptr;
            }
            else
            {
                BTreeNode<T> *parent = dynamic_cast<BTreeNode<T>*>(node->parent);

                if (node == parent->left)
                {
                    parent->left = nullptr;
                }
                else if (node == parent->right)
                {
                    parent->right = nullptr;
                }

                node->parent = nullptr;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create btree ...");
        }
    }
};

}

#endif // BTREE_H

文件：main.cpp

#include <iostream>
#include "BTreeNode.h"
#include "BTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    BTree<int> bt;
    BTreeNode<int> *n = nullptr;

    bt.insert(1, nullptr);

    n = bt.find(1);
    bt.insert(2, n);
    bt.insert(3, n);

    n = bt.find(2);
    bt.insert(4, n);
    bt.insert(5, n);

    n = bt.find(4);
    bt.insert(8, n);
    bt.insert(9, n);

    n = bt.find(5);
    bt.insert(10, n);

    n = bt.find(3);
    bt.insert(6, n);
    bt.insert(7, n);

    SharedPointer<Tree<int>> sp = bt.remove(3);

    int a[] = {8, 9, 10, 6, 7};

    for (int i=0; i<5; ++i)
    {
        TreeNode<int> *node = bt.find(a[i]);

        while (node)
        {
            cout << node->value << " ";
            node = node->parent;
        }

        cout << endl;
    }

    cout << "----------" << endl;

    for (int i=0; i<5; ++i)
    {
        TreeNode<int> *node = sp->find(a[i]);

        while (node)
        {
            cout << node->value << " ";
            node = node->parent;
        }

        cout << endl;
    }

    return 0;
}

输出：

8 4 2 1
9 4 2 1
10 5 2 1


----------



6 3
7 3

二叉树的清除

清除操作的定义

  • void clear();

    • 将二叉树中的所有结点清除 （释放堆中的结点）

二叉树中结点的清除

【数据结构】64_二叉树中的结点删除与清除

清除操作的功能定义

  • free(node)

    • 清除 node 为根节点的二叉树
    • 释放二叉树中的每一个结点

【数据结构】64_二叉树中的结点删除与清除

编程实验：清除二叉树中的结点

文件：BTree.h

#ifndef BTREE_H
#define BTREE_H

#include "Tree.h"
#include "BTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"

namespace DTLib
{

template <typename T>
class BTree : public Tree<T>
{
public:
    BTree() = default;

    bool insert(TreeNode<T> *node) override
    {
        return insert(node, ANY);
    }

    virtual bool insert(TreeNode<T> *node, BTNodePos pos)
    {
        bool ret = true;

        if (node != nullptr)
        {
            if (this->m_root == nullptr)
            {
                node->parent = nullptr;
                this->m_root = node;
            }
            else
            {
                BTreeNode<T> *np = find(node->parent);

                if (np != nullptr)
                {
                    ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
                }
                else
                {
                    THROW_EXCEPTION(InvalidParameterExcetion, "Invalid parent tree node ...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter can not be null ...");
        }

        return ret;
    }

    bool insert(const T &value, TreeNode<T> *parent) override
    {
        return insert(value, parent, ANY);
    }

    virtual bool insert(const T &value, TreeNode<T> *parent, BTNodePos pos)
    {
        bool ret = true;
        BTreeNode<T> *node = BTreeNode<T>::NewNode();

        if (node != nullptr)
        {
            node->value = value;
            node->parent = parent;

            ret = insert(node, pos);

            if (!ret)
            {
                delete node;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to create node ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(const T &value) override
    {
        BTree<T> *ret = nullptr;

        BTreeNode<T> *node = find(value);

        if (node != nullptr)
        {
            remove(node, ret);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Can not find the tree node via value ...");
        }

        return ret;
    }

    SharedPointer<Tree<T>> remove(TreeNode<T> *node) override
    {
        BTree<T> *ret = nullptr;

        node = find(node);

        if (node != nullptr)
        {
            remove(dynamic_cast<BTreeNode<T>*>(node), ret);
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter node is invalid ...");
        }

        return ret;
    }

    BTreeNode<T>* find(const T &value) const override
    {
        return find(root(), value);
    }

    BTreeNode<T>* find(TreeNode<T> *node) const override
    {
        return find(root(), dynamic_cast<BTreeNode<T>*>(node));
    }

    BTreeNode<T>* root() const override
    {
        return dynamic_cast<BTreeNode<T>*>(this->m_root);
    }

    int degree() const override
    {
        return 0;
    }

    int count() const override
    {
        return 0;
    }

    int height() const
    {
        return 0;
    }

    void clear() override
    {
        free(root());

        this->m_root = nullptr;
    }

    ~BTree()
    {
        clear();
    }

protected:
    BTree(const BTree<T>&) = default;
    BTree<T>& operator = (const BTree<T>&) = default;

    virtual BTreeNode<T>* find(BTreeNode<T> *node, const T &value) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node != nullptr)
        {
            if (node->value == value)
            {
                ret = node;
            }
            else
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, value);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, value);
                }
            }
        }

        return ret;
    }

    virtual BTreeNode<T>* find(BTreeNode<T> *node, BTreeNode<T> *obj) const
    {
        BTreeNode<T> *ret = nullptr;

        if (node == obj)
        {
            ret = node;
        }
        else
        {
            if (node != nullptr)
            {
                if (ret == nullptr)
                {
                    ret = find(node->left, obj);
                }

                if (ret == nullptr)
                {
                    ret = find(node->right, obj);
                }
            }
        }

        return ret;
    }

    virtual bool insert(BTreeNode<T> *node, BTreeNode<T> *np, BTNodePos pos)
    {
        bool ret = true;

        if (pos == ANY)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == LEFT)
        {
            if (np->left == nullptr)
            {
                np->left = node;
            }
            else
            {
                ret = false;
            }
        }
        else if (pos == RIGHT)
        {
            if (np->right == nullptr)
            {
                np->right = node;
            }
            else
            {
                ret = false;
            }
        }

        return ret;
    }

    virtual void remove(BTreeNode<T> *node, BTree<T> *&ret)
    {
        ret = new BTree<T>();

        if (ret != nullptr)
        {
            if (root() == node)
            {
                this->m_root = nullptr;
            }
            else
            {
                BTreeNode<T> *parent = dynamic_cast<BTreeNode<T>*>(node->parent);

                if (node == parent->left)
                {
                    parent->left = nullptr;
                }
                else if (node == parent->right)
                {
                    parent->right = nullptr;
                }

                node->parent = nullptr;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create btree ...");
        }
    }

    virtual void free(BTreeNode<T> *node)
    {
        if (node != nullptr)
        {
            free(node->left);
            free(node->right);

            if (node->flag())
            {
                delete node;
            }
        }
    }
};

}

#endif // BTREE_H

文件:main.cpp

#include <iostream>
#include "BTreeNode.h"
#include "BTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    BTree<int> bt;
    BTreeNode<int> *n = nullptr;

    bt.insert(1, nullptr);

    n = bt.find(1);
    bt.insert(2, n);
    bt.insert(3, n);

    n = bt.find(2);
    bt.insert(4, n);
    bt.insert(5, n);

    n = bt.find(4);
    bt.insert(8, n);
    bt.insert(9, n);

    n = bt.find(5);
    bt.insert(10, n);

    n = bt.find(3);
    bt.insert(6, n);
    bt.insert(7, n);

    bt.clear();

    int a[] = {8, 9, 10, 6, 7};

    for (int i=0; i<5; ++i)
    {
        TreeNode<int> *node = bt.find(a[i]);

        while (node)
        {
            cout << node->value << " ";
            node = node->parent;
        }

        cout << endl;
    }

    return 0;
}

输出：

小结

  • 删除操作将目标结点所代表的子树移除
  • 删除操作必须完善处理父结点和子结点的关系
  • 清除操作用于销毁树中的每个结点
  • 销毁结点时判断是否释放对应的内存空间（工厂模式）

以上内容整理于狄泰软件学院系列课程，请大家保护原创！

c++
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
•
3年前
PHP安全性防范方式
<h2SQL注入</h2<pSQL注入是一种恶意攻击，用户利用在表单字段输入SQL语句的方式来影响正常的SQL执行。</p<h4防范方式</h4<ul<li使用mysql\_real\_escape\_string()，或者addslashes()过滤数据</li<li手动检查每一数据是否为正确的数据类型</li<li使用
972
0
0
Stella981 Stella981
•
3年前
Photoshop
1.保存的时候，选择保存为web和设备所用格式按住shift，点击你想要保存的切片，选中的边框会变黄，再点击“存储”在接下来的框的底部，点击选择“选中的切片”2.PS如何删除所有切片呢？如果文件里面有很多切片，需要全部删除，最快捷的操作是这样的：执行“视图——清除切片”，这样可以快速删除所有切片。3.li:lastofty
821
0
0
Wesley13 Wesley13
•
3年前
Activiti 工作流入门指南
<divclass"htmledit\_views"id"content\_views"<h1<aname"t0"</a概览</h1<p如我们的介绍部分所述，Activiti目前分为两大类：</p<ul<li<p<ahref"https://activiti.gitbook.io/activiti7deve
1085
0
0
Wesley13 Wesley13
•
3年前
Java实现 LeetCode 814 二叉树剪枝 （遍历树）
814\.二叉树剪枝给定二叉树根结点root，此外树的每个结点的值要么是0，要么是1。返回移除了所有不包含1的子树的原二叉树。(节点X的子树为X本身，以及所有X的后代。)示例1:输入:\1,null,0,0,1\输出:\1,null,0,null,1\解释:
1026
0
0
Stella981 Stella981
•
3年前
ASMSupport教程4.8 生成逻辑运算操作
<p在java中有以下逻辑运算符：</p<ul<li&amp;&amp;：条件与</li<li||：条件或</li<li&amp;:布尔型的逻辑与</li<li|：布尔型的逻辑或</li<li^:布尔型的逻辑异或</li<li!:非操作</li</ul<p那么接下来我们将些段例子
983
0
0
Stella981 Stella981
•
3年前
C# WCF Post body过大 404 not found
1、web.config进行下面的配置，可以看到报错的详细信息<system.serviceModel  <behaviors   <serviceBehaviors    <behavior     <!为避免泄漏元数据信息，请在部署前将以下值设置为false并删除上面的元数据终结点
848
0
0
Stella981 Stella981
•
3年前
ASMSupport教程4.11 生成数组操作
<p在任何语言里，数组都是基本的数据类型，我们这一节将讲述如何生成数组操作。</p<p数组操作包括以下几个：</p<ol<li创建数组</li<li获取数组长度</li<li获取数组每个元素的内容</li<li为数组元素赋值</li</ol<p我们接下来对每种操作进行详解。</p<h3<fonts
922
0
0
Stella981 Stella981
•
3年前
IdeaVim
<divid"cnblogs\_post\_body"class"blogpostbodycnblogsmarkdown"<h3id"ideavim简介"IdeaVim简介</h3<pIdeaVim是IntelliJIDEA的一款插件，他提高了我们写代码的速度，对代码的跳转，查找也很友好。</p<ul<li安装位置</
915
0
0
Stella981 Stella981
•
3年前
PHP中unset,array_splice删除数组中元素的区别
php(https://www.oschina.net/p/php)中删除数组元素是非常的简单的，但有时删除数组需要对索引进行一些排序要求我们会使用到相关的函数，这里我们来介绍使用unset,array\_splice删除数组中的元素区别吧如果要在某个数组中删除一个元素，可以直接用的unset，但是数组的索引不会重排：?(https://ww
834
0
0
Wesley13 Wesley13
•
3年前
MySQL 清空表(truncate)与删除表中数据(delete) 详解
删除表信息的方式有两种:truncatetabletable\_name;delete\fromtable\_name;注:truncate操作中的table可以省略，delete操作中的\可以省略truncate、delete清空表数据的区别:1truncate是整体删除(速度较快)，delete是逐条删
837
0
0
Wesley13 Wesley13
•
3年前
HTML快捷写法大全
父子用\ \Ulli\3\<ul\    <li\</li\    <li\</li\    <li\</li\</ul\兄弟之间用,也可以省写\pspan\，\ul\<p\</p\<span
896
0
0
算法漫游者
算法漫游者
Lv1
人归落雁后，思发在花前。
文章
3
粉丝
0
获赞
0
热门文章
盘点Windows那些优秀的文本编辑器
VUE - MVVM - part1 - defineProperty