A .樹的屬性及介紹

樹是一種非線性的數據結構

樹是由n(n>=0)個結點組成的有限集合

1.如果n=0,稱為空樹

2.如果n>0，則有一個特定的稱之為根的結點，跟結點隻有直接後繼，但沒有直接前驅，除根以外的其他結點劃分為m(m>=0)個互不相交的有限集合T0,T1,…,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹

3.樹中度的概念

a.樹的結點包含一個數據及若幹指向子樹的分支

b.結點擁有的子樹數目稱為結點的度–度為0的結點稱為葉節點，度不為0的結點稱為分支結點

c.樹的度定義為所有結點中度的最大值

4.樹中的前驅和後繼

a.結點的直接後繼稱為該結點的孩子–相應的，該結點稱為孩子的雙親

b.結點的孩子的孩子的…稱為該結點的子孫–相應的,該結點稱為子孫的祖先

c.同一個雙親的孩子之間互稱為兄弟

5.樹中結點的層次

樹中結點的最大層次稱為樹的深度或高度

6.樹的有序性

如果樹中結點的各子樹從左向右是有次序的，子樹件不能互換位置，則稱該樹為有序樹，否則為無序樹

7.森林的概念

森林是由n(n>=0)棵互不相交的樹組成的集合

樹的實現

template <typename T> class Tree: public Object { protected: TreeNode<T>* m_root; public: Tree(){m_root=NULL}; //插入結點 virtual bool insert(TreeNode<T>* node)=0; virtual bool insert(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；//清空樹 }；

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

【領QT開發教程學習資料，點擊→「鍊接」」←莬費領取，先碼住不迷路~】

template <typename T> class TreeNode:public Object { T value; TreeNode<T>* parent; TreeNode() { parent=NULL; } virtual ~TreeNode()=0; };

樹與結點的關系

B. 樹的各種實現

a.樹和結點的存儲結構設計

設計要點：

1.GTree為通用樹結構，每個結點可以存在多個後繼結點

2.GTreeNode能夠包含任意多指向後繼結點的指針

3.實現樹結構的所有操作(增，删，查，等)

GTreeNode設計與實現

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

GTree的設計與實現

template <typename T> class GTree :public Tree<T> { };

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

template <typename T> class GTreeNode:public TreeNode<T> { public: LinkList<GTreeNode<T>*>child;//child成員為單鍊表 static GTreeNode<T>* NewNode() { GTreeNode<T>* ret=new GTreeNode<T>(); if(ret!=NULL) { ret->m_flag=true; } return ret; } };

每個樹結點在包含指向前驅結點的指針的原因是

1.根結點==》葉結點:非線性數據結構

2.葉結點==》根結點:線性數據結構

樹中結點的查找操作

A.查找的方式

1.基于數據元素的查找

GTreeNode<T>* find(const T&value)const

2.基于結點的查找

GTreeNode<T>*find(TreeNode<T>*node)const

基于數據元素值的查找

定義功能：find(node,value)–在node為根結點的樹中查找value所在的結點

基于結點的查找

定義功能:find(node,obj)–在node為根結點的樹中查找是否存在obj結點

樹中結點的插入操作

A.插入的方式

1.插入新結點

bool insert(TreeNode<T>* node)

2.插入數據元素

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

分析

1.樹是非線性的，無法采用下标的形式定位數據元素

2.每一個樹結點都有唯一的前驅結點(父結點)

3.因此，必須先找到前驅結點，才能完成新結點的插入

樹中結點的清除操作

void clear()–将樹中的所有結點清除(釋放堆中的結點)

清除操作功能的定義

free(node)–清除node為根結點的樹，釋放每一個結點

樹中結點的删除操作

A.删除方式

1.基于數據元素值的删除

SharePointer<Tree<T>>remove(const T&value)

2.基于結點的删除

SharePointer<Tree<T>>remove(TreeNode<T>*node)

删除操作成員函數的設計要點

1.将被删結點所代表的子樹進行删除

2.删除函數返回一顆堆空間中的樹

3.具體返回值為指向樹的智能指針對象

删除操作功能的定義

void remove(GTreeNode<T>* node,GTree<T>*& ret)–将node為根結點的子樹從原來的樹中删除，ret作為子樹返回(ret指向堆空間的樹對象)

樹中屬性操作的實現

A.樹中結點的數目

定義功能:count(node)–在node為根結點的樹中統計結點數目

B.樹的高度

定義功能:height(node)–獲取node為根結點的樹的高度

C.樹的度數

定義功能:degree(node)–獲取node為根結點的樹的度數

D.樹的層次遍曆

設計思路：

1.在樹中定義一個遊标(GTreeNode<T>*)

2.在遍曆開始前将遊标指向根結點(root())

3.獲取遊标指向的數據元素

4.通過結點中的child成員移動遊标

算法

1.原料：class LinkQueue<T>

2.遊标：LinkQueue<T>::front()

3.思想

a.begin()=>将根結點壓入隊列中

b.current()=>訪問對頭元素指向的數據元素

c.next()=>隊頭元素彈出，将隊頭元素的孩子壓入隊列中

d.end()=>判斷隊列是否為空

#include "TreeNode.h" #include "GTreeNode.h" #include "Exception.h" #include "LinkQueue.h" namespace MyLib { template <typename T> class GTree:public Tree<T> { protected: LinkQueue <GTreeNode<T>*> m_queue; //基于數據元素值的查找，都是遍曆實現的 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; } void free(GTreeNode<T>* node) { if(node!=NULL) { for(node->child.move(0); !node->child.end(); node->child.next()) { free(node->child.current()); } if(node->flag()) { delete node; } } } /* * 删除操作成員函數的設計要點 * 将被删除結點所代表的子樹進行删除 * 删除函數返回一顆堆空間中的樹 * 具體返回值為指向樹的智能指針對象 */ void remove(GTreeNode<T>* node,GTree<T>*& ret) { ret=new GTree<T>(); if(ret==NULL) { THROW_EXCEPTION(NoEoughMemoryException,"..."); } else { if(root()!=node) { //獲取删除結點的父結點的子結點鍊表 LinkList<GTreeNode<T>*>& child=dynamic_cast<GTreeNode<T>*>(node->parent)->child; child.remove(child.find(node)); //從鍊表中删除結點 node->parent=NULL;//結點的父結點置NULL } else { this->m_root=NULL; } } } 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 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; } 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; } public: //插入結點 //以結點的方式插入 bool insert(TreeNode<T>* node) { bool ret=true; if(node!=NULL)//當結點不為空時 { if(this->m_root==NULL)//如果此時的根結點為空 { node->parent=NULL;//node結點就是根結點 this->m_root=node; } else { GTreeNode<T>* np=find(node->parent);//在堆空間創建np指向node的父節點 if(np!=NULL) { GTreeNode<T>* n=dynamic_cast<GTreeNode<T>*>(node);//noded的類型為TreeNode,需要将其強制轉換為GTreeNode if(np->child.find(n)<0) { ret=np->child.insert(n); } } else { THROW_EXCEPTION(InvalidOperationException,"..."); } } } else { THROW_EXCEPTION(InvalidOperationException,"..."); } return ret; } bool insert(const T& value, TreeNode<T>* parent) { bool ret=true; GTreeNode<T>* node=GTreeNode<T>::NewNode(); if(node!=NULL) { node->value=value; node->parent=parent; insert(node); } else { THROW_EXCEPTION(InvalidOperationException,"..."); } return ret; } //删除結點 SharedPointer< Tree<T> > remove(const T& value) { GTree<T>* ret=NULL; GTreeNode<T>* node=find(value); if(node!=NULL) { remove(node,ret); } else { THROW_EXCEPTION(InvalidOperationException,"..."); } 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); } else { THROW_EXCEPTION(InvalidOperationException,"..."); } return NULL; } //查找結點 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));//強制類型轉換将TreeNode類型轉換為GTreeNode類型 }//root對應的root的類型也應該一樣 //根結點訪問函數 GTreeNode<T>* root()const { return dynamic_cast<GTreeNode<T>*>(this->m_root); } //樹的度訪問函數 int degree()const { return degree(root()); } //樹的高度訪問函數 int height()const { return height(root()); } //樹的結點數目訪問函數 int count()const { return count(root()); } //清空樹 void clear() { free(root()); this->m_root=NULL; } //樹中結點的遍曆 //樹是一種非線性的數據結構，遍曆樹中結點可以采用遊标的方式。 //A、在樹中定義一個遊标（GTreeNode<T>* node） //B、遍曆開始前将遊标指向根結點 //C、獲取遊标指向的數據元素 //D、通過結點中的child成員移動遊标 bool begin() { bool ret=(root()!=NULL); if(ret) { m_queue.clear();//清空隊列 m_queue.add(root());//将根結點加入隊列 } return ret; } bool end() { return (m_queue.length()==0); } bool next() { bool ret=(m_queue.length()>0); { GTreeNode<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(InvalidOperationException,"..."); } } ~GTree() { clear(); } }; }

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!