數(shù)據(jù)結(jié)構(gòu)--樹

一 樹

A .樹的屬性及介紹
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)
樹是由n(n>=0)個(gè)結(jié)點(diǎn)組成的有限集合
1.如果n=0,稱為空樹
2.如果n>0，則有一個(gè)特定的稱之為根的結(jié)點(diǎn)，跟結(jié)點(diǎn)只有直接后繼，但沒有直接前驅(qū)，除根以外的其他結(jié)點(diǎn)劃分為m(m>=0)個(gè)互不相交的有限集合T0,T1,....,Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹

3.樹中度的概念
a.樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及若干指向子樹的分支
b.結(jié)點(diǎn)擁有的子樹數(shù)目稱為結(jié)點(diǎn)的度--度為0的結(jié)點(diǎn)稱為葉節(jié)點(diǎn)，度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)
c.樹的度定義為所有結(jié)點(diǎn)中度的最大值

4.樹中的前驅(qū)和后繼
a.結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子--相應(yīng)的，該結(jié)點(diǎn)稱為孩子的雙親
b.結(jié)點(diǎn)的孩子的孩子的.....稱為該結(jié)點(diǎn)的子孫--相應(yīng)的,該結(jié)點(diǎn)稱為子孫的祖先
c.同一個(gè)雙親的孩子之間互稱為兄弟

5.樹中結(jié)點(diǎn)的層次

樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度
6.樹的有序性
如果樹中結(jié)點(diǎn)的各子樹從左向右是有次序的，子樹件不能互換位置，則稱該樹為有序樹，否則為無序樹

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

創(chuàng)新互聯(lián)堅(jiān)信：善待客戶，將會(huì)成為終身客戶。我們能堅(jiān)持多年，是因?yàn)槲覀円恢笨芍档眯刨嚒Ｎ覀儚牟缓鲇瞥踉L客戶，我們用心做好本職工作，不忘初心，方得始終。10多年網(wǎng)站建設(shè)經(jīng)驗(yàn)創(chuàng)新互聯(lián)是成都老牌網(wǎng)站營(yíng)銷服務(wù)商,為您提供成都網(wǎng)站制作、做網(wǎng)站、網(wǎng)站設(shè)計(jì)、H5高端網(wǎng)站建設(shè)、網(wǎng)站制作、高端網(wǎng)站設(shè)計(jì)、小程序設(shè)計(jì)服務(wù),給眾多知名企業(yè)提供過好品質(zhì)的建站服務(wù)。

樹的實(shí)現(xiàn)

template <typename T>
class Tree: public Object
{
    protected:
        TreeNode<T>* m_root;
    public:
        Tree(){m_root=NULL};
        //插入結(jié)點(diǎn)
        virtual bool insert(TreeNode<T>* node)=0;
        virtual bool insert(const T& value,TreeNode<T>* parent)=0;
        //刪除結(jié)點(diǎn)
        virtual SharedPointer<Tree<T>>remove(const T& value)=0;
        virtual SharedPointer<Tree<T>>remove(TreeNode<T>* node)=0;
        //查找結(jié)點(diǎn)
        virtual TreeNode<T>* find(const T& value)const=0;
        virtual TreeNode<T>* find(TreeNode<T>* node)const=0;
        //根結(jié)點(diǎn)訪問
        virtual TreeNode<T>* root()const=0;
        virtual int degree()const=0;//樹的度
        virtual int count()const=0;//樹的結(jié)點(diǎn)數(shù)目
        virtual int height()const=0;//樹的高度
        virtual void clear()=0；//清空樹
}；

樹中的結(jié)點(diǎn)也表示為一種特殊的數(shù)據(jù)類型

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

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

樹與結(jié)點(diǎn)的關(guān)系

B. 樹的各種實(shí)現(xiàn)
a.樹和結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)

設(shè)計(jì)要點(diǎn)：
1.GTree為通用樹結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可以存在多個(gè)后繼結(jié)點(diǎn)
2.GTreeNode能夠包含任意多指向后繼結(jié)點(diǎn)的指針
3.實(shí)現(xiàn)樹結(jié)構(gòu)的所有操作(增，刪，查，等)

GTreeNode設(shè)計(jì)與實(shí)現(xiàn)

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

GTree的設(shè)計(jì)與實(shí)現(xiàn)

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

GTree(通用樹結(jié)構(gòu))的實(shí)現(xiàn)架構(gòu)

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

每個(gè)樹結(jié)點(diǎn)在包含指向前驅(qū)結(jié)點(diǎn)的指針的原因是
1.根結(jié)點(diǎn)==》葉結(jié)點(diǎn):非線性數(shù)據(jù)結(jié)構(gòu)
2.葉結(jié)點(diǎn)==》根結(jié)點(diǎn):線性數(shù)據(jù)結(jié)構(gòu)

樹中結(jié)點(diǎn)的查找操作
A.查找的方式
1.基于數(shù)據(jù)元素的查找

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

2.基于結(jié)點(diǎn)的查找

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

基于數(shù)據(jù)元素值的查找
定義功能：find(node,value)--在node為根結(jié)點(diǎn)的樹中查找value所在的結(jié)點(diǎn)

基于結(jié)點(diǎn)的查找
定義功能:find(node,obj)--在node為根結(jié)點(diǎn)的樹中查找是否存在obj結(jié)點(diǎn)

樹中結(jié)點(diǎn)的插入操作
A.插入的方式
1.插入新結(jié)點(diǎn)

bool insert(TreeNode<T>* node)

2.插入數(shù)據(jù)元素

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

分析
1.樹是非線性的，無法采用下標(biāo)的形式定位數(shù)據(jù)元素
2.每一個(gè)樹結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)(父結(jié)點(diǎn))
3.因此，必須先找到前驅(qū)結(jié)點(diǎn)，才能完成新結(jié)點(diǎn)的插入

樹中結(jié)點(diǎn)的清除操作
void clear()--將樹中的所有結(jié)點(diǎn)清除(釋放堆中的結(jié)點(diǎn))
清除操作功能的定義
free(node)--清除node為根結(jié)點(diǎn)的樹，釋放每一個(gè)結(jié)點(diǎn)

樹中結(jié)點(diǎn)的刪除操作
A.刪除方式
1.基于數(shù)據(jù)元素值的刪除

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

2.基于結(jié)點(diǎn)的刪除

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

刪除操作成員函數(shù)的設(shè)計(jì)要點(diǎn)
1.將被刪結(jié)點(diǎn)所代表的子樹進(jìn)行刪除
2.刪除函數(shù)返回一顆堆空間中的樹
3.具體返回值為指向樹的智能指針對(duì)象

刪除操作功能的定義
void remove(GTreeNode<T> node,GTree<T>& ret)--將node為根結(jié)點(diǎn)的子樹從原來的樹中刪除，ret作為子樹返回(ret指向堆空間的樹對(duì)象)

樹中屬性操作的實(shí)現(xiàn)
A.樹中結(jié)點(diǎn)的數(shù)目
定義功能:count(node)--在node為根結(jié)點(diǎn)的樹中統(tǒng)計(jì)結(jié)點(diǎn)數(shù)目

B.樹的高度
定義功能:height(node)--獲取node為根結(jié)點(diǎn)的樹的高度

C.樹的度數(shù)
定義功能:degree(node)--獲取node為根結(jié)點(diǎn)的樹的度數(shù)

D.樹的層次遍歷
設(shè)計(jì)思路：
1.在樹中定義一個(gè)游標(biāo)(GTreeNode<T>*)
2.在遍歷開始前將游標(biāo)指向根結(jié)點(diǎn)(root())
3.獲取游標(biāo)指向的數(shù)據(jù)元素
4.通過結(jié)點(diǎn)中的child成員移動(dòng)游標(biāo)
算法
1.原料：class LinkQueue<T>
2.游標(biāo)：LinkQueue<T>::front()
3.思想
a.begin()=>將根結(jié)點(diǎn)壓入隊(duì)列中
b.current()=>訪問對(duì)頭元素指向的數(shù)據(jù)元素
c.next()=>隊(duì)頭元素彈出，將隊(duì)頭元素的孩子壓入隊(duì)列中
d.end()=>判斷隊(duì)列是否為空

完整樹的實(shí)現(xiàn)代碼

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

        //基于數(shù)據(jù)元素值的查找，都是遍歷實(shí)現(xiàn)的
        GTreeNode<T>* find(GTreeNode<T>* node, const T& value)const
            {
              GTreeNode<T>* ret = NULL;
              if(node != NULL)
              {
                  //如果根結(jié)點(diǎn)的就是目標(biāo)結(jié)點(diǎn)
                  if(node->value == value)
                  {
                       return node;
                  }
                  else
                  {
                      //遍歷根節(jié)點(diǎn)的子結(jié)點(diǎn)
                      for(node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
                      {
                          //對(duì)每個(gè)子子結(jié)點(diǎn)進(jìn)行查找
                          ret = find(node->child.current(), value);
                      }
                  }
              }
              return ret;
            }
        //基于結(jié)點(diǎn)得查找
        GTreeNode<T>* find(GTreeNode<T>* node, GTreeNode<T>* obj)const
           {
             GTreeNode<T>* ret = NULL;
             //根結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)
             if(node == obj)
             {
                 return node;
             }
             else
             {
                 if(node != NULL)
                 {
                     //遍歷子結(jié)點(diǎn)
                     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;
                }
            }
        }

        /*
         * 刪除操作成員函數(shù)的設(shè)計(jì)要點(diǎn)
         *   將被刪除結(jié)點(diǎn)所代表的子樹進(jìn)行刪除
         *   刪除函數(shù)返回一顆堆空間中的樹
         *   具體返回值為指向樹的智能指針對(duì)象
         */
        void remove(GTreeNode<T>* node,GTree<T>*& ret)
        {
            ret=new GTree<T>();

            if(ret==NULL)
            {
                THROW_EXCEPTION(NoEoughMemoryException,"...");
            }
            else
            {
                if(root()!=node)
                {
                    //獲取刪除結(jié)點(diǎn)的父結(jié)點(diǎn)的子結(jié)點(diǎn)鏈表
                    LinkList<GTreeNode<T>*>& child=dynamic_cast<GTreeNode<T>*>(node->parent)->child;
                    child.remove(child.find(node)); //從鏈表中刪除結(jié)點(diǎn)
                    node->parent=NULL;//結(jié)點(diǎn)的父結(jié)點(diǎn)置NULL
                }
                else
                {
                    this->m_root=NULL;
                }
            }
        }

        int count(GTreeNode<T>* node)const
        {
            int ret=0;
            if(node!=NULL)
            {
                ret=1;
                //遍歷根結(jié)點(diǎn)的子節(jié)點(diǎn)
                for(node->child.move(0);!node->child.end();node->child.next())
                {
                    ret+=count(node->child.current());//對(duì)結(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)
                }
            }

            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:
        //插入結(jié)點(diǎn)
        //以結(jié)點(diǎn)的方式插入
        bool insert(TreeNode<T>* node)
        {
            bool ret=true;

            if(node!=NULL)//當(dāng)結(jié)點(diǎn)不為空時(shí)
            {
                if(this->m_root==NULL)//如果此時(shí)的根結(jié)點(diǎn)為空
                {
                    node->parent=NULL;//node結(jié)點(diǎn)就是根結(jié)點(diǎn)
                    this->m_root=node;
                }
                else
                {
                    GTreeNode<T>* np=find(node->parent);//在堆空間創(chuàng)建np指向node的父節(jié)點(diǎn)
                    if(np!=NULL)
                    {
                        GTreeNode<T>* n=dynamic_cast<GTreeNode<T>*>(node);//noded的類型為TreeNode,需要將其強(qiáng)制轉(zhuǎn)換為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;
        }

        //刪除結(jié)點(diǎn)
        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;
        }

        //查找結(jié)點(diǎn)
        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));//強(qiáng)制類型轉(zhuǎn)換將TreeNode類型轉(zhuǎn)換為GTreeNode類型
        }//root對(duì)應(yīng)的root的類型也應(yīng)該一樣

        //根結(jié)點(diǎn)訪問函數(shù)
        GTreeNode<T>* root()const
        {
            return dynamic_cast<GTreeNode<T>*>(this->m_root);
        }

        //樹的度訪問函數(shù)
        int degree()const
        {
            return degree(root());
        }

        //樹的高度訪問函數(shù)
        int height()const
        {
             return height(root());
        }

        //樹的結(jié)點(diǎn)數(shù)目訪問函數(shù)
        int count()const
        {
            return count(root());
        }

        //清空樹
        void clear()
        {
            free(root());
            this->m_root=NULL;
        }
        //樹中結(jié)點(diǎn)的遍歷
        //樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，遍歷樹中結(jié)點(diǎn)可以采用游標(biāo)的方式。
        //A、在樹中定義一個(gè)游標(biāo)（GTreeNode<T>* node）
        //B、遍歷開始前將游標(biāo)指向根結(jié)點(diǎn)
        //C、獲取游標(biāo)指向的數(shù)據(jù)元素
        //D、通過結(jié)點(diǎn)中的child成員移動(dòng)游標(biāo)

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

            if(ret)
            {
                m_queue.clear();//清空隊(duì)列
                m_queue.add(root());//將根結(jié)點(diǎn)加入隊(duì)列
            }
            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();//隊(duì)頭元素出隊(duì)列
                //將隊(duì)頭元素的子節(jié)點(diǎn)入隊(duì)
                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();
        }
    };
}

網(wǎng)站標(biāo)題：數(shù)據(jù)結(jié)構(gòu)--樹
本文地址：http://bm7419.com/article38/igddsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計(jì)、網(wǎng)站導(dǎo)航、營(yíng)銷型網(wǎng)站建設(shè)、用戶體驗(yàn)、定制網(wǎng)站、全網(wǎng)營(yíng)銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)