c的数据结构（数据结构--树）

1、树

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(); } }; }

,