55_树中结点的清除操作

关键词：树的清除操作、工厂模式

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. 问题：树中的结点可能来源于不同的存储空间，如何判断堆空间中的结点并释放？

问题分析：

• 单凭内存地址很难准确判断具体的存储区域
• 只有堆空间的内存需要主动释放
• 清除操作时只需要对堆中的结点进行释放

解决方案：工厂模式

1. 在GTreeNode中增加保护成员变量m_flag
2. 将GTreeNode中的operator new重载为保护成员函数
3. 提供工厂方法GTreeNode<T>* NewNode()(共有的静态成员函数)
4. 在工厂方法中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