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

我們在前面學習了排序相關(guān)的知識，從今天開始，我們來學習數(shù)據(jù)結(jié)構(gòu)中樹的相關(guān)東西。那么什么是樹呢？樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)。

創(chuàng)新互聯(lián)為您提適合企業(yè)的網(wǎng)站設計?讓您的網(wǎng)站在搜索引擎具有高度排名，讓您的網(wǎng)站具備超強的網(wǎng)絡競爭力！結(jié)合企業(yè)自身，進行網(wǎng)站設計及把握，最后結(jié)合企業(yè)文化和具體宗旨等，才能創(chuàng)作出一份性化解決方案。從網(wǎng)站策劃到網(wǎng)站設計制作、做網(wǎng)站， 我們的網(wǎng)頁設計師為您提供的解決方案。

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

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

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

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

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

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

1、將元素插入樹中；

2、將元素從樹中刪除；

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

4、獲取樹的高度；

5、獲取樹的度；

6、清空樹中的元素；

7、 ......???

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

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

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é)點的存儲結(jié)構(gòu)是怎么設計的，結(jié)構(gòu)圖如下

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

GTree（通用樹結(jié)構(gòu)）的實現(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

我們在樹的設計中，為什么要在每個樹節(jié)點中包含指向前驅(qū)結(jié)點的指針呢？從根結(jié)點到葉結(jié)點是非線性的數(shù)據(jù)結(jié)構(gòu)，但是從葉結(jié)點到根結(jié)點是線性的數(shù)據(jù)結(jié)構(gòu)（鏈表），結(jié)果如下

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

1、查找操作

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

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

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

具體查找相關(guān)源碼實現(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、插入操作

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

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

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

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

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

下來我們來看看具體源碼是怎么實現(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

我們來寫點測試代碼，看看前面實現(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;
}

運行結(jié)果如下

我們看到已經(jīng)實現(xiàn)了之前定義的樹結(jié)構(gòu)。

3、清除操作

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

b> free(node)；清除 node 為根結(jié)點的樹，釋放樹中的每一個結(jié)點，實現(xiàn)思路如下

具體源碼實現(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ù)元素刪除掉。這必然會導致問題，那么對于樹中的結(jié)點來源于不同的存儲空間的話，此時我們應如何判斷堆空間中的結(jié)點并釋放？問題分析：單憑內(nèi)存地址很難準確判斷具體的存儲區(qū)域，只有堆空間的內(nèi)存需要主動釋放（delete），清除操作時只需要對堆中的結(jié)點進行釋放。

此時的解決方案：工廠模式。

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

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

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

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

樹結(jié)點的工廠模式示例如下

我們來看看具體的源碼實現(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 操作時外面進行 node->flag() 的判斷，如果為 true，我們再來進行刪除。為例方便的進行說明，我們在這塊加個調(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é)點的刪除：SharedPointer< Tree<T> > remove(TreeNode<T>* node)；

刪除操作成員函數(shù)的設計要點：1、將被刪結(jié)點所代表的子樹進行刪除；2、刪除函數(shù)返回一顆堆空間的樹；3、具體返回值為指向樹的只能指針對象。樹中結(jié)點的刪除示意如下圖所示

如果當我們需要從函數(shù)中返回堆中的對象時，使用智能指針（SharedPointer）作為函數(shù)的返回值。刪除操作功能的定義：void remove(GTreeNode<T>* node, GTree<T>*& ret)；將 node 為根結(jié)點的子樹從原來的樹中刪除，ret 作為子樹返回（ret 指向堆空間中的樹對象）。刪除功能函數(shù)的實現(xiàn)思路如下

具體源碼實現(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

我們來寫點測試代碼，刪除子樹 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;
}

我們來看看運行結(jié)果

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

我們看到打印出的是我們刪除的子樹 D。

5、其他屬性操作

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

樹的結(jié)點數(shù)目的計算示例如下：

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

樹的高度計算示例如下：

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

樹的度計算示例

下來看看具體的源碼實現(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;
}

我們來看看運行結(jié)果

6、層次遍歷

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

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

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

下來我們來看看具體的源碼實現(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 的操作中也要加上相應的隊列的清除：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;
}

運行結(jié)果如下

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

網(wǎng)頁名稱：數(shù)據(jù)結(jié)構(gòu)之樹（三十四）-創(chuàng)新互聯(lián)
分享URL：http://www.bm7419.com/article4/ihsoe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、網(wǎng)站內(nèi)鏈、網(wǎng)站設計、標簽優(yōu)化、響應式網(wǎng)站、品牌網(wǎng)站建設

廣告

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