56_树中结点的删除操作

关键词：结点的删除

0. 删除方式

• 基于数据元素值的删除：SharedPoiter<Tree<T>> remove(const T& value)
• 基于结点的删除：SharedPoiter<Tree<T>> remove(TreeNode<T>* node)

1. 删除操作成员函数的设计要点

• 将被删除结点所代表的子树进行删除
• 删除函数返回一颗堆空间中的树
• 具体返回值为指向树的智能指针对象
  树中结点的删除

实用的设计原则：当需要从函数中返回堆中的对象时，使用智能指针SharedPointer作为函数的返回值。

2. 删除操作功能的定义

void remove(GTreeNode<T>* node, GTree<T>*& ret):

• 将node为根节点的子树从原来的树中删除
• ret作为子树返回（ret指向堆空间中的树对象）
  删除功能函数的实现

    void remove(GTreeNode<T>* node, GTree<T>*& ret)
    {
        ret = new GTree<T>();

        if( ret != NULL )
        {
            if( root() != node )    // 当node结点不为root()结点时
            {
                LinkList<GTreeNode<T>*>& child = dynamic_cast<GTreeNode<T>*>(node->parent)->child;   // 父结点的孩子链表

                child.remove(child.find(node)); // 删除链表中的node结点

                node->parent = NULL;    // 将node结点的parent指针置为空
            }
            else                    // 当node结点为root()结点时
            {
                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)
    {
         GTree<T>* ret;
         GTreeNode<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)
    {
        GTree<T>* ret;

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

       return ret;
    }

3. 小结

• 删除操作将目标结点所代表的子树移除
• 删除操作必须完善处理父结点和子结点的关系
• 删除操作的返回值为指向树的智能指针对象
• 函数中返回堆中的对象时，使用智能指针作为返回值

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