关键词：树的清除操作、工厂模式
0. 清除操作的定义
void clear():将树中的所有结点清除（释放堆空间的结点）
1. 树中数据元素的清除
清除步骤
2. 清除操作功能的定义
free(node)：清除node为根节点的树，并释放树中的每一个结点
递归调用free(node)函数
void free(GTreeNode<T>* node)
{
if( node != NULL )
{
for(node->child.move(0); !node->child.end(); node->child.next())
{
free(node->child.current());
}
delete node;
}
}
void clear()
{
free(root());
this->m_root = NULL;
}
3. 问题：树中的结点可能来源于不同的存储空间，如何判断堆空间中的结点并释放？
问题分析：
- 单凭内存地址很难准确判断具体的存储区域
- 只有堆空间的内存需要主动释放
- 清除操作时只需要对堆中的结点进行释放
解决方案：工厂模式
- 在
GTreeNode中增加保护成员变量m_flag - 将
GTreeNode中的operator new重载为保护成员函数 - 提供工厂方法
GTreeNode<T>* NewNode()(共有的静态成员函数) - 在工厂方法中
new新结点并将m_flag设置为true
4. 树结点的工厂模式示例
树结点工厂模式类图及使用示例
- 修改
GTreeNode.h文件
#ifndef GTREENODE_H
#define GTREENODE_H
#include "TreeNode.h"
#include "LinkList.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class GTreeNode : public TreeNode<T>
{
protected:
bool m_flag;
void* operator new(unsigned int size) throw() // 将new设置为保护成员函数
{
return Object::operator new(size);
}
public:
LinkList<GTreeNode<T>*> child;
GTreeNode()
{
m_flag = false;
}
bool flag()
{
return m_flag;
}
static GTreeNode<T>* NewNode() // 工厂方法
{
GTreeNode<T>* ret = new GTreeNode<T>();
if( ret != NULL )
{
ret->m_flag = true;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create new GTreeNode...");
}
return ret;
}
};
}
#endif // GTREENODE_H
- 修改
GTree.h中的insert函数和free函数
void free(GTreeNode<T>* node)
{
if( node != NULL )
{
for(node->child.move(0); !node->child.end(); node->child.next())
{
free(node->child.current());
}
if( node->flag() ) // 添加判断条件，如果flag为真，即在堆空间中创建对象，则需要delete空间
{
delete node;
}
}
}
bool insert(const T& value, TreeNode<T>* parent)
{
bool ret = true;
GTreeNode<T>* node = GTreeNode<T>::NewNode(); // 使用工厂方法
if( node != NULL )
{
node->value = value;
node->parent = parent;
insert(node);
}
else
{
THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create new GTreeNode...");
}
return ret;
}
5. 小结
- 清除操作用于销毁树中的每个结点
- 销毁结点时需要决定是否释放对应的内存空间
- 工厂模式可用于定制堆空间中的结点
- 只有销毁定制结点的时候需要进行释放
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
