我们在前面学习了排序相关的知识,从今天开始,我们来学习数据结构中树的相关东西。那么什么是树呢?树是一种非线性的数据结构。
树是由 n( n >= 0 ) 个结点组成的有限集合。如果 n= 0,称为空树;如果 n > 0,则:a> 有一个特定的称之为根(root)的结点;b> 根结点只有直接后继,但没有直接前驱;c> 除根以外的其它结点划分为 m( m >= 0 ) 个互不相交的有限集合T0, T1, … Tm-1,每个集合又是一棵树,并且称之为根的子树(sub tree)。下来我们来看看树的示意图,如下所示
下来我们来看一个树中度的概念。它是指树中的结点包含一个数据及若干指向子树的分支,及诶单拥有子树的数目称为结点的度。度为 0 的结点称为叶结点,度不为 0 的结点称为分支节点。树的度定义为所有节点中度的最大值。下来来看一个数的度为 3 的示例,如下图所示
下来来介绍下树中的前驱和后继。结点的直接后继称为该结点的孩子,相应的,该结点称为孩子的双亲;结点的孩子的孩子的 ... 称为该结点的子孙,相应的,该结点称为子孙的祖先;同一个双亲的孩子之间互称兄弟。下来来看看树的前驱和后继的结构示意图
我们来看看树中结点的层次,如下图所示
树也有有序性,什么叫树的有序性呢?如果树中结点的各子树从左向右是有次序的,子树间不能互换位置,则称该树为有序树,否则为无序树。示意图如下图所示
那么既然有树的概念,就肯定有森林的概念。森林是由 n( n >= 0 ) 棵互不相交的树组成的集合。那么在树中肯定也有一些常用的操作,如下
1、将元素插入树中;
2、将元素从树中删除;
3、获取树的结点数;
4、获取树的高度;
5、获取树的度;
6、清空树中的元素;
7、 ......
树与结点的类关系可以如下表示
那么我们下来来看看那树和结点抽象类的具体源码是怎样写的
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
下来我们来看看树和结点的存储结构是怎么设计的,结构图如下
设计要点:1、GTree 为通用的树结构,每个结点可以存在多个后继结点;2、GTreeNode 能够包含任意多指向后继结点的指针;3、实现树结构的所有操作(增,删,查,等)。
GTree(通用树结构)的实现框架如下图所示
我们来看看通用树结构(框架)是怎样创建的,源码如下
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
我们在树的设计中,为什么要在每个树节点中包含指向前驱结点的指针呢?从根结点到叶结点是非线性的数据结构,但是从叶结点到根结点是线性的数据结构(链表),结果如下
下来我们就来一一的实现上面的查找、插入等操作
1、查找操作
查找的方式应分为两种:a> 基于数据元素值的查找:GTreeNode<T>* find(const T& value) const;b> 基于结点的查找:GTreeNode<T>* find(TreeNode<T>* node) const。
a> 基于数据元素值的查找,我们先在 protected 属性中定义 find(node, value) 功能,在 node 为根结点的树中查找 value 所在的结点,实现思路如下
b> 基于结点的查找,还是在 protected 属性中定义 find(node, obj) 功能,在 node 为根结点的树中查找是否存在 obj 结点,实现思路如下
具体查找相关源码实现如下
#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> 插入新结点:bool ×××ert(TreeNode<T>* node);b> 插入数据元素:bool ×××ert(const T& value, TreeNode<T>* parent)。
那么如何在树中指定新结点的位置呢?问题分析:a> 树是非线性的,无法采用下标的形式定位数据元素;b> 每一个树结点都有唯一的前驱结点(父结点);c> 因此,必须先找到前驱节点,才能完成新结点的插入。
a> 新结点的插入,如下图所示
插入新结点的流程如下图所示
b> 插入数据元素,流程如下图所示
下来我们来看看具体源码是怎么实现的
#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
我们来写点测试代码,看看前面实现的查找和插入代码是否正确
#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;
}
运行结果如下
我们看到已经实现了之前定义的树结构。
3、清除操作
a> 定义:void clear();将树中的所有结点清除(释放堆中的结点),树中数据元素的清除如下所示
b> free(node);清除 node 为根结点的树,释放树中的每一个结点,实现思路如下
具体源码实现如下
#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;
}
我们来看看结果
我们看到已经清空了树。但是此时存在一个问题,那便是我们在 main 函数中是在堆上值指定的数据元素,上面的清除操作也会将这个堆中的数据元素删除掉。这必然会导致问题,那么对于树中的结点来源于不同的存储空间的话,此时我们应如何判断堆空间中的结点并释放?问题分析:单凭内存地址很难准确判断具体的存储区域,只有堆空间的内存需要主动释放(delete),清除操作时只需要对堆中的结点进行释放。
此时的解决方案:工厂模式。
i. 在 GTreeNode 中增加保护成员变量 m_flag;
ii. 将 GTreeNode 中的 operator new 重载为保护成员函数;
iii. 提供工厂方法 GTreeNode<T>* NewNode();
iv. 在工厂方法中 new 新结点并将 m_flag 设置为 true。
树结点的工厂模式示例如下
我们来看看具体的源码实现
#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,我们再来进行删除。为例方便的进行说明,我们在这块加个调试语句,再来一个 else 语句,里面打印出不同存储区域的数据元素,我们来看看结果
我们看到此时除了我们自己在堆上指定的 A 之外,剩下的数据元素已经全部被清除掉。
4、删除操作
删除的方式也分为两种:a> 基于数据元素值的删除:SharedPointer< Tree<T> > remove(const T& value);b> 基于结点的删除:SharedPointer< Tree<T> > remove(TreeNode<T>* node);
删除操作成员函数的设计要点:1、将被删结点所代表的子树进行删除;2、删除函数返回一颗堆空间的树;3、具体返回值为指向树的只能指针对象。树中结点的删除示意如下图所示
如果当我们需要从函数中返回堆中的对象时,使用智能指针(SharedPointer)作为函数的返回值。删除操作功能的定义:void remove(GTreeNode<T>* node, GTree<T>*& ret);将 node 为根结点的子树从原来的树中删除,ret 作为子树返回(ret 指向堆空间中的树对象)。删除功能函数的实现思路如下
具体源码实现如下
#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;
}
我们来看看运行结果
我们看到子树 D 已经被删除了,如果我们想用这个删除的子树 D,该如何做呢?将上面的测试代码中的注释的那行放开,将下面的 remove 注释掉,再将下面 for 循环中的 t.find(s[i]) 改为 p->find(s[i]),我们来看看运行结果
我们看到打印出的是我们删除的子树 D。
5、其他属性操作
a> 树中结点的数目,功能定义:count(node);在 node 为根结点的树中统计结点数目,实现思路如下
树的结点数目的计算示例如下:
b> 树的高度,功能定义:height(node);获取 node 为根结点的树的高度,实现思路如下
树的高度计算示例如下:
c> 树的度数,功能定义:degree(node);获取 node 为根结点的树的度数,实现思路如下
树的度计算示例
下来看看具体的源码实现
#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;
}
我们来看看运行结果
6、层次遍历
如何按层次遍历通用树结构中的每一个数据元素呢?树是非线性的数据结构,树的结点没有固定的编号方式。那么我们就得提供一个新的需求,为通用树结构提供新的方法,能快速遍历每一个结点。
设计思路(游标):a> 在树中定义一个游标(GTreeNode<T>*);b> 遍历开始前将游标指向根结点(root());c> 获取游标指向的数据元素;d> 通过结点中的 child 成员移动游标。提供一组遍历相关的函数,按层次访问树中的数据元素。如下
层次遍历算法:a> 原料:class LinkQueue<T>;b> 游标:LinkQueue<T>::front();c> 思想:i. begin() --> 将根节点压入队列中;ii. current() --> 访问队头元素指向的数据元素;iii. next() --> 队头元素弹出,将对头元素的孩子压入队列中(核心);iv. end() --> 判断队列是否为空。层次遍历算法示例如下
下来我们来看看具体的源码实现
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;
}
运行结果如下
我们看到已经将之前的树结构层次遍历了一遍。通过对树的学习,总结如下:1、树是一种非线性的数据结构,结点拥有唯一前驱(父结点)和若干后继(子结点);2、树的结点包含一个数据及若干指向其他结点的指针,树与结点在程序中表现为特殊的数据类型;3、基于数据元素的查找可判断值是否存在于树中,基于结点的查找可判断树中是否存在指定结点;4、插入操作是构建树的唯一操作,执行插入操作时必须指明结点间的父子关系;5、插入操作必须正确处理指向父结点的指针,插入数据元素时需要从堆空间中创建结点;6、销毁结点时需要决定是否释放对应的内存空间,工厂模式可用于“定制”堆空间中的结点,只有销毁定制结点的时候需要进行释放;7、删除操作必须完善处理父结点和子结点的关系,它的返回值为指向树的智能指针对象,函数中返回堆中的对象时使用智能指针作为返回值;8、插入操作和删除操作都依赖于查找操作;9、树的结点没有固定的编号方式,可以按照层次关系对树中的结点进行遍历;10、通过游标的思想设计遍历成员函数,遍历成员函数是相互依赖,相互配合的关系,遍历算法的核心为队列的使用。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。