树——通用树结点的清除

1，树是一种数据结构，用来存储容器，因此它可以用来看做一种容器类型；既可以向容器中插入东西，也可以将容器中的东西倒出来；

2，清除操作的定义：

1，void clear()：

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

3，树中数据元素的清除：

1，递归清除；

4，清除操作功能的定义：

1，free(node)

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

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

　　2，功能函数代码实现：

 1 　　 /* 清除 node 树的根结点 */
 2     void free(GTreeNode<T>* node)
 3     {
 4         if( node != NULL )  // 非空树，结点的父结点为空和结点指向空是截然不同的，一个是根结点，一个是空树
 5         {
 6             for(node->child.move(0); !node->child.end(); node->child.next())
 7             {
 8                 free(node->child.current());  // 每个孩子执行清除操作
 9             }
10 
11             if( node->flag() ) // 是否来自堆空间，有些结点直接在栈上申请了，没有用 insert() 函数申请
12             {
13                 delete node;  // 删除根结点，只有堆中的对象才能 delete， 否则其他对象在其生命周期是不需要在代码里面来管理的，否则崩溃
14             }
15         }
16 　　}

5，清除 clear() 函数代码的实现：

1     void clear()
2     {
3         free(root());
4         this->m_root = NULL;
5         m_queue.clear();  // 树里面每个元素都没有了，所以也要清除队列里面的数据元素
6     }

6，树中的结点可能来源于不同的存储空间，如何判断指针指向的结点对象是堆空间中的结点并释放？

1，问题分析：

1，单凭内存地址很难准确判断具体的存储区域；

2，只有堆空间的内存需要主动释放（delete）；

1，堆空间中的内存通过 new 来的，可以在 new 一个对象时，标记一个对象，依据标记来 delete;

3，清除操作时只要对堆空间中的结点进行释放；

2，解决方案：工厂模式

1，在 GTreeNode 中增加保护成员变量 m_flat；

1，增加标记；

2，将 GTreeNode 中的 operator new 重载为保护成员函数；

1，意味着在外部不能用 new 操作符创建堆空间中的结点；

3，提供工厂方法 GTreeNode<T>* NewNode()；

1，NewNode() 是公有静态的，返回堆里面的一个结点；

2，在外部可以用它创建堆空间的结点；

3，这就是工厂方法；

4，在工厂方法中 new 新结点并将 m_flag 设置为 true；

3，树结点的工厂模式示例：

1，也就是禁止外界 new （因为外界 new 不会标记）的同时让外界或内部用 NewNode() 并标记 m_flag；

7，工程模式代码实现（具体参见博文“树——树的定义与操作”中 15.1 和“树——通用树的存储结构与结点实现”中 7.1的内容）：

 1     protected:  // 从两个子类中重构而来；减少代码冗余
 2     bool m_flag;  // 结点是否申请自堆空间的标志，第一步
 3     
 4     void* operator new(unsigned int size) throw()  // new 不能够在外部调用了，统一路径，第二步
 5     {
 6         return Object::operator new(size);
 7     }
 8 
 9 public:
10     T value;  // 存储数据
11     GTreeNode<T>* parent;  // 每个结点包含指向父结点的指针，向上是线性数据结构（链表）
12 
13     GTreeNode()
14     {
15         m_flag = false;  // 构造函数将堆空间申请标志置为 false; 第四步
16         parent = NULL;
17     }
18 
19     static GTreeNode<T>* NewNode() // 工厂模式，第三步
20     {
21         GTreeNode<T>* ret = new GTreeNode<T>();
22         if( ret != NULL )  // 申请堆空间成功
23         {
24             ret->m_flag = true;
25         }
26         return ret;
27     }
28 
29     bool flag()  // 堆空间的标志； 重构而来
30     {
31         return m_flag;
32     }

8，小结：

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

2，销毁结点时需要决定是否释放对应的内存空间；

1，之前的顺序结构没有销毁结点的考虑是因为它们的结点不是单独的类，外界不能够定义；

3，工厂模式可用于“定制”堆空间中的结点；