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

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

數(shù)據(jù)結(jié)構(gòu)之樹（三十四）-創(chuàng)新互聯(lián)

我們在前面學(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 ) 個(gè)結(jié)點(diǎn)組成的有限集合。如果n= 0，稱為空樹；如果n > 0，則：a> 有一個(gè)特定的稱之為根（root）的結(jié)點(diǎn)；b> 根結(jié)點(diǎn)只有直接后繼，但沒有直接前驅(qū)；c> 除根以外的其它結(jié)點(diǎn)劃分為 m( m >= 0 ) 個(gè)互不相交的有限集合T0, T1, … Tm-1，每個(gè)集合又是一棵樹，并且稱之為根的子樹（sub tree）。下來我們來看看樹的示意圖，如下所示

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

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

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

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

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

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

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

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

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

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

1、將元素插入樹中；

2、將元素從樹中刪除；

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

4、獲取樹的高度；

5、獲取樹的度；

6、清空樹中的元素；

7、 ......???


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

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

那么我們下來來看看那樹和結(jié)點(diǎn)抽象類的具體源碼是怎樣寫的

Tree.h 源碼

#ifndef?TREE_H
#define?TREE_H

#include?"TreeNode.h"
#include?"SharedPointer.h"

namespace?DTLib
{

template?
class?Tree?:?public?Object
{
protected:
????TreeNode*?m_root;
public:
????Tree()?{?m_root?=?NULL;?}
????virtual?bool?×××ert(TreeNode*?node)?=?0;
????virtual?bool?×××ert(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;
};

}

#endif?//?TREE_H

TreeNode.h 源碼

#ifndef?TREENODE_H
#define?TREENODE_H

#include?"Object.h"

namespace?DTLib
{

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

????TreeNode()
????{
????????parent?=?NULL;
????}

????virtual?~TreeNode()?=?0;
};

template?
TreeNode::~TreeNode()
{

}

}

#endif?//?TREENODE_H

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

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

設(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)的所有操作（增，刪，查，等）。

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

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

我們來看看通用樹結(jié)構(gòu)（框架）是怎樣創(chuàng)建的，源碼如下

GTree.h 源碼

#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
public:
????bool?×××ert(TreeNode*?node)
????{
????????bool?ret?=?true;
????????
????????return?ret;
????}

????bool?×××ert(const?T&?value,?TreeNode*?parent)
????{
????????bool?ret?=?true;

????????return?ret;
????}

????SharedPointer?>?remove(const?T&?value)
????{
????????return?NULL;
????}

????SharedPointer?>?remove(TreeNode*?node)
????{
????????return?NULL;
????}

????GTreeNode*?find(const?T&?value)?const
????{
????????return?NULL;
????}

????GTreeNode*?find(TreeNode*?node)?const
????{
????????return?NULL;
????}

????GTreeNode*?root()?const
????{
????????return?dynamic_cast*>(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?
class?GTreeNode?:?public?TreeNode
{
public:
????LinkList*>?child;
};

}

#endif?//?GTREENODE_H

我們在樹的設(shè)計(jì)中，為什么要在每個(gè)樹節(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ù)據(jù)結(jié)構(gòu)之樹（三十四）

下來我們就來一一的實(shí)現(xiàn)上面的查找、插入等操作

1、查找操作

查找的方式應(yīng)分為兩種：a> 基于數(shù)據(jù)元素值的查找：GTreeNode* find(const T& value) const；b> 基于結(jié)點(diǎn)的查找：GTreeNode* find(TreeNode* node) const。

?a> 基于數(shù)據(jù)元素值的查找，我們先在 protected 屬性中定義 find(node, value) 功能，在 node 為根結(jié)點(diǎn)的樹中查找 value 所在的結(jié)點(diǎn)，實(shí)現(xiàn)思路如下

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

b> 基于結(jié)點(diǎn)的查找，還是在 protected 屬性中定義 find(node, obj) 功能，在 node 為根結(jié)點(diǎn)的樹中查找是否存在 obj 結(jié)點(diǎn)，實(shí)現(xiàn)思路如下

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

具體查找相關(guān)源碼實(shí)現(xiàn)如下

#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
protected:
????GTreeNode*?find(GTreeNode*?node,?const?T&?value)?const
????{
????????GTreeNode*?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*?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;
????}
public:
????GTreeNode*?find(const?T&?value)?const
????{
????????return?find(root(),?value);
????}

????GTreeNode*?find(TreeNode*?node)?const
????{
????????return?find(root(),?dynamic_cast*>(node));
????}
????
????GTreeNode*?root()?const
????{
????????return?dynamic_cast*>(this->m_root);
????}
};

}

#endif?//?GTREE_H

2、插入操作

插入的方式應(yīng)分為兩種：a> 插入新結(jié)點(diǎn)：bool ×××ert(TreeNode* node)；b> 插入數(shù)據(jù)元素：bool ×××ert(const T& value, TreeNode* parent)。

那么如何在樹中指定新結(jié)點(diǎn)的位置呢？問題分析：a> 樹是非線性的，無法采用下標(biāo)的形式定位數(shù)據(jù)元素；b> 每一個(gè)樹結(jié)點(diǎn)都有唯一的前驅(qū)結(jié)點(diǎn)（父結(jié)點(diǎn)）；c> 因此，必須先找到前驅(qū)節(jié)點(diǎn)，才能完成新結(jié)點(diǎn)的插入。

?a> 新結(jié)點(diǎn)的插入，如下圖所示

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

插入新結(jié)點(diǎn)的流程如下圖所示

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

?b> 插入數(shù)據(jù)元素，流程如下圖所示

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

下來我們來看看具體源碼是怎么實(shí)現(xiàn)的

#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"
#include?"Exception.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
public:
????bool?×××ert(TreeNode*?node)
????{
????????bool?ret?=?true;

????????if(?node?!=?NULL?)
????????{
????????????if(?this->m_root?==?NULL?)
????????????{
????????????????node->parent?=?NULL;
????????????????this->m_root?=?node;
????????????}
????????????else
????????????{
????????????????GTreeNode*?np?=?find(node->parent);

????????????????if(?np?!=?NULL?)
????????????????{
????????????????????GTreeNode*?n?=?dynamic_cast*>(node);

????????????????????if(?np->child.find(n)?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*?parent)
????{
????????bool?ret?=?true;
????????GTreeNode*?node?=?GTreeNode::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?
#include?"GTree.h"

using?namespace?std;
using?namespace?DTLib;

int?main()
{
????GTree?t;
????GTreeNode*?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*?node?=?t.find(s[i]);

????????while(?node?!=?NULL?)
????????{
????????????cout?<value?<parent;
????????}

????????cout?<
運(yùn)行結(jié)果如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到已經(jīng)實(shí)現(xiàn)了之前定義的樹結(jié)構(gòu)。
3、清除操作
a> 定義：void clear()；將樹中的所有結(jié)點(diǎn)清除（釋放堆中的結(jié)點(diǎn)），樹中數(shù)據(jù)元素的清除如下所示
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
b> free(node)；清除 node 為根結(jié)點(diǎn)的樹，釋放樹中的每一個(gè)結(jié)點(diǎn)，實(shí)現(xiàn)思路如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
具體源碼實(shí)現(xiàn)如下
#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
protected:
????void?free(GTreeNode*?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?
#include?"GTree.h"

using?namespace?std;
using?namespace?DTLib;

int?main()
{
????GTree?t;
????GTreeNode*?node?=?NULL;
????GTreeNode?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*?node?=?t.find(s[i]);

????????while(?node?!=?NULL?)
????????{
????????????cout?<value?<parent;
????????}

????????cout?<
我們來看看結(jié)果
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到已經(jīng)清空了樹。但是此時(shí)存在一個(gè)問題，那便是我們在 main 函數(shù)中是在堆上值指定的數(shù)據(jù)元素，上面的清除操作也會將這個(gè)堆中的數(shù)據(jù)元素刪除掉。這必然會導(dǎo)致問題，那么對于樹中的結(jié)點(diǎn)來源于不同的存儲空間的話，此時(shí)我們應(yīng)如何判斷堆空間中的結(jié)點(diǎn)并釋放？問題分析：單憑內(nèi)存地址很難準(zhǔn)確判斷具體的存儲區(qū)域，只有堆空間的內(nèi)存需要主動(dòng)釋放（delete），清除操作時(shí)只需要對堆中的結(jié)點(diǎn)進(jìn)行釋放。
此時(shí)的解決方案：工廠模式。
?i. 在 GTreeNode 中增加保護(hù)成員變量 m_flag；
?ii. 將 GTreeNode 中的 operator new 重載為保護(hù)成員函數(shù)；
?iii. 提供工廠方法 GTreeNode* NewNode()；
 iv. 在工廠方法中 new 新結(jié)點(diǎn)并將 m_flag 設(shè)置為 true。
樹結(jié)點(diǎn)的工廠模式示例如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們來看看具體的源碼實(shí)現(xiàn)
#ifndef?GTREENODE_H
#define?GTREENODE_H

#include?"Tree.h"
#include?"LinkList.h"

namespace?DTLib
{

template?
class?GTreeNode?:?public?TreeNode
{
protected:
????bool?m_flag;

????GTreeNode(const?GTreeNode&);
????GTreeNode*?operator?=?(const?GTreeNode&);

????void*?operator?new(unsigned?int?size)?throw()
????{
????????return?Object::operator?new(size);
????}
public:
????LinkList*>?child;

????GTreeNode()
????{
????????m_flag?=?false;
????}

????bool?flag()
????{
????????return?m_flag;
????}

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

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

????????return?ret;
????}
};

}

#endif?//?GTREENODE_H
在上面的 delete node 操作時(shí)外面進(jìn)行 node->flag() 的判斷，如果為 true，我們再來進(jìn)行刪除。為例方便的進(jìn)行說明，我們在這塊加個(gè)調(diào)試語句，再來一個(gè) else 語句，里面打印出不同存儲區(qū)域的數(shù)據(jù)元素，我們來看看結(jié)果
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到此時(shí)除了我們自己在堆上指定的 A 之外，剩下的數(shù)據(jù)元素已經(jīng)全部被清除掉。
4、刪除操作
刪除的方式也分為兩種：a> 基于數(shù)據(jù)元素值的刪除：SharedPointer< Tree > remove(const T& value)；b> 基于結(jié)點(diǎn)的刪除：SharedPointer< Tree > remove(TreeNode* node)；
刪除操作成員函數(shù)的設(shè)計(jì)要點(diǎn)：1、將被刪結(jié)點(diǎn)所代表的子樹進(jìn)行刪除；2、刪除函數(shù)返回一顆堆空間的樹；3、具體返回值為指向樹的只能指針對象。樹中結(jié)點(diǎn)的刪除示意如下圖所示
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
如果當(dāng)我們需要從函數(shù)中返回堆中的對象時(shí)，使用智能指針（SharedPointer）作為函數(shù)的返回值。刪除操作功能的定義：void remove(GTreeNode* node, GTree*& ret)；將 node 為根結(jié)點(diǎn)的子樹從原來的樹中刪除，ret 作為子樹返回（ret 指向堆空間中的樹對象）。刪除功能函數(shù)的實(shí)現(xiàn)思路如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
具體源碼實(shí)現(xiàn)如下
#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"
#include?"Exception.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
protected:
????void?remove(GTreeNode*?node,?GTree*&?ret)
????{
????????ret?=?new?GTree();

????????if(?ret?!=?NULL?)
????????{
????????????if(?root()?==?node?)
????????????{
????????????????this->m_root?=?NULL;
????????????}
????????????else
????????????{
????????????????LinkList*>&?child?=?dynamic_cast*>(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?>?remove(const?T&?value)
????{
????????GTree*?ret?=?NULL;
????????GTreeNode*?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?>?remove(TreeNode*?node)
????{
????????GTree*?ret?=?NULL;

????????node?=?find(node);

????????if(?node?!=?NULL?)
????????{
????????????remove(dynamic_cast*>(node),?ret);

????????????m_queue.clear();
????????}
????????else
????????{
????????????THROW_EXCEPTION(InvalidParameterException,?"Parament?node?is?invalid?...");
????????}

????????return?ret;
????}
};

}

#endif?//?GTREE_H
我們來寫點(diǎn)測試代碼，刪除子樹 D，測試代碼如下
#include?
#include?"GTree.h"

using?namespace?std;
using?namespace?DTLib;

int?main()
{
????GTree?t;
????GTreeNode*?node?=?NULL;
????GTreeNode?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?>?p?=?t.remove(t.find('D'));
????t.remove(t.find('D'));

????const?char*?s?=?"KLFNMIJ";

????for(int?i=0;?i<7;?i++)
????{
????????TreeNode*?node?=?t.find(s[i]);

????????while(?node?!=?NULL?)
????????{
????????????cout?<value?<parent;
????????}

????????cout?<
我們來看看運(yùn)行結(jié)果
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到子樹 D 已經(jīng)被刪除了，如果我們想用這個(gè)刪除的子樹 D，該如何做呢？將上面的測試代碼中的注釋的那行放開，將下面的 remove 注釋掉，再將下面 for 循環(huán)中的 t.find(s[i]) 改為 p->find(s[i])，我們來看看運(yùn)行結(jié)果
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到打印出的是我們刪除的子樹 D。
5、其他屬性操作
a> 樹中結(jié)點(diǎn)的數(shù)目，功能定義：count(node)；在 node 為根結(jié)點(diǎn)的樹中統(tǒng)計(jì)結(jié)點(diǎn)數(shù)目，實(shí)現(xiàn)思路如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
樹的結(jié)點(diǎn)數(shù)目的計(jì)算示例如下：
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
b> 樹的高度，功能定義：height(node)；獲取 node 為根結(jié)點(diǎn)的樹的高度，實(shí)現(xiàn)思路如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
樹的高度計(jì)算示例如下：
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
c> 樹的度數(shù)，功能定義：degree(node)；獲取 node 為根結(jié)點(diǎn)的樹的度數(shù)，實(shí)現(xiàn)思路如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
樹的度計(jì)算示例
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
下來看看具體的源碼實(shí)現(xiàn)
#ifndef?GTREE_H
#define?GTREE_H

#include?"Tree.h"
#include?"GTreeNode.h"
#include?"Exception.h"

namespace?DTLib
{

template?
class?GTree?:?public?Tree
{
protected
????int?count(GTreeNode*?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*?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)?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?
測試代碼如下
#include?
#include?"GTree.h"

using?namespace?std;
using?namespace?DTLib;

int?main()
{
????GTree?t;
????GTreeNode*?node?=?NULL;
????GTreeNode?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?<
我們來看看運(yùn)行結(jié)果
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
6、層次遍歷
如何按層次遍歷通用樹結(jié)構(gòu)中的每一個(gè)數(shù)據(jù)元素呢？樹是非線性的數(shù)據(jù)結(jié)構(gòu)，樹的結(jié)點(diǎn)沒有固定的編號方式。那么我們就得提供一個(gè)新的需求，為通用樹結(jié)構(gòu)提供新的方法，能快速遍歷每一個(gè)結(jié)點(diǎn)。
設(shè)計(jì)思路（游標(biāo)）：a> 在樹中定義一個(gè)游標(biāo)（GTreeNode*）；b> 遍歷開始前將游標(biāo)指向根結(jié)點(diǎn)（root()）；c> 獲取游標(biāo)指向的數(shù)據(jù)元素；d> 通過結(jié)點(diǎn)中的 child 成員移動(dòng)游標(biāo)。提供一組遍歷相關(guān)的函數(shù)，按層次訪問樹中的數(shù)據(jù)元素。如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
層次遍歷算法：a> 原料：class LinkQueue；b> 游標(biāo)：LinkQueue::front()；c> 思想：i. begin() --> 將根節(jié)點(diǎn)壓入隊(duì)列中；ii. current() --> 訪問隊(duì)頭元素指向的數(shù)據(jù)元素；iii. next() --> 隊(duì)頭元素彈出，將對頭元素的孩子壓入隊(duì)列中（核心）；iv. end() --> 判斷隊(duì)列是否為空。層次遍歷算法示例如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
下來我們來看看具體的源碼實(shí)現(xiàn)
GTreeNode.h 源碼
#ifndef?GTREENODE_H
#define?GTREENODE_H

#include?"Tree.h"
#include?"LinkList.h"

namespace?DTLib
{

template?
class?GTreeNode?:?public?TreeNode
{
protected:
????bool?m_flag;

????GTreeNode(const?GTreeNode&);
????GTreeNode*?operator?=?(const?GTreeNode&);

????void*?operator?new(unsigned?int?size)?throw()
????{
????????return?Object::operator?new(size);
????}
public:
????LinkList*>?child;

????GTreeNode()
????{
????????m_flag?=?false;
????}

????bool?flag()
????{
????????return?m_flag;
????}

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

????????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?
class?GTree?:?public?Tree
{
protected:
????LinkQueue*>?m_queue;

????GTree(const?GTree&);
????GTree*?operator?=?(const?GTree&);
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*?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?
#include?"GTree.h"

using?namespace?std;
using?namespace?DTLib;

int?main()
{
????GTree?t;
????GTreeNode*?node?=?NULL;
????GTreeNode?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?<
運(yùn)行結(jié)果如下
數(shù)據(jù)結(jié)構(gòu)之樹（三十四）
我們看到已經(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)包含一個(gè)數(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í)行插入操作時(shí)必須指明結(jié)點(diǎn)間的父子關(guān)系；5、插入操作必須正確處理指向父結(jié)點(diǎn)的指針，插入數(shù)據(jù)元素時(shí)需要從堆空間中創(chuàng)建結(jié)點(diǎn)；6、銷毀結(jié)點(diǎn)時(shí)需要決定是否釋放對應(yīng)的內(nèi)存空間，工廠模式可用于“定制”堆空間中的結(jié)點(diǎn)，只有銷毀定制結(jié)點(diǎn)的時(shí)候需要進(jìn)行釋放；7、刪除操作必須完善處理父結(jié)點(diǎn)和子結(jié)點(diǎn)的關(guān)系，它的返回值為指向樹的智能指針對象，函數(shù)中返回堆中的對象時(shí)使用智能指針作為返回值；8、插入操作和刪除操作都依賴于查找操作；9、樹的結(jié)點(diǎn)沒有固定的編號方式，可以按照層次關(guān)系對樹中的結(jié)點(diǎn)進(jìn)行遍歷；10、通過游標(biāo)的思想設(shè)計(jì)遍歷成員函數(shù)，遍歷成員函數(shù)是相互依賴，相互配合的關(guān)系，遍歷算法的核心為隊(duì)列的使用。
            

            名稱欄目：數(shù)據(jù)結(jié)構(gòu)之樹（三十四）-創(chuàng)新互聯(lián)            

            文章位置：http://weahome.cn/article/ihsoe.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部