树是一种非线性的数据结构，右n(n>=0)个结点组成的有限集合，如果n=0,称为空树，如果n>0,则：
创新互联公司基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽，联通大带宽，移动大带宽，多线BGP大带宽租用,是为众多客户提供专业达州电信机房报价，主机托管价格性价比高，为金融证券行业服务器托管，ai人工智能服务器托管提供bgp线路100M独享，G口带宽及机柜租用的专业成都idc公司。
除根结点外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1...Tm-1，每一个集合又是一颗子树，并称之为跟的子树。
树的示例如下：
树的结点包含一个数据及若干指向子树的分支，结点拥有的子树数目称为结点的度(度为0的结点称为叶结点；度不为0称为分支结点)；
树的度定义为所有结点中度的最大值。
结点的直接后继称为该结点的孩子，相应的，该结点称为孩子的双亲；
结点的孩子的孩子，称为该结点的子孙，相应 该结点称为子孙的祖先；
同一个双亲的孩子之间互称兄弟。
树中结点最大层次称为树的深度或高度。
如果树中结点的各个子树从左向右是有次序的，子树间不能互换位置，则称该树为有序树，否则为无序树。
与其他的数据结构一样，树的常用操作包括：插入、删除、查找(获取树的节点)、获取树的高度/深度、获取树的度、清空树中的元素等。
template < typename T >
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* node) = 0;
virtual SharedPointer> remove(TreeNode* node) = 0;
virtual SharedPointer> remove(const T& value) = 0;
virtual TreeNode* find(TreeNode* node) const = 0;
virtual TreeNode* find(const T& value) const = 0;
virtual TreeNode* root() const = 0;
virtual int degree() const = 0;
virtual int hight() const = 0;
virtual int count() const = 0;
virtual void clear() =0;
}; 树的节点也表现为一种特殊的数据类型
template < typename T >
class TreeNode : public Object
{
public:
TreeNode* m_parent;
TreeNode()
{
m_parent = NULL;
}
virtual ~TreeNode() = 0;
}; 树与节点的类关系：都继承自顶层父类Object，通过树的节点与树形成组合关系。
总结：
课程目标：完成树和结点的存储结构设计。
前面我们实现了树的抽象结构，本节我们实现一个通用树结构的基本框架。类继承结构如下图所示：
设计要点：
1.GTree为通用树结构，每个结点可以存在多个后继结点；
2.GTreeNode能够包含任意多指向后继结点的指针
3.实现树结构的所有操作(增、删、查、改、等)
我们使用单链表组合完成GTreeNode的实现，便于在GTreeNode中存储多个指向其后继结点的指针；
template < typename T >
class GTreeNode : public TreeNode
{
public:
LinkList*> child;
~GTreeNode(){}
}; 
template
class GTree : public Tree
{ }; 
问题：每个树结中为什么要包含指向前驱结点的指针？
查找方式：
GTreeNode<T>* find(const T& value) const基于结点的查找GTreeNode<T>* find(TreeNode<T>* node) const
基于数据元素值的查找：
定义功能函数：find (node, value)，在node为根结点的树中递归查找value所在的节点
GTreeNode* find(GTreeNode* node, const T& value)const
{
GTreeNode* ret = NULL;
if(node != NULL)
{
//如果根结点的就是目标结点
if(node->value == value)
{
ret = node;
}
else
{
//遍历根节点的子结点
for(node->m_children.move(0); !node->m_children.end() && (ret == NULL); node->m_children.next())
{
//对每个子子结点进行查找
ret = find(node->m_children.current(), value);
}
}
}
return ret;
}
//查找结点
virtual GTreeNode* find(const T& value)const
{
return find(root(), value);
} 基于结点的查找：
定义功能函数：find(node, obj)，在node为根结点的树中递归查找是否存在obj结点；
GTreeNode* find(GTreeNode* node, GTreeNode* obj)const
{
GTreeNode* ret = NULL;
//根结点为目标结点
if(node == obj)
{
ret = node;
}
else
{
if(node != NULL)
{
//遍历子结点
for(node->m_children.move(0); !node->m_children.end() && (ret == NULL); node->m_children.next())
{
ret = find(node->m_children.current(), obj);
}
}
}
return ret;
}
virtual GTreeNode* find(TreeNode* node)const
{
return find(root(), dynamic_cast*>(node));
} 总结：
1.查找操作是树的关键操作之一，插入函删除操作都依赖于查找操作；
2.基于数据元素的查找可以判断值是否存在于树中；基于结点的查找可以判断树中是否存在指定结点；
插入方式：
bool insert(TreeNode<T>* node)bool insert(const T& value,TreeNode<T>* parent)
bool insert(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->m_children.find(n) < 0)
{
ret = np->m_children.insert(n);
}
}
else
{
THROW_EXCEPTION(InvalidOperationException, "Invalid node...");
}
}
}
else
{
THROW_EXCEPTION(InvalidParameterException, "Parameter is invalid...");
}
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(NoEnoughMemoryException, "No enough memory...");
}
return ret;
} 总结：
1.插入操作是构建树的唯一操作，需要从堆空间中创建结点
2.执行插入操作必须正确处理指向父节点的指针
清除操作的定义：void clear() //将树中的所有节点清除(释放堆中的节点)
清除操作功能函数定义：
free(node) //清除node为根结点的树，释放树中的每一个结点
问题：树中的结点可能来源于不同的存储空间，如何判断堆空间中的结点并释放？
1.单凭内存地址很难准确判断具体的存储区域；
2.只有堆空间的内存才需要主动释放(delete)
3.清除操作时只需要对堆中的结点进行释放
1.在GTreeNode中增加保护成员m_flag;
2.将GTreeNode中的operator new重载为保护成员函数；
3.提供工厂方法GTreeNode
4.在工厂方法中new新结点并将m_flage设置为true;
树结点的工厂模式示例：
template
class GTreeNode:public TreeNode
{
protected:
bool m_flag;//堆空间标识
//重载new操作符，声明为保护
void* operator new(unsigned int size)throw()
{
return Object::operator new(size);
}
public:
LinkedList*> m_children;
GTreeNode()
{
//栈上分配的空间标识为false
m_flag = false;
}
//工厂方法，创建堆空间的结点
static GTreeNode* NewNode()
{
GTreeNode* ret = new GTreeNode();
if(ret != NULL)
{
//堆空间的结点标识为true
ret->m_flag = true;
}
return ret;
}
//堆空间结点标识访问函数
bool flag()const
{
return m_flag;
}
};
//结点的释放：
void free(GTreeNode* node)
{
if(node != NULL)
{
for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
{
free(node->m_children.current());
}
//如果结点存储在堆空间
if(node->flag())
delete node;//释放
}
}
//清空树：
void clear()
{
free(root());
this->m_root = NULL;
} 总结：
1.清除操作用于销毁树中的每个结点，需要释放对应的内存空间；
2.工厂模式可用于“定制”堆空间中的结点，只有销毁定制结点的时候需要进行释放
删除的方式：
SharedPointer< Tree<T> > remove(const T& value)基于结点的删除SharedPointer< Tree<T> > remove(TreeNode<T>* node)
删除操作成员函数的操作要点：
1.被删除的结点所代表的子树进行删除；
2.删除函数返回一棵树堆空间中的树
3.具体返回值为指向树的智能指针对象
实用的设计原则：
当需要从函数中返回堆中的对象时，使用智能指针(SharedPointer)作为函数的返回值。
删除操作功能函数定义：void remove(GTreeNode<T>* node, GTree<T>*& ret)
1.将node为根结点的子树从原来的树中删除
2.Ret做为子树返回(ret指向堆空间中的树对象)
// 删除操作功能函数
void remove(GTreeNode* node, GTree*& ret)
{
ret = new GTree();
if(ret != NULL)
{
//如果删除的结点是根结点
if(root() == node)
{
this->m_root = NULL;
}
else
{
//获取删除结点的父结点的子结点链表
LinkedList*>& child = dynamic_cast*>(node->parent)->m_children;
//从链表中删除结点
child.remove(child.find(node));
//结点的父结点置NULL
node->parent = NULL;
}
//将删除结点赋值给创建的树ret的根结点
ret->m_root = node;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
}
}
// A、基于删除数据元素值删除结点
SharedPointer> remove(const T& value)
{
GTree* ret = NULL;
//找到结点
GTreeNode* node = find(value);
if(node != NULL)
{
remove(node, ret);
}
else
{
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
}
return ret;
}
// B、基于结点删除
SharedPointer> remove(TreeNode* node)
{
GTree* ret = NULL;
node = find(node);
if(node != NULL)
{
remove(dynamic_cast*>(node), ret);
}
else
{
THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
}
return ret;
} 总结：
1.删除操作将目标节点所代表的子树移除，返回值为指向树智能指针对象；
2.删除操作必须完善处理父节点和子节点的关系；
3.函数中返回堆中的对象时，使用智能指针作为返回值。
定义功能，count(node)，在node为根结点的树中统计结点数目。
使用递归实现：结点数目 = 子树结点数目+1(根结点)。
int count(GTreeNode* node) const
{
int ret = 0;
if(node != NULL)
{
ret = 1;//根结点
//遍历根节点的子结点
for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
{
ret += count(node->m_children.current());
}
}
return ret;
}
//树的结点数目访问函数
int count()const
{
count(root());
} 功能定义：height(node)，获取node为根结点的树的高度。
递归实现：树的高度 = 子树结点高度的最大值 + 1(根结点)。
int degree(GTreeNode* node) const
{
int ret = 0;
if(node != NULL)
{
//结点的子结点的数量
ret = node->m_children.length();
//遍历子结点
for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
{
int d = degree(node->m_children.current());
if(ret < d)
{
ret = d;
}
}
}
return ret;
}
//树的度访问函数
int degree()const
{
return degree(root());
} 功能定义：degree(node)，获取node为结点的树的度数。
递归实现：树的度数 = 子树的最大度数 + 1(根结点)
int height(GTreeNode* node)const
{
int ret = 0;
if(node != NULL)
{
//遍历子结点
for(node->m_children.move(0); !node->m_children.end(); node->m_children.next())
{
//当前结点的高度
int h = height(node->m_children.current());
if(ret < h)
{
ret = h;
}
}
ret = ret + 1;
}
return ret;
}
//树的高度访问函数
int height()const
{
height(root());
} 问题：如何按照层次遍历通用树结构中的每一个数据元素？
当前的事实：- 树是一种非线性的数据结构，树的节点没有固定的编号方式；
新的需求：- 为通用树结构提供新的方法，快速遍历每一个节点
设计思路：
在树中定义一个新游标(GTreeNode
提供一组遍历相关的函数，按层次访问树中的数据元素。
层次遍历算法：
原料：class LinkQueue
思想：
end() 判断队列是否为空
//将根结点压入队列中
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->m_children.move(0); !node->m_children.end(); node->m_children.next())
{
m_queue.add(node->m_children.current());
}
}
return ret;
}
//访问队头元素指向的数据元素
T current()
{
if(!end())
{
return m_queue.front()->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "No value at current Node...");
}
} 总结：
1.树的结点没有固定的编号方式，可以按照层次关系堆树中的结点进行遍历；
2.通过游标的思想设计成员函数，遍历函数是相互依赖，相互配合的；
3.遍历操作的核心是队列的使用。
template
class GTree : public Tree
{
protected:
LinkQueue*> m_queue;
GTree(const GTree&);
GTree& operator =(const GTree&); //容器的内容不能复制
GTreeNode* find(GTreeNode* node, const T& value) const
{
GTreeNode* ret = NULL;
if(node != NULL)
{
if(node->value == value)
{
ret = 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 != NULL)
{
if(node == obj)
{
ret = node;
}
else
{
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;
}
/*else
{
cout << node->value << endl;
}*/
}
}
// 删除操作的功能函数，(1.将node为根结点的子树从原来的树中删除 2.Ret做为子树返回(ret指向堆空间中的树对象))
void remove(GTreeNode* node, GTree*& ret) //ret 是一个指针的别名
{
ret = new GTree();
if(ret != NULL)
{
if(node == root())
{
this->m_root = NULL;
}
else
{
//获取删除结点的父结点的子结点链表
LinkList*>& child = dynamic_cast*>(node->m_parent)->child;
// 从链表中删除节点
child.remove(child.find(node));
// 结点的父结点置NULL
node->m_parent = NULL;
}
// 将删除结点赋值给创建的树ret的根结点
ret->m_root = node;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create GTree...");
}
}
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(h > ret) //获取子树高度的最大值
{
ret = h;
}
}
ret = ret + 1/*根结点*/;
}
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 < d)
{
ret = d; //获取子树高度的最大度数
}
}
}
return ret;
}
public:
GTree(){}
bool insert(TreeNode* node)
{
bool ret = true;
if(node != NULL)
{
if(this->m_root == NULL)
{
this->m_root = node;
node->m_parent = NULL;
}
else
{
GTreeNode* np = find(node->m_parent);
if(np != NULL)
{
GTreeNode* n = dynamic_cast*>(node);
// 防止重复插入
if( np->child.find(n) < 0 )
{
np->child.insert(n);
}
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "can't find parent node for current node...");
}
}
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "con't insert NULL node...");
}
return ret;
}
bool insert(const T& value, TreeNode* parent)
{
bool ret = true;
GTreeNode* node = GTreeNode::NewNode();
if(node != NULL)
{
node->value = value;
node->m_parent = parent;
insert(node);
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create node... ");
}
return ret;
}
SharedPointer< Tree > remove(const T& value)
{
GTree* ret = NULL;
GTreeNode* node = find(value);
if(node != NULL)
{
remove(node, ret);
m_queue.clear();
m_queue.clear();
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "invaild paremeter...");
}
return ret;
}
SharedPointer< Tree > remove(TreeNode* node)
{
GTree* ret = NULL;
node = find(node);
if(node != NULL)
{
remove(dynamic_cast*>(node), ret);
}
else
{
THROW_EXCEPTION(InvaildParemeterException, "invaild paremeter...");
}
return ret;
}
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);
}
int degree() const
{
return degree(root());
}
int count() const
{
return count(root());
}
int height() const
{
return height(root());
}
void clear()
{
free(root());
this->m_root = NULL;
}
bool begin()
{
bool ret = (root() != NULL);
if(ret)
{
m_queue.clear();
m_queue.enqueue(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.dequeue();
for(node->child.move(0); !node->child.end(); node->child.next())
{
m_queue.enqueue(node->child.current());
}
}
return ret;
}
T current()
{
if(!end())
{
return m_queue.front()->value;
}
else
{
THROW_EXCEPTION(InvalidOperationException, "invalid operation ...");
}
}
~GTree()
{
clear();
m_queue.clear();
}
}; template < typename T >
class GTreeNode : public TreeNode
{
protected:
//堆空间标识,如果在堆空间中创建了结点，则置为true，以便后续释放结点时判断结点是否创建自堆空间
bool m_flag;
GTreeNode(const GTreeNode&);
GTreeNode& operator =(const GTreeNode&); //容器的内容不能复制
//重载new操作符，声明为保护成员
void* operator new(unsigned int size)throw()
{
return Object::operator new(size);
}
public:
LinkList*> child;
GTreeNode()
{
m_flag = false;
}
static GTreeNode* NewNode()
{
GTreeNode* ret = new GTreeNode();
if(ret != NULL)
{
ret->m_flag = true; //在堆空间中申请了结点，则将该标识置为true
}
return ret;
}
//堆空间结点标识访问函数
bool flag()const
{
return m_flag;
}
~GTreeNode(){}
};