数据结构--树

一 树

A .树的属性及介绍
树是一种非线性的数据结构
树是由n(n>=0)个结点组成的有限集合
1.如果n=0,称为空树
2.如果n>0，则有一个特定的称之为根的结点，跟结点只有直接后继，但没有直接前驱，除根以外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1,....,Tm-1，每个集合又是一棵树，并且称之为根的子树

3.树中度的概念
a.树的结点包含一个数据及若干指向子树的分支
b.结点拥有的子树数目称为结点的度--度为0的结点称为叶节点，度不为0的结点称为分支结点
c.树的度定义为所有结点中度的最大值

4.树中的前驱和后继
a.结点的直接后继称为该结点的孩子--相应的，该结点称为孩子的双亲
b.结点的孩子的孩子的.....称为该结点的子孙--相应的,该结点称为子孙的祖先
c.同一个双亲的孩子之间互称为兄弟

5.树中结点的层次

树中结点的最大层次称为树的深度或高度
6.树的有序性
如果树中结点的各子树从左向右是有次序的，子树件不能互换位置，则称该树为有序树，否则为无序树

7.森林的概念
森林是由n(n>=0)棵互不相交的树组成的集合

树的实现

template <typename T>
class Tree: public Object
{
    protected:
        TreeNode<T>* m_root;
    public:
        Tree(){m_root=NULL};
        //插入结点
        virtual bool insert(TreeNode<T>* node)=0;
        virtual bool insert(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；//清空树
}；

树中的结点也表示为一种特殊的数据类型

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

    TreeNode()
    {
        parent=NULL;
    }
    virtual ~TreeNode()=0;
};

树与结点的关系

B. 树的各种实现
a.树和结点的存储结构设计

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

GTreeNode设计与实现

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

GTree的设计与实现

template <typename T>
class GTree :public Tree<T>
{
};

GTree(通用树结构)的实现架构

    template <typename T>
    class GTreeNode:public TreeNode<T>
    {
    public:
        LinkList<GTreeNode<T>*>child;//child成员为单链表

        static GTreeNode<T>* NewNode()
        {
            GTreeNode<T>* ret=new GTreeNode<T>();

            if(ret!=NULL)
            {
                ret->m_flag=true;
            }

            return ret;
        }
    };

每个树结点在包含指向前驱结点的指针的原因是
1.根结点==》叶结点:非线性数据结构
2.叶结点==》根结点:线性数据结构

树中结点的查找操作
A.查找的方式
1.基于数据元素的查找

GTreeNode<T>* find(const T&value)const

2.基于结点的查找

GTreeNode<T>*find(TreeNode<T>*node)const

基于数据元素值的查找
定义功能：find(node,value)--在node为根结点的树中查找value所在的结点

基于结点的查找
定义功能:find(node,obj)--在node为根结点的树中查找是否存在obj结点

树中结点的插入操作
A.插入的方式
1.插入新结点

bool insert(TreeNode<T>* node)

2.插入数据元素

bool insert(const T&value,TreeNode<T>* parent)

分析
1.树是非线性的，无法采用下标的形式定位数据元素
2.每一个树结点都有唯一的前驱结点(父结点)
3.因此，必须先找到前驱结点，才能完成新结点的插入

树中结点的清除操作
void clear()--将树中的所有结点清除(释放堆中的结点)
清除操作功能的定义
free(node)--清除node为根结点的树，释放每一个结点

树中结点的删除操作
A.删除方式
1.基于数据元素值的删除

SharePointer<Tree<T>>remove(const T&value)

2.基于结点的删除

SharePointer<Tree<T>>remove(TreeNode<T>*node)

删除操作成员函数的设计要点
1.将被删结点所代表的子树进行删除
2.删除函数返回一颗堆空间中的树
3.具体返回值为指向树的智能指针对象

删除操作功能的定义
void remove(GTreeNode<T> node,GTree<T>& ret)--将node为根结点的子树从原来的树中删除，ret作为子树返回(ret指向堆空间的树对象)

树中属性操作的实现
A.树中结点的数目
定义功能:count(node)--在node为根结点的树中统计结点数目

B.树的高度
定义功能:height(node)--获取node为根结点的树的高度

C.树的度数
定义功能:degree(node)--获取node为根结点的树的度数

D.树的层次遍历
设计思路：
1.在树中定义一个游标(GTreeNode<T>*)
2.在遍历开始前将游标指向根结点(root())
3.获取游标指向的数据元素
4.通过结点中的child成员移动游标
算法
1.原料：class LinkQueue<T>
2.游标：LinkQueue<T>::front()
3.思想
a.begin()=>将根结点压入队列中
b.current()=>访问对头元素指向的数据元素
c.next()=>队头元素弹出，将队头元素的孩子压入队列中
d.end()=>判断队列是否为空

完整树的实现代码

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

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

        //基于数据元素值的查找，都是遍历实现的
        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;
           }

        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())
                {
                    delete node;
                }
            }
        }

        /*
         * 删除操作成员函数的设计要点
         *   将被删除结点所代表的子树进行删除
         *   删除函数返回一颗堆空间中的树
         *   具体返回值为指向树的智能指针对象
         */
        void remove(GTreeNode<T>* node,GTree<T>*& ret)
        {
            ret=new GTree<T>();

            if(ret==NULL)
            {
                THROW_EXCEPTION(NoEoughMemoryException,"...");
            }
            else
            {
                if(root()!=node)
                {
                    //获取删除结点的父结点的子结点链表
                    LinkList<GTreeNode<T>*>& child=dynamic_cast<GTreeNode<T>*>(node->parent)->child;
                    child.remove(child.find(node)); //从链表中删除结点
                    node->parent=NULL;//结点的父结点置NULL
                }
                else
                {
                    this->m_root=NULL;
                }
            }
        }

        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 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;
        }

        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;
        }
    public:
        //插入结点
        //以结点的方式插入
        bool insert(TreeNode<T>* node)
        {
            bool ret=true;

            if(node!=NULL)//当结点不为空时
            {
                if(this->m_root==NULL)//如果此时的根结点为空
                {
                    node->parent=NULL;//node结点就是根结点
                    this->m_root=node;
                }
                else
                {
                    GTreeNode<T>* np=find(node->parent);//在堆空间创建np指向node的父节点
                    if(np!=NULL)
                    {
                        GTreeNode<T>* n=dynamic_cast<GTreeNode<T>*>(node);//noded的类型为TreeNode,需要将其强制转换为GTreeNode

                        if(np->child.find(n)<0)
                        {
                            ret=np->child.insert(n);
                        }
                    }
                    else
                    {
                        THROW_EXCEPTION(InvalidOperationException,"...");
                    }
                }
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }

            return ret;
        }

        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(InvalidOperationException,"...");
            }

            return ret;
        }

        //删除结点
        SharedPointer< Tree<T> > remove(const T& value)
        {
            GTree<T>* ret=NULL;

            GTreeNode<T>* node=find(value);

            if(node!=NULL)
            {
                remove(node,ret);
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }

            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);
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }

            return NULL;
        }

        //查找结点
        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));//强制类型转换将TreeNode类型转换为GTreeNode类型
        }//root对应的root的类型也应该一样

        //根结点访问函数
        GTreeNode<T>* root()const
        {
            return dynamic_cast<GTreeNode<T>*>(this->m_root);
        }

        //树的度访问函数
        int degree()const
        {
            return degree(root());
        }

        //树的高度访问函数
        int height()const
        {
             return height(root());
        }

        //树的结点数目访问函数
        int count()const
        {
            return count(root());
        }

        //清空树
        void clear()
        {
            free(root());
            this->m_root=NULL;
        }
        //树中结点的遍历
        //树是一种非线性的数据结构，遍历树中结点可以采用游标的方式。
        //A、在树中定义一个游标（GTreeNode<T>* node）
        //B、遍历开始前将游标指向根结点
        //C、获取游标指向的数据元素
        //D、通过结点中的child成员移动游标

        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);
            {
                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(InvalidOperationException,"...");
            }
        }

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