树——通用树的存储结构与结点实现

1，上篇博文介绍了树的定义和相关概念定义，本节课创建树对象和树结点对象；

 

2，课程目标：

 

       1，完成树和结点的存储结构设计：

              1，没有树结点，就没有树，同生死；

                    

3，设计要点：

       1，GTree 为通用树结构，每个结点可以存在多个后继结点；

       2，GTreeNode 能够包含任意多指向后继结点的指针；

       3，实现树结构的所有操作（增，删，查，等）；

              1，抽象类只用包含功能函数，具体的对象才包含成员变量和实现功能函数；

             

4，GTreeNode 的设计与实现：

 

       1，组合单链表类，因为要包含任意多指向结点的指针：

              

            

5，GTree 的设计与实现：

 

       1，继承抽象树及组合使用通用结点：

             

      

6，GTree（通用树结构）的实现架构：

 

       1，后继表示方式是指针，指针通过单链表组织；

       2，包含指向父结点的指针；

 

7，通用树结点的创建：

　　1，通用树结点 GTreeNode 的创建：

#ifndef GTREENODE_H
#define GTREENODE_H

#include "TreeNode.h"
#include "LinkList.h"

namespace DTLib
{

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

    static GTreeNode<T>* NewNode() // 工厂模式
    {
        GTreeNode<T>* ret = new GTreeNode<T>();
        if( ret != NULL )  // 申请堆空间成功
        {
            ret->m_flag = true;
        }

        return ret;
    }
};

}

#endif // GTREENODE_H

    　2，通用树 GTree 的创建：

　　　　1，见后续通用树相关博文；

 

9，每个树结点中为什么包含指向前驱结点的指针？

 

       1，根结点 ==> 叶结点：非线性数据结构；

       2，叶结点 ==> 根结点：线性数据结构（链表）；

              1，每个结点通过 parent 指针都能找到唯一的父结点，于是每个叶结点都能够通过 parent 指针找到唯一的根结点，这是线性的链表结构；

              2，可以用树相关的知识，也可以用链表相关的知识处理树的问题；