我們在前面學(xué)習(xí)了排序相關(guān)的知識,從今天開始,我們來學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中樹的相關(guān)東西。那么什么是樹呢?樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)。
創(chuàng)新互聯(lián)為您提適合企業(yè)的網(wǎng)站設(shè)計(jì)?讓您的網(wǎng)站在搜索引擎具有高度排名,讓您的網(wǎng)站具備超強(qiáng)的網(wǎng)絡(luò)競爭力!結(jié)合企業(yè)自身,進(jìn)行網(wǎng)站設(shè)計(jì)及把握,最后結(jié)合企業(yè)文化和具體宗旨等,才能創(chuàng)作出一份性化解決方案。從網(wǎng)站策劃到網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站, 我們的網(wǎng)頁設(shè)計(jì)師為您提供的解決方案。樹是由 n( n >= 0 ) 個結(jié)點(diǎn)組成的有限集合。如果n= 0,稱為空樹;如果n > 0,則:a> 有一個特定的稱之為根(root)的結(jié)點(diǎn);b> 根結(jié)點(diǎn)只有直接后繼,但沒有直接前驅(qū);c> 除根以外的其它結(jié)點(diǎn)劃分為 m( m >= 0 ) 個互不相交的有限集合T0, T1, … Tm-1,每個集合又是一棵樹,并且稱之為根的子樹(sub tree)。下來我們來看看樹的示意圖,如下所示
下來我們來看一個樹中度的概念。它是指樹中的結(jié)點(diǎn)包含一個數(shù)據(jù)及若干指向子樹的分支,及誒單擁有子樹的數(shù)目稱為結(jié)點(diǎn)的度。度為 0 的結(jié)點(diǎn)稱為葉結(jié)點(diǎn),度不為 0 的結(jié)點(diǎn)稱為分支節(jié)點(diǎn)。樹的度定義為所有節(jié)點(diǎn)中度的大值。下來來看一個數(shù)的度為 3 的示例,如下圖所示
下來來介紹下樹中的前驅(qū)和后繼。結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子,相應(yīng)的,該結(jié)點(diǎn)稱為孩子的雙親;結(jié)點(diǎn)的孩子的孩子的 ... 稱為該結(jié)點(diǎn)的子孫,相應(yīng)的,該結(jié)點(diǎn)稱為子孫的祖先;同一個雙親的孩子之間互稱兄弟。下來來看看樹的前驅(qū)和后繼的結(jié)構(gòu)示意圖
我們來看看樹中結(jié)點(diǎn)的層次,如下圖所示
樹也有有序性,什么叫樹的有序性呢?如果樹中結(jié)點(diǎn)的各子樹從左向右是有次序的,子樹間不能互換位置,則稱該樹為有序樹,否則為無序樹。示意圖如下圖所示
那么既然有樹的概念,就肯定有森林的概念。森林是由 n( n >= 0 ) 棵互不相交的樹組成的集合。那么在樹中肯定也有一些常用的操作,如下
1、將元素插入樹中;
2、將元素從樹中刪除;
3、獲取樹的結(jié)點(diǎn)數(shù);
4、獲取樹的高度;
5、獲取樹的度;
6、清空樹中的元素;
7、 ......???
樹與結(jié)點(diǎn)的類關(guān)系可以如下表示
那么我們下來來看看那樹和結(jié)點(diǎn)抽象類的具體源碼是怎樣寫的
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
下來我們來看看樹和結(jié)點(diǎn)的存儲結(jié)構(gòu)是怎么設(shè)計(jì)的,結(jié)構(gòu)圖如下
設(shè)計(jì)要點(diǎn):1、GTree 為通用的樹結(jié)構(gòu),每個結(jié)點(diǎn)可以存在多個后繼結(jié)點(diǎn);2、GTreeNode 能夠包含任意多指向后繼結(jié)點(diǎn)的指針;3、實(shí)現(xiàn)樹結(jié)構(gòu)的所有操作(增,刪,查,等)。
GTree(通用樹結(jié)構(gòu))的實(shí)現(xiàn)框架如下圖所示
我們來看看通用樹結(jié)構(gòu)(框架)是怎樣創(chuàng)建的,源碼如下
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
我們在樹的設(shè)計(jì)中,為什么要在每個樹節(jié)點(diǎn)中包含指向前驅(qū)結(jié)點(diǎn)的指針呢?從根結(jié)點(diǎn)到葉結(jié)點(diǎn)是非線性的數(shù)據(jù)結(jié)構(gòu),但是從葉結(jié)點(diǎn)到根結(jié)點(diǎn)是線性的數(shù)據(jù)結(jié)構(gòu)(鏈表),結(jié)果如下
下來我們就來一一的實(shí)現(xiàn)上面的查找、插入等操作
1、查找操作
查找的方式應(yīng)分為兩種:a> 基于數(shù)據(jù)元素值的查找:GTreeNode<T>* find(const T& value) const;b> 基于結(jié)點(diǎn)的查找:GTreeNode<T>* find(TreeNode<T>* node) const。
?a> 基于數(shù)據(jù)元素值的查找,我們先在 protected 屬性中定義 find(node, value) 功能,在 node 為根結(jié)點(diǎn)的樹中查找 value 所在的結(jié)點(diǎn),實(shí)現(xiàn)思路如下
b> 基于結(jié)點(diǎn)的查找,還是在 protected 屬性中定義 find(node, obj) 功能,在 node 為根結(jié)點(diǎn)的樹中查找是否存在 obj 結(jié)點(diǎn),實(shí)現(xiàn)思路如下
具體查找相關(guān)源碼實(shí)現(xiàn)如下
#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、插入操作
插入的方式應(yīng)分為兩種:a> 插入新結(jié)點(diǎn):bool ×××ert(TreeNode<T>* node);b> 插入數(shù)據(jù)元素:bool ×××ert(const T& value, TreeNode<T>* parent)。
那么如何在樹中指定新結(jié)點(diǎn)的位置呢?問題分析:a> 樹是非線性的,無法采用下標(biāo)的形式定位數(shù)據(jù)元素;b> 每一個樹結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)(父結(jié)點(diǎn));c> 因此,必須先找到前驅(qū)節(jié)點(diǎn),才能完成新結(jié)點(diǎn)的插入。
?a> 新結(jié)點(diǎn)的插入,如下圖所示
插入新結(jié)點(diǎn)的流程如下圖所示
?b> 插入數(shù)據(jù)元素,流程如下圖所示
下來我們來看看具體源碼是怎么實(shí)現(xiàn)的
#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
我們來寫點(diǎn)測試代碼,看看前面實(shí)現(xiàn)的查找和插入代碼是否正確
#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; }
運(yùn)行結(jié)果如下
我們看到已經(jīng)實(shí)現(xiàn)了之前定義的樹結(jié)構(gòu)。
3、清除操作
a> 定義:void clear();將樹中的所有結(jié)點(diǎn)清除(釋放堆中的結(jié)點(diǎn)),樹中數(shù)據(jù)元素的清除如下所示
b> free(node);清除 node 為根結(jié)點(diǎn)的樹,釋放樹中的每一個結(jié)點(diǎn),實(shí)現(xiàn)思路如下
具體源碼實(shí)現(xiàn)如下
#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; }
我們來看看結(jié)果
我們看到已經(jīng)清空了樹。但是此時存在一個問題,那便是我們在 main 函數(shù)中是在堆上值指定的數(shù)據(jù)元素,上面的清除操作也會將這個堆中的數(shù)據(jù)元素刪除掉。這必然會導(dǎo)致問題,那么對于樹中的結(jié)點(diǎn)來源于不同的存儲空間的話,此時我們應(yīng)如何判斷堆空間中的結(jié)點(diǎn)并釋放?問題分析:單憑內(nèi)存地址很難準(zhǔn)確判斷具體的存儲區(qū)域,只有堆空間的內(nèi)存需要主動釋放(delete),清除操作時只需要對堆中的結(jié)點(diǎn)進(jìn)行釋放。
此時的解決方案:工廠模式。
?i. 在 GTreeNode 中增加保護(hù)成員變量 m_flag;
?ii. 將 GTreeNode 中的 operator new 重載為保護(hù)成員函數(shù);
?iii. 提供工廠方法 GTreeNode<T>* NewNode();
iv. 在工廠方法中 new 新結(jié)點(diǎn)并將 m_flag 設(shè)置為 true。
樹結(jié)點(diǎn)的工廠模式示例如下
我們來看看具體的源碼實(shí)現(xiàn)
#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 操作時外面進(jìn)行 node->flag() 的判斷,如果為 true,我們再來進(jìn)行刪除。為例方便的進(jìn)行說明,我們在這塊加個調(diào)試語句,再來一個 else 語句,里面打印出不同存儲區(qū)域的數(shù)據(jù)元素,我們來看看結(jié)果
我們看到此時除了我們自己在堆上指定的 A 之外,剩下的數(shù)據(jù)元素已經(jīng)全部被清除掉。
4、刪除操作
刪除的方式也分為兩種:a> 基于數(shù)據(jù)元素值的刪除:SharedPointer< Tree<T> > remove(const T& value);b> 基于結(jié)點(diǎn)的刪除:SharedPointer< Tree<T> > remove(TreeNode<T>* node);
刪除操作成員函數(shù)的設(shè)計(jì)要點(diǎn):1、將被刪結(jié)點(diǎn)所代表的子樹進(jìn)行刪除;2、刪除函數(shù)返回一顆堆空間的樹;3、具體返回值為指向樹的只能指針對象。樹中結(jié)點(diǎn)的刪除示意如下圖所示
如果當(dāng)我們需要從函數(shù)中返回堆中的對象時,使用智能指針(SharedPointer)作為函數(shù)的返回值。刪除操作功能的定義:void remove(GTreeNode<T>* node, GTree<T>*& ret);將 node 為根結(jié)點(diǎn)的子樹從原來的樹中刪除,ret 作為子樹返回(ret 指向堆空間中的樹對象)。刪除功能函數(shù)的實(shí)現(xiàn)思路如下
具體源碼實(shí)現(xiàn)如下
#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
我們來寫點(diǎn)測試代碼,刪除子樹 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; }
我們來看看運(yùn)行結(jié)果
我們看到子樹 D 已經(jīng)被刪除了,如果我們想用這個刪除的子樹 D,該如何做呢?將上面的測試代碼中的注釋的那行放開,將下面的 remove 注釋掉,再將下面 for 循環(huán)中的 t.find(s[i]) 改為 p->find(s[i]),我們來看看運(yùn)行結(jié)果
我們看到打印出的是我們刪除的子樹 D。
5、其他屬性操作
a> 樹中結(jié)點(diǎn)的數(shù)目,功能定義:count(node);在 node 為根結(jié)點(diǎn)的樹中統(tǒng)計(jì)結(jié)點(diǎn)數(shù)目,實(shí)現(xiàn)思路如下
樹的結(jié)點(diǎn)數(shù)目的計(jì)算示例如下:
b> 樹的高度,功能定義:height(node);獲取 node 為根結(jié)點(diǎn)的樹的高度,實(shí)現(xiàn)思路如下
樹的高度計(jì)算示例如下:
c> 樹的度數(shù),功能定義:degree(node);獲取 node 為根結(jié)點(diǎn)的樹的度數(shù),實(shí)現(xiàn)思路如下
樹的度計(jì)算示例
下來看看具體的源碼實(shí)現(xiàn)
#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; }
我們來看看運(yùn)行結(jié)果
6、層次遍歷
如何按層次遍歷通用樹結(jié)構(gòu)中的每一個數(shù)據(jù)元素呢?樹是非線性的數(shù)據(jù)結(jié)構(gòu),樹的結(jié)點(diǎn)沒有固定的編號方式。那么我們就得提供一個新的需求,為通用樹結(jié)構(gòu)提供新的方法,能快速遍歷每一個結(jié)點(diǎn)。
設(shè)計(jì)思路(游標(biāo)):a> 在樹中定義一個游標(biāo)(GTreeNode<T>*);b> 遍歷開始前將游標(biāo)指向根結(jié)點(diǎn)(root());c> 獲取游標(biāo)指向的數(shù)據(jù)元素;d> 通過結(jié)點(diǎn)中的 child 成員移動游標(biāo)。提供一組遍歷相關(guān)的函數(shù),按層次訪問樹中的數(shù)據(jù)元素。如下
層次遍歷算法:a> 原料:class LinkQueue<T>;b> 游標(biāo):LinkQueue<T>::front();c> 思想:i. begin() --> 將根節(jié)點(diǎn)壓入隊(duì)列中;ii. current() --> 訪問隊(duì)頭元素指向的數(shù)據(jù)元素;iii. next() --> 隊(duì)頭元素彈出,將對頭元素的孩子壓入隊(duì)列中(核心);iv. end() --> 判斷隊(duì)列是否為空。層次遍歷算法示例如下
下來我們來看看具體的源碼實(shí)現(xiàn)
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 的操作中也要加上相應(yīng)的隊(duì)列的清除: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; }
運(yùn)行結(jié)果如下
我們看到已經(jīng)將之前的樹結(jié)構(gòu)層次遍歷了一遍。通過對樹的學(xué)習(xí),總結(jié)如下:1、樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),結(jié)點(diǎn)擁有唯一前驅(qū)(父結(jié)點(diǎn))和若干后繼(子結(jié)點(diǎn));2、樹的結(jié)點(diǎn)包含一個數(shù)據(jù)及若干指向其他結(jié)點(diǎn)的指針,樹與結(jié)點(diǎn)在程序中表現(xiàn)為特殊的數(shù)據(jù)類型;3、基于數(shù)據(jù)元素的查找可判斷值是否存在于樹中,基于結(jié)點(diǎn)的查找可判斷樹中是否存在指定結(jié)點(diǎn);4、插入操作是構(gòu)建樹的唯一操作,執(zhí)行插入操作時必須指明結(jié)點(diǎn)間的父子關(guān)系;5、插入操作必須正確處理指向父結(jié)點(diǎn)的指針,插入數(shù)據(jù)元素時需要從堆空間中創(chuàng)建結(jié)點(diǎn);6、銷毀結(jié)點(diǎn)時需要決定是否釋放對應(yīng)的內(nèi)存空間,工廠模式可用于“定制”堆空間中的結(jié)點(diǎn),只有銷毀定制結(jié)點(diǎn)的時候需要進(jìn)行釋放;7、刪除操作必須完善處理父結(jié)點(diǎn)和子結(jié)點(diǎn)的關(guān)系,它的返回值為指向樹的智能指針對象,函數(shù)中返回堆中的對象時使用智能指針作為返回值;8、插入操作和刪除操作都依賴于查找操作;9、樹的結(jié)點(diǎn)沒有固定的編號方式,可以按照層次關(guān)系對樹中的結(jié)點(diǎn)進(jìn)行遍歷;10、通過游標(biāo)的思想設(shè)計(jì)遍歷成員函數(shù),遍歷成員函數(shù)是相互依賴,相互配合的關(guān)系,遍歷算法的核心為隊(duì)列的使用。
網(wǎng)頁名稱:數(shù)據(jù)結(jié)構(gòu)之樹(三十四)-創(chuàng)新互聯(lián)
分享URL:http://www.muchs.cn/article4/ihsoe.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供全網(wǎng)營銷推廣、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)、標(biāo)簽優(yōu)化、響應(yīng)式網(wǎng)站、品牌網(wǎng)站建設(shè)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)