真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯網站制作重慶分公司

數據結構--樹

一 樹

A .樹的屬性及介紹
樹是一種非線性的數據結構
樹是由n(n>=0)個結點組成的有限集合
1.如果n=0,稱為空樹
2.如果n>0，則有一個特定的稱之為根的結點，跟結點只有直接后繼，但沒有直接前驅，除根以外的其他結點劃分為m(m>=0)個互不相交的有限集合T0,T1,....,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹
數據結構--樹
3.樹中度的概念
a.樹的結點包含一個數據及若干指向子樹的分支
b.結點擁有的子樹數目稱為結點的度--度為0的結點稱為葉節(jié)點，度不為0的結點稱為分支結點
c.樹的度定義為所有結點中度的最大值
數據結構--樹
4.樹中的前驅和后繼
a.結點的直接后繼稱為該結點的孩子--相應的，該結點稱為孩子的雙親
b.結點的孩子的孩子的.....稱為該結點的子孫--相應的,該結點稱為子孫的祖先
c.同一個雙親的孩子之間互稱為兄弟
數據結構--樹
5.樹中結點的層次
數據結構--樹
樹中結點的最大層次稱為樹的深度或高度
6.樹的有序性
如果樹中結點的各子樹從左向右是有次序的，子樹件不能互換位置，則稱該樹為有序樹，否則為無序樹
數據結構--樹
7.森林的概念
森林是由n(n>=0)棵互不相交的樹組成的集合
數據結構--樹

創(chuàng)新互聯堅信：善待客戶，將會成為終身客戶。我們能堅持多年，是因為我們一直可值得信賴。我們從不忽悠初訪客戶，我們用心做好本職工作，不忘初心，方得始終。10多年網站建設經驗創(chuàng)新互聯是成都老牌網站營銷服務商,為您提供成都網站制作、做網站、網站設計、H5高端網站建設、網站制作、高端網站設計、小程序設計服務,給眾多知名企業(yè)提供過好品質的建站服務。

樹的實現

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

樹中的結點也表示為一種特殊的數據類型

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

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

樹與結點的關系
數據結構--樹

B. 樹的各種實現
a.樹和結點的存儲結構設計
數據結構--樹
設計要點：
1.GTree為通用樹結構，每個結點可以存在多個后繼結點
2.GTreeNode能夠包含任意多指向后繼結點的指針
3.實現樹結構的所有操作(增，刪，查，等)

GTreeNode設計與實現
數據結構--樹

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

GTree的設計與實現
數據結構--樹

template 
class GTree :public Tree
{
};

GTree(通用樹結構)的實現架構
數據結構--樹

    template 
    class GTreeNode:public TreeNode
    {
    public:
        LinkList*>child;//child成員為單鏈表

        static GTreeNode* NewNode()
        {
            GTreeNode* ret=new GTreeNode();

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

            return ret;
        }
    };

每個樹結點在包含指向前驅結點的指針的原因是
1.根結點==》葉結點:非線性數據結構
2.葉結點==》根結點:線性數據結構

數據結構--樹
樹中結點的查找操作
A.查找的方式
1.基于數據元素的查找

GTreeNode* find(const T&value)const

2.基于結點的查找

GTreeNode*find(TreeNode*node)const

基于數據元素值的查找
定義功能：find(node,value)--在node為根結點的樹中查找value所在的結點
數據結構--樹
基于結點的查找
定義功能:find(node,obj)--在node為根結點的樹中查找是否存在obj結點
數據結構--樹
樹中結點的插入操作
A.插入的方式
1.插入新結點

bool insert(TreeNode* node)

2.插入數據元素

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

分析
1.樹是非線性的，無法采用下標的形式定位數據元素
2.每一個樹結點都有唯一的前驅結點(父結點)
3.因此，必須先找到前驅結點，才能完成新結點的插入
數據結構--樹數據結構--樹
樹中結點的清除操作
void clear()--將樹中的所有結點清除(釋放堆中的結點)
清除操作功能的定義
free(node)--清除node為根結點的樹，釋放每一個結點
數據結構--樹
樹中結點的刪除操作
A.刪除方式
1.基于數據元素值的刪除

SharePointer>remove(const T&value)

2.基于結點的刪除

SharePointer>remove(TreeNode*node)

刪除操作成員函數的設計要點
1.將被刪結點所代表的子樹進行刪除
2.刪除函數返回一顆堆空間中的樹
3.具體返回值為指向樹的智能指針對象

刪除操作功能的定義
void remove(GTreeNode node,GTree& ret)--將node為根結點的子樹從原來的樹中刪除，ret作為子樹返回(ret指向堆空間的樹對象)
數據結構--樹

樹中屬性操作的實現
A.樹中結點的數目
定義功能:count(node)--在node為根結點的樹中統(tǒng)計結點數目
數據結構--樹
B.樹的高度
定義功能:height(node)--獲取node為根結點的樹的高度
數據結構--樹
C.樹的度數
定義功能:degree(node)--獲取node為根結點的樹的度數
數據結構--樹
D.樹的層次遍歷
設計思路：
1.在樹中定義一個游標(GTreeNode*)
2.在遍歷開始前將游標指向根結點(root())
3.獲取游標指向的數據元素
4.通過結點中的child成員移動游標
算法
1.原料：class LinkQueue
2.游標：LinkQueue::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 
    class GTree:public Tree
    {
    protected:
        LinkQueue *> m_queue;

        //基于數據元素值的查找，都是遍歷實現的
        GTreeNode* find(GTreeNode* node, const T& value)const
            {
              GTreeNode* ret = NULL;
              if(node != NULL)
              {
                  //如果根結點的就是目標結點
                  if(node->value == value)
                  {
                       return node;
                  }
                  else
                  {
                      //遍歷根節(jié)點的子結點
                      for(node->child.move(0); !node->child.end() && (ret == NULL); node->child.next())
                      {
                          //對每個子子結點進行查找
                          ret = find(node->child.current(), value);
                      }
                  }
              }
              return ret;
            }
        //基于結點得查找
        GTreeNode* find(GTreeNode* node, GTreeNode* obj)const
           {
             GTreeNode* 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* 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* node,GTree*& ret)
        {
            ret=new GTree();

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

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

            return ret;
        }

        int degree(GTreeNode* 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* 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* node)
        {
            bool ret=true;

            if(node!=NULL)//當結點不為空時
            {
                if(this->m_root==NULL)//如果此時的根結點為空
                {
                    node->parent=NULL;//node結點就是根結點
                    this->m_root=node;
                }
                else
                {
                    GTreeNode* np=find(node->parent);//在堆空間創(chuàng)建np指向node的父節(jié)點
                    if(np!=NULL)
                    {
                        GTreeNode* n=dynamic_cast*>(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* parent)
        {
            bool ret=true;

            GTreeNode* node=GTreeNode::NewNode();

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

                insert(node);
            }
            else
            {
                THROW_EXCEPTION(InvalidOperationException,"...");
            }

            return ret;
        }

        //刪除結點
        SharedPointer< Tree > remove(const T& value)
        {
            GTree* ret=NULL;

            GTreeNode* node=find(value);

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

            return ret;
        }

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

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

            return NULL;
        }

        //查找結點
        GTreeNode* find(const T& value)const
        {
            return find(root(),value);
        }

        GTreeNode* find(TreeNode* node)const
        {
            return find(root(),dynamic_cast*>(node));//強制類型轉換將TreeNode類型轉換為GTreeNode類型
        }//root對應的root的類型也應該一樣

        //根結點訪問函數
        GTreeNode* root()const
        {
            return dynamic_cast*>(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* 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* node=m_queue.front();
                m_queue.remove();//隊頭元素出隊列
                //將隊頭元素的子節(jié)點入隊
                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();
        }
    };
}

新聞標題：數據結構--樹
文章地址：http://weahome.cn/article/igddsp.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部