树——通用树结点的删除

1，本文实现通用树结构结点的删除操作；

2，删除的方式（和插入操作互逆）：

1，基于数据元素值的删除：

1，SharedPointer< Tree<T> > remove(const T& value)

1，返回指向一棵树的智能指针；

2，基于结点的删除：

1，SharedPointer< Tree<T> > remove(TreeNode<T>* node)

3，删除操作成员函数的设计要点：

1，将被删除结点所代表的子树进行删除；

2，删除函数返回一颗堆空间中的树；

1，这个返回的子树在堆空间创建，创建好了要返回一个指针；

2，这样可以再次利用删除的这颗返回的子树，直接利用智能指针访问这个结点；

3，具体返回值为指向树的智能指针对象；

1，管理树的生命周期；

2，remove() 返回后自动的清除；

4，树中结点的删除：

5，实用的设计原则：

1，当需要从函数中返回堆中的对象时，使用智能指针（SharedPointer）作为函数的返回值；

1，好处是可以使申请指针函数、使用指针函数、C++ 编译器都不管的堆空间自己管理生命周期；

6，删除操作功能的定义：

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

1，将 node 为根结点的子树从原来的树中删除；

2，ret 作为子树返回（ ret 指向对空间中的树对象）；

3，第二个参数是一个指针的别名；

　　2，删除功能函数代码实现：

 1     /* 删除操作的功能函数 */
 2     void remove(GTreeNode<T>* node, GTree<T>*& ret)
 3     {
 4         ret = new GTree<T>();
 5 
 6         if( ret == NULL )  // 如果创建不成功
 7         {
 8             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new tree ...");
 9         }
10         else
11         {
12             if( root() == node )  // 判断要删除的结点和根结点是否相同
13             {
14                 this->m_root = NULL;  // 变成空结点
15             }
16             else
17             {   
18                 /* 定义要删除结点父亲中存储孩子的链表的别名 */
19                 LinkList<GTreeNode<T>*>& child = dynamic_cast<GTreeNode<T>*>(node->parent)->child;
20                 child.remove(child.find(node));  // 先找到这个结点在链表中的下标，然后剔除，这里的 remove 是链表成员函数
21                 node->parent = NULL;  // node 中的父指针指向空，不再指向其原来的//父结点
22             }
23 
24             ret->m_root = node;  // 作为一棵树返回
25         }
26 　　}

7，删除操作成员函数的代码实现：

1，按元素值删除：

 1 　　 /* 删除的是结点，之后将结点代表的子树删除，然后将子树返回，返回由堆空间指向的对象，应由智能指针指向 */
 2     SharedPointer< Tree<T> > remove(const T& value)
 3     {
 4         GTree<T>* ret = NULL;
 5 
 6         GTreeNode<T>* node = find(value);  // 先找到这个结点
 7 
 8         if( node == NULL )  // 数据元素值没有存储在树中
 9         {
10             THROW_EXCEPTION(InvalidParameterException, "Can not find the node via parameter value ...");
11         }
12         else
13         {
14             remove(node, ret);  // 调用功能函数删除
15 
16             m_queue.clear();  // 删除结点也要清除队列里面的结点
17         }
18 
19         return ret;
20 　　}

　　2，按结点删除：

 1 　　 /* 删除的是结点，之后将结点代表的子树删除，然后将子树返回，返回由堆空间指向的对象，应由智能指针指向 */
 2     SharedPointer< Tree<T> > remove(TreeNode<T>* node)
 3     {
 4         GTree<T>* ret = NULL;
 5 
 6         node = find(node);  // 先找到这个结点
 7 
 8         if( node == NULL )  // 结点没有在树中
 9         {
10             THROW_EXCEPTION(InvalidParameterException, "Parameter node is invalid ...");
11         }
12         else
13         {
14             remove(dynamic_cast<GTreeNode<T>*>(node), ret); // 调用功能函数删除
15 
16             m_queue.clear();  // 删除结点也要清除队列里面的结点，否则可能出问题
17         }
18 
19         return ret;
20 　　 }

8，小结：

1，删除操作将目标结点所代表的子树移除；

2，删除操作必须完善处理父结点和子结点的关系；

3，删除操作的返回值为指向树的智能指针对象；

4，函数中返回堆中的对象时，使用智能指针作为返回值；