数据结构之树（三十四）-创新互联

我们在前面学习了排序相关的知识，从今天开始，我们来学习数据结构中树的相关东西。那么什么是树呢？树是一种非线性的数据结构。

创新互联为您提适合企业的网站设计 让您的网站在搜索引擎具有高度排名，让您的网站具备超强的网络竞争力！结合企业自身，进行网站设计及把握，最后结合企业文化和具体宗旨等，才能创作出一份性化解决方案。从网站策划到网站设计制作、做网站， 我们的网页设计师为您提供的解决方案。

树是由 n( n >= 0 ) 个结点组成的有限集合。如果n= 0，称为空树；如果n > 0，则：a> 有一个特定的称之为根（root）的结点；b> 根结点只有直接后继，但没有直接前驱；c> 除根以外的其它结点划分为 m( m >= 0 ) 个互不相交的有限集合T0, T1, … Tm-1，每个集合又是一棵树，并且称之为根的子树（sub tree）。下来我们来看看树的示意图，如下所示

数据结构之树（三十四）

下来我们来看一个树中度的概念。它是指树中的结点包含一个数据及若干指向子树的分支，及诶单拥有子树的数目称为结点的度。度为 0 的结点称为叶结点，度不为 0 的结点称为分支节点。树的度定义为所有节点中度的大值。下来来看一个数的度为 3 的示例，如下图所示

数据结构之树（三十四）

下来来介绍下树中的前驱和后继。结点的直接后继称为该结点的孩子，相应的，该结点称为孩子的双亲；结点的孩子的孩子的 ... 称为该结点的子孙，相应的，该结点称为子孙的祖先；同一个双亲的孩子之间互称兄弟。下来来看看树的前驱和后继的结构示意图

数据结构之树（三十四）

我们来看看树中结点的层次，如下图所示

数据结构之树（三十四）

树也有有序性，什么叫树的有序性呢？如果树中结点的各子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为无序树。示意图如下图所示

数据结构之树（三十四）

那么既然有树的概念，就肯定有森林的概念。森林是由 n( n >= 0 ) 棵互不相交的树组成的集合。那么在树中肯定也有一些常用的操作，如下

1、将元素插入树中；

2、将元素从树中删除；

3、获取树的结点数；

4、获取树的高度；

5、获取树的度；

6、清空树中的元素；

7、 ......   


树与结点的类关系可以如下表示

数据结构之树（三十四）

那么我们下来来看看那树和结点抽象类的具体源码是怎样写的

Tree.h 源码

#ifndef TREE_H
#define TREE_H

#include "TreeNode.h"
#include "SharedPointer.h"

namespace DTLib
{

template < typename T >
class Tree : public Object
{
protected:
    TreeNode<T>* m_root;
public:
    Tree() { m_root = NULL; }
    virtual bool ×××ert(TreeNode<T>* node) = 0;
    virtual bool ×××ert(const T& value, TreeNode<T>* parent) = 0;
    virtual SharedPointer< Tree<T> > remove(const T& value) = 0;
    virtual SharedPointer< Tree<T> > remove(TreeNode<T>* node) = 0;
    virtual TreeNode<T>* find(const T& value) const = 0;
    virtual TreeNode<T>* find(TreeNode<T>* node) const = 0;
    virtual TreeNode<T>* root() const = 0;
    virtual int degree() const = 0;
    virtual int count() const = 0;
    virtual int height() const = 0;
    virtual void clear() = 0;
};

}

#endif // TREE_H

TreeNode.h 源码

#ifndef TREENODE_H
#define TREENODE_H

#include "Object.h"

namespace DTLib
{

template < typename T >
class TreeNode : public Object
{
public:
    T value;
    TreeNode<T>* parent;

    TreeNode()
    {
        parent = NULL;
    }

    virtual ~TreeNode() = 0;
};

template < typename T >
TreeNode<T>::~TreeNode()
{

}

}

#endif // TREENODE_H

下来我们来看看树和结点的存储结构是怎么设计的，结构图如下

数据结构之树（三十四）

设计要点：1、GTree 为通用的树结构，每个结点可以存在多个后继结点；2、GTreeNode 能够包含任意多指向后继结点的指针；3、实现树结构的所有操作（增，删，查，等）。

GTree（通用树结构）的实现框架如下图所示

数据结构之树（三十四）

我们来看看通用树结构（框架）是怎样创建的，源码如下

GTree.h 源码

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
public:
    bool ×××ert(TreeNode<T>* node)
    {
        bool ret = true;
        
        return ret;
    }

    bool ×××ert(const T& value, TreeNode<T>* parent)
    {
        bool ret = true;

        return ret;
    }

    SharedPointer< Tree<T> > remove(const T& value)
    {
        return NULL;
    }

    SharedPointer< Tree<T> > remove(TreeNode<T>* node)
    {
        return NULL;
    }

    GTreeNode<T>* find(const T& value) const
    {
        return NULL;
    }

    GTreeNode<T>* find(TreeNode<T>* node) const
    {
        return NULL;
    }

    GTreeNode<T>* root() const
    {
        return dynamic_cast<GTreeNode<T>*>(this->m_root);
    }

    int degree() const
    {
        return 0;
    }

    int count() const
    {
        return 0;
    }

    int height() const
    {
        return 0;
    }

    void clear()
    {
        this->m_root = NULL;
    }

    ~GTree()
    {
        clear();
    }
};

}

#endif // GTREE_H

GTreeNode.h 源码

#ifndef GTREENODE_H
#define GTREENODE_H

#include "Tree.h"

namespace DTLib
{

template < typename T >
class GTreeNode : public TreeNode<T>
{
public:
    LinkList<GTreeNode<T>*> child;
};

}

#endif // GTREENODE_H

我们在树的设计中，为什么要在每个树节点中包含指向前驱结点的指针呢？从根结点到叶结点是非线性的数据结构，但是从叶结点到根结点是线性的数据结构（链表），结果如下

数据结构之树（三十四）

下来我们就来一一的实现上面的查找、插入等操作

1、查找操作

查找的方式应分为两种：a> 基于数据元素值的查找：GTreeNode<T>* find(const T& value) const；b> 基于结点的查找：GTreeNode<T>* find(TreeNode<T>* node) const。

 a> 基于数据元素值的查找，我们先在 protected 属性中定义 find(node, value) 功能，在 node 为根结点的树中查找 value 所在的结点，实现思路如下

数据结构之树（三十四）

b> 基于结点的查找，还是在 protected 属性中定义 find(node, obj) 功能，在 node 为根结点的树中查找是否存在 obj 结点，实现思路如下

数据结构之树（三十四）

具体查找相关源码实现如下

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
protected:
    GTreeNode<T>* find(GTreeNode<T>* node, const T& value) const
    {
        GTreeNode<T>* ret = NULL;

        if( node != NULL )
        {
            if( node->value == value )
            {
                return node;
            }
            else
            {
                for(node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
                {
                    ret = find(node->child.current(), value);
                }
            }
        }

        return ret;
    }

    GTreeNode<T>* find(GTreeNode<T>* node, GTreeNode<T>* obj) const
    {
        GTreeNode<T>* ret = NULL;

        if( node == obj )
        {
            return node;
        }
        else
        {
            if( node != NULL )
            {
                for(node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
                {
                    ret = find(node->child.current(), obj);
                }
            }
        }

        return ret;
    }
public:
    GTreeNode<T>* find(const T& value) const
    {
        return find(root(), value);
    }

    GTreeNode<T>* find(TreeNode<T>* node) const
    {
        return find(root(), dynamic_cast<GTreeNode<T>*>(node));
    }
    
    GTreeNode<T>* root() const
    {
        return dynamic_cast<GTreeNode<T>*>(this->m_root);
    }
};

}

#endif // GTREE_H

2、插入操作

插入的方式应分为两种：a> 插入新结点：bool ×××ert(TreeNode<T>* node)；b> 插入数据元素：bool ×××ert(const T& value, TreeNode<T>* parent)。

那么如何在树中指定新结点的位置呢？问题分析：a> 树是非线性的，无法采用下标的形式定位数据元素；b> 每一个树结点都有唯一的前驱结点（父结点）；c> 因此，必须先找到前驱节点，才能完成新结点的插入。

 a> 新结点的插入，如下图所示

数据结构之树（三十四）

插入新结点的流程如下图所示

数据结构之树（三十四）

 b> 插入数据元素，流程如下图所示

数据结构之树（三十四）

下来我们来看看具体源码是怎么实现的

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
public:
    bool ×××ert(TreeNode<T>* node)
    {
        bool ret = true;

        if( node != NULL )
        {
            if( this->m_root == NULL )
            {
                node->parent = NULL;
                this->m_root = node;
            }
            else
            {
                GTreeNode<T>* np = find(node->parent);

                if( np != NULL )
                {
                    GTreeNode<T>* n = dynamic_cast<GTreeNode<T>*>(node);

                    if( np->child.find(n) < 0 )
                    {
                        np->child.×××ert(n);
                    }
                }
                else
                {
                    THROW_EXCEPTION(INvalidOPerationException, "Invalid parent tree node ...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "Parement node cannot be NULL ...");
        }

        return ret;
    }

    bool ×××ert(const T& value, TreeNode<T>* parent)
    {
        bool ret = true;
        GTreeNode<T>* node = GTreeNode<T>::NewNode();

        if( node != NULL )
        {
            node->value = value;
            node->parent = parent;

            ×××ert(node);
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new tree node ...");
        }

        return ret;
    }
};

}

#endif // GTREE_H

我们来写点测试代码，看看前面实现的查找和插入代码是否正确

#include <iostream>
#include "GTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    GTree<char> t;
    GTreeNode<char>* node = NULL;

    t.×××ert('A', NULL);
    
    node = t.find('A');
    t.×××ert('B', node);
    t.×××ert('C', node);
    t.×××ert('D', node);

    node = t.find('B');
    t.×××ert('E', node);
    t.×××ert('F', node);

    node = t.find('E');
    t.×××ert('K', node);
    t.×××ert('L', node);

    node = t.find('C');
    t.×××ert('G', node);

    node = t.find('G');
    t.×××ert('N', node);

    node = t.find('D');
    t.×××ert('H', node);
    t.×××ert('I', node);
    t.×××ert('J', node);

    node = t.find('H');
    t.×××ert('M', node);

    const char* s = "KLFNMIJ";

    for(int i=0; i<7; i++)
    {
        TreeNode<char>* node = t.find(s[i]);

        while( node != NULL )
        {
            cout << node->value << " ";

            node = node->parent;
        }

        cout << endl;
    }

    return 0;
}

运行结果如下

数据结构之树（三十四）

我们看到已经实现了之前定义的树结构。

3、清除操作

a> 定义：void clear()；将树中的所有结点清除（释放堆中的结点），树中数据元素的清除如下所示

数据结构之树（三十四）

b> free(node)；清除 node 为根结点的树，释放树中的每一个结点，实现思路如下

数据结构之树（三十四）

具体源码实现如下

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
protected:
    void free(GTreeNode<T>* node) const
    {
        if( node != NULL )
        {
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                free(node->child.current());
            }

            delete node;
        }
    }
public:    
    void clear()
    {
        free(root());

        this->m_root = NULL;

        m_queue.clear();
    }

    ~GTree()
    {
        clear();
    }
};

}

#endif // GTREE_H

测试代码如下

#include <iostream>
#include "GTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    GTree<char> t;
    GTreeNode<char>* node = NULL;
    GTreeNode<char> root;

    root.value = 'A';
    root.parent = NULL;

    t.×××ert(&root);

    node = t.find('A');
    t.×××ert('B', node);
    t.×××ert('C', node);
    t.×××ert('D', node);

    node = t.find('B');
    t.×××ert('E', node);
    t.×××ert('F', node);

    node = t.find('E');
    t.×××ert('K', node);
    t.×××ert('L', node);

    node = t.find('C');
    t.×××ert('G', node);

    node = t.find('G');
    t.×××ert('N', node);

    node = t.find('D');
    t.×××ert('H', node);
    t.×××ert('I', node);
    t.×××ert('J', node);

    node = t.find('H');
    t.×××ert('M', node);

    t.clear();

    const char* s = "KLFNMIJ";

    for(int i=0; i<7; i++)
    {
        TreeNode<char>* node = t.find(s[i]);

        while( node != NULL )
        {
            cout << node->value << " ";

            node = node->parent;
        }

        cout << endl;
    }

    return 0;
}

我们来看看结果

数据结构之树（三十四）

我们看到已经清空了树。但是此时存在一个问题，那便是我们在 main 函数中是在堆上值指定的数据元素，上面的清除操作也会将这个堆中的数据元素删除掉。这必然会导致问题，那么对于树中的结点来源于不同的存储空间的话，此时我们应如何判断堆空间中的结点并释放？问题分析：单凭内存地址很难准确判断具体的存储区域，只有堆空间的内存需要主动释放（delete），清除操作时只需要对堆中的结点进行释放。

此时的解决方案：工厂模式。

 i. 在 GTreeNode 中增加保护成员变量 m_flag；

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

 iii. 提供工厂方法 GTreeNode<T>* NewNode()；

iv. 在工厂方法中 new 新结点并将 m_flag 设置为 true。

树结点的工厂模式示例如下

数据结构之树（三十四）

我们来看看具体的源码实现

#ifndef GTREENODE_H
#define GTREENODE_H

#include "Tree.h"
#include "LinkList.h"

namespace DTLib
{

template < typename T >
class GTreeNode : public TreeNode<T>
{
protected:
    bool m_flag;

    GTreeNode(const GTreeNode<T>&);
    GTreeNode<T>* operator = (const GTreeNode<T>&);

    void* operator new(unsigned int size) throw()
    {
        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;
        }

        return ret;
    }
};

}

#endif // GTREENODE_H

在上面的 delete node 操作时外面进行 node->flag() 的判断，如果为 true，我们再来进行删除。为例方便的进行说明，我们在这块加个调试语句，再来一个 else 语句，里面打印出不同存储区域的数据元素，我们来看看结果

数据结构之树（三十四）

我们看到此时除了我们自己在堆上指定的 A 之外，剩下的数据元素已经全部被清除掉。

4、删除操作

删除的方式也分为两种：a> 基于数据元素值的删除：SharedPointer< Tree<T> > remove(const T& value)；b> 基于结点的删除：SharedPointer< Tree<T> > remove(TreeNode<T>* node)；

删除操作成员函数的设计要点：1、将被删结点所代表的子树进行删除；2、删除函数返回一颗堆空间的树；3、具体返回值为指向树的只能指针对象。树中结点的删除示意如下图所示

数据结构之树（三十四）

如果当我们需要从函数中返回堆中的对象时，使用智能指针（SharedPointer）作为函数的返回值。删除操作功能的定义：void remove(GTreeNode<T>* node, GTree<T>*& ret)；将 node 为根结点的子树从原来的树中删除，ret 作为子树返回（ret 指向堆空间中的树对象）。删除功能函数的实现思路如下

数据结构之树（三十四）

具体源码实现如下

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
protected:
    void remove(GTreeNode<T>* node, GTree<T>*& ret)
    {
        ret = new GTree();

        if( ret != NULL )
        {
            if( root() == node )
            {
                this->m_root = NULL;
            }
            else
            {
                LinkList<GTreeNode<T>*>& child = dynamic_cast<GTreeNode<T>*>(node->parent)->child;

                child.remove(child.find(node));

                node->parent = NULL;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create new tree ...");
        }
    }
public:
    SharedPointer< Tree<T> > remove(const T& value)
    {
        GTree<T>* ret = NULL;
        GTreeNode<T>* node = find(value);

        if( node != NULL )
        {
            remove(node, ret);

            m_queue.clear();
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "Can not find the node via parament value ...");
        }

        return ret;
    }

    SharedPointer< Tree<T> > remove(TreeNode<T>* node)
    {
        GTree<T>* ret = NULL;

        node = find(node);

        if( node != NULL )
        {
            remove(dynamic_cast<GTreeNode<T>*>(node), ret);

            m_queue.clear();
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "Parament node is invalid ...");
        }

        return ret;
    }
};

}

#endif // GTREE_H

我们来写点测试代码，删除子树 D，测试代码如下

#include <iostream>
#include "GTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    GTree<char> t;
    GTreeNode<char>* node = NULL;
    GTreeNode<char> root;

    root.value = 'A';
    root.parent = NULL;

    t.×××ert(&root);

    node = t.find('A');
    t.×××ert('B', node);
    t.×××ert('C', node);
    t.×××ert('D', node);

    node = t.find('B');
    t.×××ert('E', node);
    t.×××ert('F', node);

    node = t.find('E');
    t.×××ert('K', node);
    t.×××ert('L', node);

    node = t.find('C');
    t.×××ert('G', node);

    node = t.find('G');
    t.×××ert('N', node);

    node = t.find('D');
    t.×××ert('H', node);
    t.×××ert('I', node);
    t.×××ert('J', node);

    node = t.find('H');
    t.×××ert('M', node);

    //SharedPointer< Tree<char> > p = t.remove(t.find('D'));
    t.remove(t.find('D'));

    const char* s = "KLFNMIJ";

    for(int i=0; i<7; i++)
    {
        TreeNode<char>* node = t.find(s[i]);

        while( node != NULL )
        {
            cout << node->value << " ";

            node = node->parent;
        }

        cout << endl;
    }

    return 0;
}

我们来看看运行结果

数据结构之树（三十四）

我们看到子树 D 已经被删除了，如果我们想用这个删除的子树 D，该如何做呢？将上面的测试代码中的注释的那行放开，将下面的 remove 注释掉，再将下面 for 循环中的 t.find(s[i]) 改为 p->find(s[i])，我们来看看运行结果

数据结构之树（三十四）

我们看到打印出的是我们删除的子树 D。

5、其他属性操作

a> 树中结点的数目，功能定义：count(node)；在 node 为根结点的树中统计结点数目，实现思路如下

数据结构之树（三十四）

树的结点数目的计算示例如下：

数据结构之树（三十四）

b> 树的高度，功能定义：height(node)；获取 node 为根结点的树的高度，实现思路如下

数据结构之树（三十四）

树的高度计算示例如下：

数据结构之树（三十四）

c> 树的度数，功能定义：degree(node)；获取 node 为根结点的树的度数，实现思路如下

数据结构之树（三十四）

树的度计算示例

数据结构之树（三十四）

下来看看具体的源码实现

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
protected
    int count(GTreeNode<T>* node) const
    {
        int ret = 0;

        if( node != NULL )
        {
            ret = 1;

            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                ret += count(node->child.current());
            }
        }

        return ret;
    }

    int height(GTreeNode<T>* node) const
    {
        int ret = 0;

        if( node != NULL )
        {
            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int h = height(node->child.current());

                if( ret < h )
                {
                    ret = h;
                }
            }

            ret = ret + 1;
        }

        return ret;
    }

    int degree(GTreeNode<T>* node) const
    {
        int ret = 0;

        if( node != NULL )
        {
            ret = node->child.length();

            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                int d = degree(node->child.current());

                if( ret < d )
                {
                    ret = d;
                }
            }
        }

        return ret;
    }
public:
    int degree() const
    {
        return degree(root());
    }

    int count() const
    {
        return count(root());
    }

    int height() const
    {
        return height(root());
    }
};

}

#endif // GTREE_H

测试代码如下

#include <iostream>
#include "GTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    GTree<char> t;
    GTreeNode<char>* node = NULL;
    GTreeNode<char> root;

    root.value = 'A';
    root.parent = NULL;

    t.×××ert(&root);

    node = t.find('A');
    t.×××ert('B', node);
    t.×××ert('C', node);
    t.×××ert('D', node);

    node = t.find('B');
    t.×××ert('E', node);
    t.×××ert('F', node);

    node = t.find('E');
    t.×××ert('K', node);
    t.×××ert('L', node);

    node = t.find('C');
    t.×××ert('G', node);

    node = t.find('G');
    t.×××ert('N', node);

    node = t.find('D');
    t.×××ert('H', node);
    t.×××ert('I', node);
    t.×××ert('J', node);

    node = t.find('H');
    t.×××ert('M', node);

    cout << "t.count() : " << t.count() << endl;
    cout << "t.height() : " << t.height() << endl;
    cout << "t.degree() : " << t.degree() << endl;

    return 0;
}

我们来看看运行结果

数据结构之树（三十四）

6、层次遍历

如何按层次遍历通用树结构中的每一个数据元素呢？树是非线性的数据结构，树的结点没有固定的编号方式。那么我们就得提供一个新的需求，为通用树结构提供新的方法，能快速遍历每一个结点。

设计思路（游标）：a> 在树中定义一个游标（GTreeNode<T>*）；b> 遍历开始前将游标指向根结点（root()）；c> 获取游标指向的数据元素；d> 通过结点中的 child 成员移动游标。提供一组遍历相关的函数，按层次访问树中的数据元素。如下

数据结构之树（三十四）

层次遍历算法：a> 原料：class LinkQueue<T>；b> 游标：LinkQueue<T>::front()；c> 思想：i. begin() --> 将根节点压入队列中；ii. current() --> 访问队头元素指向的数据元素；iii. next() --> 队头元素弹出，将对头元素的孩子压入队列中（核心）；iv. end() --> 判断队列是否为空。层次遍历算法示例如下

数据结构之树（三十四）

下来我们来看看具体的源码实现

GTreeNode.h 源码

#ifndef GTREENODE_H
#define GTREENODE_H

#include "Tree.h"
#include "LinkList.h"

namespace DTLib
{

template < typename T >
class GTreeNode : public TreeNode<T>
{
protected:
    bool m_flag;

    GTreeNode(const GTreeNode<T>&);
    GTreeNode<T>* operator = (const GTreeNode<T>&);

    void* operator new(unsigned int size) throw()
    {
        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;
        }

        return ret;
    }
};

}

#endif // GTREENODE_H

GTree.h 源码

#ifndef GTREE_H
#define GTREE_H

#include "Tree.h"
#include "GTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"

namespace DTLib
{

template < typename T >
class GTree : public Tree<T>
{
protected:
    LinkQueue<GTreeNode<T>*> m_queue;

    GTree(const GTree<T>&);
    GTree<T>* operator = (const GTree<T>&);
public:    
    GTree()
    {

    }
    
    bool begin()    
    {
        bool ret = (root() != NULL);

        if( ret )
        {
            m_queue.clear();
            m_queue.add(root());
        }

        return ret;
    }

    bool end()
    {
        return (m_queue.length() == 0);
    }

    bool next()
    {
        bool ret = (m_queue.length() > 0);

        if( ret )
        {
            GTreeNode<T>* node = m_queue.front();

            m_queue.remove();

            for(node->child.move(0); !node->child.end(); node->child.next())
            {
                m_queue.add(node->child.current());
            }
        }

        return ret;
    }

    T current()
    {
        if( !end() )
        {
            return m_queue.front()->value;
        }
        else
        {
            THROW_EXCEPTION(InvalidParameterException, "No value at current position ...");
        }
    }
};

}

#endif // GTREE_H

那么在 remove 的操作中也要加上相应的队列的清除：m_queue.clear(); 测试代码如下

#include <iostream>
#include "GTree.h"

using namespace std;
using namespace DTLib;

int main()
{
    GTree<char> t;
    GTreeNode<char>* node = NULL;
    GTreeNode<char> root;

    root.value = 'A';
    root.parent = NULL;

    t.×××ert(&root);

    node = t.find('A');
    t.×××ert('B', node);
    t.×××ert('C', node);
    t.×××ert('D', node);

    node = t.find('B');
    t.×××ert('E', node);
    t.×××ert('F', node);

    node = t.find('E');
    t.×××ert('K', node);
    t.×××ert('L', node);

    node = t.find('C');
    t.×××ert('G', node);

    node = t.find('G');
    t.×××ert('N', node);

    node = t.find('D');
    t.×××ert('H', node);
    t.×××ert('I', node);
    t.×××ert('J', node);

    node = t.find('H');
    t.×××ert('M', node);

    for(t.begin(); !t.end(); t.next())
    {
        cout << t.current() << endl;
    }

    return 0;
}

运行结果如下

数据结构之树（三十四）

我们看到已经将之前的树结构层次遍历了一遍。通过对树的学习，总结如下：1、树是一种非线性的数据结构，结点拥有唯一前驱（父结点）和若干后继（子结点）；2、树的结点包含一个数据及若干指向其他结点的指针，树与结点在程序中表现为特殊的数据类型；3、基于数据元素的查找可判断值是否存在于树中，基于结点的查找可判断树中是否存在指定结点；4、插入操作是构建树的唯一操作，执行插入操作时必须指明结点间的父子关系；5、插入操作必须正确处理指向父结点的指针，插入数据元素时需要从堆空间中创建结点；6、销毁结点时需要决定是否释放对应的内存空间，工厂模式可用于“定制”堆空间中的结点，只有销毁定制结点的时候需要进行释放；7、删除操作必须完善处理父结点和子结点的关系，它的返回值为指向树的智能指针对象，函数中返回堆中的对象时使用智能指针作为返回值；8、插入操作和删除操作都依赖于查找操作；9、树的结点没有固定的编号方式，可以按照层次关系对树中的结点进行遍历；10、通过游标的思想设计遍历成员函数，遍历成员函数是相互依赖，相互配合的关系，遍历算法的核心为队列的使用。

网页名称：数据结构之树（三十四）-创新互联
分享URL：https://www.cdcxhl.com/article4/ihsoe.html

成都网站建设公司_创新互联，为您提供全网营销推广、网站内链、网站设计、标签优化、响应式网站、品牌网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

成都网页设计公司

手机网站建设知识

同城分类信息