树——二叉树结点的删除与清除

时间：2021-04-22 10:11:25

1，删除的方式：

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

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

                     1，删除的是那个以结点为根结点的子树，所以返回值是一个指向树的指针；

                     2，希望智能指针帮助管理这个堆空间创建出来的树；

       2，基于结点的删除：

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

             

2，二叉树中结点的删除：

树——二叉树结点的删除与清除

      

3，删除操作功能的定义及实现：

 树——二叉树结点的删除与清除

       1，void remove(BTreeNode<T>* node, BTree<T>*& ret)

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

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

　　2，功能函数代码实现：

 1 　　 /* 实现一个删除功能函数， ret 返回一个堆空间中的二叉树对象 */
 2     virtual void remove(BTreeNode<T>* node, BTree<T>*& ret)
 3     {
 4         ret = new BTree<T>();
 5 
 6         if( ret == NULL )
 7         {
 8             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new tree ...");
 9         }
10         else  // node 当然是不可以为空，在共有 remove() 函数中有体现，但是这样不好，建议在此处体现的好
11         {
12             if( root() == node )  // 如果删除的是根结点
13             {
14                 this->m_root = NULL;  // 根结点清空，这里有点不理解，这里 m_root 只是树指向 node 的一个指针，它不是结点的一部分；
15             }
16             else  // 断掉和父结点之间的指针
17             {
18                BTreeNode<T>* parent = dynamic_cast<BTreeNode<T>*>(node->parent);
19 
20                 if( parent->left == node )  // 如果结点是父结点的左子树
21                 {
22                     parent->left = NULL;
23                 }
24                 else if( parent->right == node )  // 如果结点是父结点的右子树
25                 {
26                     parent->right = NULL;
27                 }
28 
29                 node->parent = NULL;  // 删除结点的父亲
30             }
31 
32             ret->m_root = node;  // 通过 ret 返回新的结点指向这里
33         }
34 　　 }

　　3，成员函数代码实现：

　　　　1，基于数据值的代码实现：

 1 　　 SharedPointer< Tree<T> > remove(const T& value)
 2     {
 3         BTree<T>* ret = NULL;
 4 
 5         BTreeNode<T>* node = find(value);
 6 
 7         if( node == NULL )
 8         {
 9             THROW_EXCEPTION(InvalidParameterException, "Can not find the tree node via value ...");
10         }
11         else
12         {
13             remove(node, ret);
14 
15             m_queue.clear();
16         }
17 
18         return ret;
19 　　 }

    　　2，基于结点的代码实现：

 1 　　 SharedPointer< Tree<T> > remove(TreeNode<T>* node)
 2     {
 3         BTree<T>* ret = NULL;
 4 
 5         node = find(node);  // 当前要删除的结点在这个树中
 6 
 7         if( node == NULL )
 8         {
 9             THROW_EXCEPTION(InvalidParameterException, "Parameter node is invalid ...");
10         }
11         else
12         {
13             remove(dynamic_cast<BTreeNode<T>*>(node), ret);
14 
15             m_queue.clear();
16         }
17 
18         return ret;
19     }

 

4，清除操作的定义：

       1，void clear()

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

             

5，二叉树中结点的清除：

 树——二叉树结点的删除与清除

 

6，清除操作功能的定义及成员函数实现：

      树——二叉树结点的删除与清除

       1，free(node):

              1，清除 node 为根结点的二叉树；

              2，释放二叉树中的每一个结点；

　　2，功能函数代码实现：

 1 　　 /* 定义清除功能函数，参数为要清除树的根结点 */
 2     virtual void free(BTreeNode<T>* node)
 3     {
 4         if( node != NULL )  // 树非空
 5         {
 6             free(node->left);
 7             free(node->right);
 8 
 9             if( node->flag() )  // 如果是从堆空间申请来的
10             {
11                 delete node;
12             }
13         }
14     }

　　3，clear() 成员函数代码实现：

1     void clear()
2     {
3         free(root());
4         m_queue.clear();
5         this->m_root = NULL;
6     }

 

7，小结：

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

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

              1，完全断绝父子关系；

       3，清除操作用于销毁树中的每个结点；

       4，销毁结点时判断是否释放对应的内存空间（工厂模式）；

标签：

相关文章