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)棵互不相交的树组成的集合
创新互联坚信：善待客户，将会成为终身客户。我们能坚持多年，是因为我们一直可值得信赖。我们从不忽悠初访客户，我们用心做好本职工作，不忘初心，方得始终。10多年网站建设经验创新互联是成都老牌网站营销服务商,为您提供成都网站制作、做网站、网站设计、H5高端网站建设、网站制作、高端网站设计、小程序设计服务,给众多知名企业提供过好品质的建站服务。
树的实现
template
class Tree: public Object
{
protected:
TreeNode* m_root;
public:
Tree(){m_root=NULL};
//插入结点
virtual bool insert(TreeNode* node)=0;
virtual bool insert(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；//清空树
}； 树中的结点也表示为一种特殊的数据类型
template
class TreeNode:public Object
{
T value;
TreeNode* parent;
TreeNode()
{
parent=NULL;
}
virtual ~TreeNode()=0;
}; 树与结点的关系
B. 树的各种实现
a.树和结点的存储结构设计
设计要点：
1.GTree为通用树结构，每个结点可以存在多个后继结点
2.GTreeNode能够包含任意多指向后继结点的指针
3.实现树结构的所有操作(增，删，查，等)
GTreeNode设计与实现
template
class GTreeNode:public TreeNode
{
public:
LinkList*>child;
}; GTree的设计与实现
template
class GTree :public Tree
{
}; GTree(通用树结构)的实现架构
template
class GTreeNode:public TreeNode
{
public:
LinkList*>child;//child成员为单链表
static GTreeNode* NewNode()
{
GTreeNode* ret=new GTreeNode();
if(ret!=NULL)
{
ret->m_flag=true;
}
return ret;
}
}; 每个树结点在包含指向前驱结点的指针的原因是
1.根结点==》叶结点:非线性数据结构
2.叶结点==》根结点:线性数据结构
树中结点的查找操作
A.查找的方式
1.基于数据元素的查找
GTreeNode* find(const T&value)const 2.基于结点的查找
GTreeNode*find(TreeNode*node)const 基于数据元素值的查找
定义功能：find(node,value)--在node为根结点的树中查找value所在的结点
基于结点的查找
定义功能:find(node,obj)--在node为根结点的树中查找是否存在obj结点
树中结点的插入操作
A.插入的方式
1.插入新结点
bool insert(TreeNode* node) 2.插入数据元素
bool insert(const T&value,TreeNode* parent) 分析
1.树是非线性的，无法采用下标的形式定位数据元素
2.每一个树结点都有唯一的前驱结点(父结点)
3.因此，必须先找到前驱结点，才能完成新结点的插入
树中结点的清除操作
void clear()--将树中的所有结点清除(释放堆中的结点)
清除操作功能的定义
free(node)--清除node为根结点的树，释放每一个结点
树中结点的删除操作
A.删除方式
1.基于数据元素值的删除
SharePointer>remove(const T&value) 2.基于结点的删除
SharePointer>remove(TreeNode*node) 删除操作成员函数的设计要点
1.将被删结点所代表的子树进行删除
2.删除函数返回一颗堆空间中的树
3.具体返回值为指向树的智能指针对象
删除操作功能的定义
void remove(GTreeNode
树中属性操作的实现
A.树中结点的数目
定义功能:count(node)--在node为根结点的树中统计结点数目
B.树的高度
定义功能:height(node)--获取node为根结点的树的高度
C.树的度数
定义功能:degree(node)--获取node为根结点的树的度数
D.树的层次遍历
设计思路：
1.在树中定义一个游标(GTreeNode
2.在遍历开始前将游标指向根结点(root())
3.获取游标指向的数据元素
4.通过结点中的child成员移动游标
算法
1.原料：class LinkQueue
2.游标：LinkQueue
3.思想
a.begin()=>将根结点压入队列中
b.current()=>访问对头元素指向的数据元素
c.next()=>队头元素弹出，将队头元素的孩子压入队列中
d.end()=>判断队列是否为空
完整树的实现代码
#include "TreeNode.h"
#include "GTreeNode.h"
#include "Exception.h"
#include "LinkQueue.h"
namespace MyLib
{
template
class GTree:public Tree
{
protected:
LinkQueue *> m_queue;
//基于数据元素值的查找，都是遍历实现的
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;
}
void free(GTreeNode* 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* node,GTree*& ret)
{
ret=new GTree();
if(ret==NULL)
{
THROW_EXCEPTION(NoEoughMemoryException,"...");
}
else
{
if(root()!=node)
{
//获取删除结点的父结点的子结点链表
LinkList*>& child=dynamic_cast*>(node->parent)->child;
child.remove(child.find(node)); //从链表中删除结点
node->parent=NULL;//结点的父结点置NULL
}
else
{
this->m_root=NULL;
}
}
}
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 degree(GTreeNode* 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* 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)
{
bool ret=true;
if(node!=NULL)//当结点不为空时
{
if(this->m_root==NULL)//如果此时的根结点为空
{
node->parent=NULL;//node结点就是根结点
this->m_root=node;
}
else
{
GTreeNode* np=find(node->parent);//在堆空间创建np指向node的父节点
if(np!=NULL)
{
GTreeNode* n=dynamic_cast*>(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* parent)
{
bool ret=true;
GTreeNode* node=GTreeNode::NewNode();
if(node!=NULL)
{
node->value=value;
node->parent=parent;
insert(node);
}
else
{
THROW_EXCEPTION(InvalidOperationException,"...");
}
return ret;
}
//删除结点
SharedPointer< Tree > remove(const T& value)
{
GTree* ret=NULL;
GTreeNode* node=find(value);
if(node!=NULL)
{
remove(node,ret);
}
else
{
THROW_EXCEPTION(InvalidOperationException,"...");
}
return ret;
}
SharedPointer< Tree > remove(TreeNode* node)
{
GTree* ret=NULL;
node=find(node);
if(node!=NULL)
{
remove(dynamic_cast*>(node),ret);
}
else
{
THROW_EXCEPTION(InvalidOperationException,"...");
}
return NULL;
}
//查找结点
GTreeNode* find(const T& value)const
{
return find(root(),value);
}
GTreeNode* find(TreeNode* node)const
{
return find(root(),dynamic_cast*>(node));//强制类型转换将TreeNode类型转换为GTreeNode类型
}//root对应的root的类型也应该一样
//根结点访问函数
GTreeNode* root()const
{
return dynamic_cast*>(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* 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* 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();
}
};
}