55 树中结点的清除操作

树中结点的清除操作(一)

问题树中的结点可能来源于不同的存储空间，如何判断堆空间的结点并释放？
问题分析
- 单凭内存地址很难准确判断具体的存储区域
- 只有堆空间的内存需要主动释放(delete)
- 清除操作时只需要对堆中的结点进行释放
解决方案:工厂模式
1. 在GTreeNode中增加保护成员m_flag
2. 将GTreeNode中的operator new重载为保护成员函数
3. 提供工厂方法GTreeNode<T>* NewNode()
4. 在工厂方法中new 新结点并将m_flag设置为true
树结点的工厂模式示例
```
GTreeNode<int> *hn=GTreeNode<int>::NewNode();
GTreeNode<int> sp;
if(hn->flag())    //true
{
    delete hn;
}
hn = &sn;
if(sn->flag())    //false
{
    delete hn;
}
```

删除的方式
- 基于数据元素值的删除
  - SharedPointer<Tree<T>>remove(const T &value)
- 基于结点的删除
  - SharedPointer<Tree<T>>remove(TreeNode<T> *node)
删除操作成员函数的设计要点
- 将被删除结点所代表的子树进行删除
- 删除函数返回一棵堆空间中的树
- 具体返回值为指向树的智能指针对象
树中结点的删除
实用的设计原则

当需要从函数中返回堆中的对象时，使用智能指针(SharedPointer)作为函数的返回值。
删除操作功能的定义
- void remove(GeneralTreeNode<T> *node,GeneralTree<T>* &ret)
  - 将node为根节点的子树从原来的树中删除
  - ret作为子树返回(ret指向堆空间中的树对象)
删除功能函数的实现