64_二叉树的结点删除与清除

关键词：二叉树的结点的删除、二叉树的结点的清除

0. 删除的方式

• 基于数据元素值的删除：SharedPointer<Tree<T>> remove(const T& value)
• 基于结点的删除：SharedPointer<Tree<T>> remove(TreeNode<T>* node)
  二叉树中结点的删除
• 删除操作的功能函数的定义：void remove(BTreeNode<T>* node, BTree<T>* &ret)
  • 将node为根结点的子树从原来的二叉树中删除
  • ret作为子树返回（ret指向堆空间中的二叉树对象）
    删除功能函数的实现流程图

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

        if( ret != NULL )
        {
            if( root() != node )
            {
                BTreeNode<T>* p = dynamic_cast<BTreeNode<T>*>(node->parent);

                if( p->left == node )
                {
                    p->left = NULL;
                }
                else if( p->right == node )
                {
                    p->right = NULL;
                }

                node->parent = NULL;
            }
            else
            {
                this->m_root = NULL;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a new tree...");
        }
    }

    SharedPointer< Tree<T> > remove(const T& value)
    {
        BTree<T>* ret = NULL;
        BTreeNode<T>* node = find(value);

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

        return ret;
    }

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

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

        return ret;
    }

1. 清除操作

• void clear()：将二叉树中的所有结点清除（释放堆中的结点）
  二叉树中结点的清除示意图
• 清除操作功能的定义：free(node)
  • 清除node为根结点的二叉树

  • 释放二叉树中的每一个结点

    
    清除操作的递归调用

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

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

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

        this->m_root = NULL;
    }

2. 小结

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

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4