數(shù)據(jù)結(jié)構(gòu)之樹(shù)（三十四）

????????我們?cè)谇懊鎸W(xué)習(xí)了排序相關(guān)的知識(shí)，從今天開(kāi)始，我們來(lái)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中樹(shù)的相關(guān)東西。那么什么是樹(shù)呢？樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)。

????????樹(shù)是由 n( n >= 0 ) 個(gè)結(jié)點(diǎn)組成的有限集合。如果 n= 0，稱為空樹(shù)；如果 n > 0，則：a> 有一個(gè)特定的稱之為根（root）的結(jié)點(diǎn)；b> 根結(jié)點(diǎn)只有直接后繼，但沒(méi)有直接前驅(qū)；c> 除根以外的其它結(jié)點(diǎn)劃分為 m( m >= 0 ) 個(gè)互不相交的有限集合T₀, T₁, … T_m-1，每個(gè)集合又是一棵樹(shù)，并且稱之為根的子樹(shù)（sub tree）。下來(lái)我們來(lái)看看樹(shù)的示意圖，如下所示

????????下來(lái)我們來(lái)看一個(gè)樹(shù)中度的概念。它是指樹(shù)中的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及若干指向子樹(shù)的分支，及誒單擁有子樹(shù)的數(shù)目稱為結(jié)點(diǎn)的度。度為 0 的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，度不為 0 的結(jié)點(diǎn)稱為分支節(jié)點(diǎn)。樹(shù)的度定義為所有節(jié)點(diǎn)中度的最大值。下來(lái)來(lái)看一個(gè)數(shù)的度為 3 的示例，如下圖所示

????????下來(lái)來(lái)介紹下樹(shù)中的前驅(qū)和后繼。結(jié)點(diǎn)的直接后繼稱為該結(jié)點(diǎn)的孩子，相應(yīng)的，該結(jié)點(diǎn)稱為孩子的雙親；結(jié)點(diǎn)的孩子的孩子的 ... 稱為該結(jié)點(diǎn)的子孫，相應(yīng)的，該結(jié)點(diǎn)稱為子孫的祖先；同一個(gè)雙親的孩子之間互稱兄弟。下來(lái)來(lái)看看樹(shù)的前驅(qū)和后繼的結(jié)構(gòu)示意圖

????????我們來(lái)看看樹(shù)中結(jié)點(diǎn)的層次，如下圖所示

????????樹(shù)也有有序性，什么叫樹(shù)的有序性呢？如果樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左向右是有次序的，子樹(shù)間不能互換位置，則稱該樹(shù)為有序樹(shù)，否則為無(wú)序樹(shù)。示意圖如下圖所示

????????那么既然有樹(shù)的概念，就肯定有森林的概念。森林是由 n( n >= 0 ) 棵互不相交的樹(shù)組成的集合。那么在樹(shù)中肯定也有一些常用的操作，如下

????????1、將元素插入樹(shù)中；

????????2、將元素從樹(shù)中刪除；

????????3、獲取樹(shù)的結(jié)點(diǎn)數(shù)；

????????4、獲取樹(shù)的高度；

????????5、獲取樹(shù)的度；

????????6、清空樹(shù)中的元素；

????????7、 ......???

????????樹(shù)與結(jié)點(diǎn)的類關(guān)系可以如下表示

????????那么我們下來(lái)來(lái)看看那樹(shù)和結(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

????????下來(lái)我們來(lái)看看樹(shù)和結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是怎么設(shè)計(jì)的，結(jié)構(gòu)圖如下

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

????????GTree（通用樹(shù)結(jié)構(gòu)）的實(shí)現(xiàn)框架如下圖所示

????????我們來(lái)看看通用樹(shù)結(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

????????我們?cè)跇?shù)的設(shè)計(jì)中，為什么要在每個(gè)樹(shù)節(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é)果如下

????????下來(lái)我們就來(lái)一一的實(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)的樹(shù)中查找 value 所在的結(jié)點(diǎn)，實(shí)現(xiàn)思路如下

????????????b> 基于結(jié)點(diǎn)的查找，還是在 protected 屬性中定義 find(node, obj) 功能，在 node 為根結(jié)點(diǎn)的樹(shù)中查找是否存在 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)。

????????那么如何在樹(shù)中指定新結(jié)點(diǎn)的位置呢？問(wèn)題分析：a> 樹(shù)是非線性的，無(wú)法采用下標(biāo)的形式定位數(shù)據(jù)元素；b> 每一個(gè)樹(shù)結(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ù)元素，流程如下圖所示

????????下來(lái)我們來(lái)看看具體源碼是怎么實(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

??????? 我們來(lái)寫點(diǎn)測(cè)試代碼，看看前面實(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)了之前定義的樹(shù)結(jié)構(gòu)。

????????3、清除操作

????????a> 定義：void clear()；將樹(shù)中的所有結(jié)點(diǎn)清除（釋放堆中的結(jié)點(diǎn)），樹(shù)中數(shù)據(jù)元素的清除如下所示

???????? b> free(node)；清除 node 為根結(jié)點(diǎn)的樹(shù)，釋放樹(shù)中的每一個(gè)結(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

??????? 測(cè)試代碼如下

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

????????我們來(lái)看看結(jié)果

??????? 我們看到已經(jīng)清空了樹(shù)。但是此時(shí)存在一個(gè)問(wèn)題，那便是我們?cè)?main 函數(shù)中是在堆上值指定的數(shù)據(jù)元素，上面的清除操作也會(huì)將這個(gè)堆中的數(shù)據(jù)元素刪除掉。這必然會(huì)導(dǎo)致問(wèn)題，那么對(duì)于樹(shù)中的結(jié)點(diǎn)來(lái)源于不同的存儲(chǔ)空間的話，此時(shí)我們應(yīng)如何判斷堆空間中的結(jié)點(diǎn)并釋放？問(wèn)題分析：?jiǎn)螒{內(nèi)存地址很難準(zhǔn)確判斷具體的存儲(chǔ)區(qū)域，只有堆空間的內(nèi)存需要主動(dòng)釋放（delete），清除操作時(shí)只需要對(duì)堆中的結(jié)點(diǎn)進(jìn)行釋放。

????????此時(shí)的解決方案：工廠模式。

????????????i. 在 GTreeNode 中增加保護(hù)成員變量 m_flag；

????????????ii. 將 GTreeNode 中的 operator new 重載為保護(hù)成員函數(shù)；

????????????iii. 提供工廠方法 GTreeNode<T>* NewNode()；

??????????? iv. 在工廠方法中 new 新結(jié)點(diǎn)并將 m_flag 設(shè)置為 true。

????????樹(shù)結(jié)點(diǎn)的工廠模式示例如下

????????我們來(lái)看看具體的源碼實(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 操作時(shí)外面進(jìn)行 node->flag() 的判斷，如果為 true，我們?cè)賮?lái)進(jìn)行刪除。為例方便的進(jìn)行說(shuō)明，我們?cè)谶@塊加個(gè)調(diào)試語(yǔ)句，再來(lái)一個(gè) else 語(yǔ)句，里面打印出不同存儲(chǔ)區(qū)域的數(shù)據(jù)元素，我們來(lái)看看結(jié)果

????????我們看到此時(shí)除了我們自己在堆上指定的 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)所代表的子樹(shù)進(jìn)行刪除；2、刪除函數(shù)返回一顆堆空間的樹(shù)；3、具體返回值為指向樹(shù)的只能指針對(duì)象。樹(shù)中結(jié)點(diǎn)的刪除示意如下圖所示

????????如果當(dāng)我們需要從函數(shù)中返回堆中的對(duì)象時(shí)，使用智能指針（SharedPointer）作為函數(shù)的返回值。刪除操作功能的定義：void remove(GTreeNode<T>* node, GTree<T>*& ret)；將 node 為根結(jié)點(diǎn)的子樹(shù)從原來(lái)的樹(shù)中刪除，ret 作為子樹(shù)返回（ret 指向堆空間中的樹(shù)對(duì)象）。刪除功能函數(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

????????我們來(lái)寫點(diǎn)測(cè)試代碼，刪除子樹(shù) D，測(cè)試代碼如下

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

????????我們來(lái)看看運(yùn)行結(jié)果

????????我們看到子樹(shù) D 已經(jīng)被刪除了，如果我們想用這個(gè)刪除的子樹(shù) D，該如何做呢？將上面的測(cè)試代碼中的注釋的那行放開(kāi)，將下面的 remove 注釋掉，再將下面 for 循環(huán)中的 t.find(s[i]) 改為 p->find(s[i])，我們來(lái)看看運(yùn)行結(jié)果

????????我們看到打印出的是我們刪除的子樹(shù) D。

????????5、其他屬性操作

????????a> 樹(shù)中結(jié)點(diǎn)的數(shù)目，功能定義：count(node)；在 node 為根結(jié)點(diǎn)的樹(shù)中統(tǒng)計(jì)結(jié)點(diǎn)數(shù)目，實(shí)現(xiàn)思路如下

????????樹(shù)的結(jié)點(diǎn)數(shù)目的計(jì)算示例如下：

????????b> 樹(shù)的高度，功能定義：height(node)；獲取 node 為根結(jié)點(diǎn)的樹(shù)的高度，實(shí)現(xiàn)思路如下

????????樹(shù)的高度計(jì)算示例如下：

????????c> 樹(shù)的度數(shù)，功能定義：degree(node)；獲取 node 為根結(jié)點(diǎn)的樹(shù)的度數(shù)，實(shí)現(xiàn)思路如下

????????樹(shù)的度計(jì)算示例

????????下來(lái)看看具體的源碼實(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

????????測(cè)試代碼如下

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

????????我們來(lái)看看運(yùn)行結(jié)果

????????6、層次遍歷

????????如何按層次遍歷通用樹(shù)結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素呢？樹(shù)是非線性的數(shù)據(jù)結(jié)構(gòu)，樹(shù)的結(jié)點(diǎn)沒(méi)有固定的編號(hào)方式。那么我們就得提供一個(gè)新的需求，為通用樹(shù)結(jié)構(gòu)提供新的方法，能快速遍歷每一個(gè)結(jié)點(diǎn)。

????????設(shè)計(jì)思路（游標(biāo)）：a> 在樹(shù)中定義一個(gè)游標(biāo)（GTreeNode<T>*）；b> 遍歷開(kāi)始前將游標(biāo)指向根結(jié)點(diǎn)（root()）；c> 獲取游標(biāo)指向的數(shù)據(jù)元素；d> 通過(guò)結(jié)點(diǎn)中的 child 成員移動(dòng)游標(biāo)。提供一組遍歷相關(guān)的函數(shù)，按層次訪問(wèn)樹(shù)中的數(shù)據(jù)元素。如下

????????層次遍歷算法：a> 原料：class LinkQueue<T>；b> 游標(biāo)：LinkQueue<T>::front()；c> 思想：i. begin() --> 將根節(jié)點(diǎn)壓入隊(duì)列中；ii. current() --> 訪問(wèn)隊(duì)頭元素指向的數(shù)據(jù)元素；iii. next() --> 隊(duì)頭元素彈出，將對(duì)頭元素的孩子壓入隊(duì)列中（核心）；iv. end() --> 判斷隊(duì)列是否為空。層次遍歷算法示例如下

????????下來(lái)我們來(lái)看看具體的源碼實(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(); 測(cè)試代碼如下

#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)將之前的樹(shù)結(jié)構(gòu)層次遍歷了一遍。通過(guò)對(duì)樹(shù)的學(xué)習(xí)，總結(jié)如下：1、樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)擁有唯一前驅(qū)（父結(jié)點(diǎn)）和若干后繼（子結(jié)點(diǎn)）；2、樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及若干指向其他結(jié)點(diǎn)的指針，樹(shù)與結(jié)點(diǎn)在程序中表現(xiàn)為特殊的數(shù)據(jù)類型；3、基于數(shù)據(jù)元素的查找可判斷值是否存在于樹(shù)中，基于結(jié)點(diǎn)的查找可判斷樹(shù)中是否存在指定結(jié)點(diǎn)；4、插入操作是構(gòu)建樹(shù)的唯一操作，執(zhí)行插入操作時(shí)必須指明結(jié)點(diǎn)間的父子關(guān)系；5、插入操作必須正確處理指向父結(jié)點(diǎn)的指針，插入數(shù)據(jù)元素時(shí)需要從堆空間中創(chuàng)建結(jié)點(diǎn)；6、銷毀結(jié)點(diǎn)時(shí)需要決定是否釋放對(duì)應(yīng)的內(nèi)存空間，工廠模式可用于“定制”堆空間中的結(jié)點(diǎn)，只有銷毀定制結(jié)點(diǎn)的時(shí)候需要進(jìn)行釋放；7、刪除操作必須完善處理父結(jié)點(diǎn)和子結(jié)點(diǎn)的關(guān)系，它的返回值為指向樹(shù)的智能指針對(duì)象，函數(shù)中返回堆中的對(duì)象時(shí)使用智能指針作為返回值；8、插入操作和刪除操作都依賴于查找操作；9、樹(shù)的結(jié)點(diǎn)沒(méi)有固定的編號(hào)方式，可以按照層次關(guān)系對(duì)樹(shù)中的結(jié)點(diǎn)進(jìn)行遍歷；10、通過(guò)游標(biāo)的思想設(shè)計(jì)遍歷成員函數(shù)，遍歷成員函數(shù)是相互依賴，相互配合的關(guān)系，遍歷算法的核心為隊(duì)列的使用。