摘要:本文主要向大家介绍了C/C++知识点之1 数据结构(13)_二叉树的概念及常用操作实现,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之1 数据结构(13)_二叉树的概念及常用操作实现,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。
思考:通用树结构的实现太过复杂(树中每个结点都可以有任意多的孩子,具有多种形态),工程中很少会用到如此复杂的树是否可以简化呢?
思路:减少树结点中孩子的数量。但这样树是否还能通用呢?
双亲孩子表示法:
孩子兄弟表示法:
孩子兄弟表示法的特点:
1.能够表示任意的树形结构
2.每个结点包含一个数据成员和两个指针成员
3.孩子结点指针和兄弟结点指针构成“树杈”
二叉树是由n(n>=0)个节点组成的有限集合,该集合或者为空,或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。
满二叉树:
如果二叉树中所有分支结点的度数都为2,且叶子结点都在同一层次上,则称这类二叉树为满二叉树。
完全二叉树:
如果一棵具有N个结点高度为K的二叉树,它的每一个结点与高度为K的满二叉树中编号1~n的结点一一对应,则称这颗二叉树为完全二叉树。(从上到下,从左到右编号)。
完全二叉树的特性:
同样结点的二叉树,完全二叉树的高度最小;完全二叉树的叶结点一定出现在最下面两层。
1.最底层的叶结点一定出现在左边;
2.倒数第二层的叶结点一定出现在右边;
3.完全二叉树中度数为1的结点只有左孩子。
总结:
1.通用树结构采用了双亲结点表示法进行描述;
2.孩子兄弟表示法也有能力描述任意类型的树结构;
3.孩子兄弟表示法能够将通用树转化为二叉树(最多有两个孩子);
1.在二叉树的第i层最多有2^(i-1)个结点(i>=1);
2.高度为K的二叉树最多有2^k - 1个结点(K>=0);
3.对于任何一颗二叉树,如果其叶结点有n0个,度为2的非叶结点有n2个,则有n0 = n2 + 1;
推导证明:
假设二叉树中为1的结点有n1个,总结点数为n,则:n = n0 + n1 + n2;
假设二叉树中连接父子结点的边为e条,则: e = n1 + 2n2 (从上往下看,有一条边的结点+有两条边的结点),同时从下往上看e = n-1(根结点之上没有与之相连的边),故:
n1 + 2n2 = n-1 ==> n1 + 2n2 = n0 + n1 + n2 - 1 ==> n0 = n2 + 1
4.具有n个结点的完全二叉树的告诉为【log2N】 + 1 (【x】表示不大于x的最大整数)
5.
目标:完成二叉树和二叉树结点的存储设计;
设计要点:
1.BTree为二叉树,每个结点最多只有两个后继结点;
2.BTreeNode只包含4个固有的公有成员:(数据成员、指向左孩子和右孩子的指针、指向父节点的指针)
BTreeNode的设计
直接继承自抽象树结点,使用工厂模式(标识使用的堆空间,方便使用智能指针进行释放)。
template < typename T >
class BTreeNode : public TreeNode<T>
{
public:
BTreeNode<T>* left;
BTreeNode<T>* right;
static BTreeNode<T>* NewNode()
{
BTreeNode<T>* ret = new BTreeNode<T>();
if(ret != NULL)
{
ret->m_flag = true; //在堆空间中申请了结点,则将该标识置为true
}
return ret;
}
~BTreeNode(){}
};
BTree的设计
继承自抽象树结构,并组合使用BTreeNode.
template < typename T >
class BTree : public Tree<T>
{
};
二叉树的实现架构:
1.基于数据元素值的查找:
BTreeNode<T>* find(const T& value) const
virtual BTreeNode<T>* find(BTreeNode<T>* node, const T& value) const
{
BTreeNode<T>* ret = NULL;
if(node != NULL) // 判断是否为空树
{
if(node->value == value) //比较根结点
{
ret = node;
}
else
{
if(ret == NULL)
{
//递归查找左子树
ret = find(node->m_left, value);
}
if(ret == NULL)
{
//递归查找右子树
ret = find(node->m_right, value);
}
}
}
return ret;
}
BTreeNode<T>* find(const T& value) const
{
return find(root(), value);
}
2.基于结点的查找:
BTreeNode<T> find(TreeNode<T> node) const
virtual BTreeNode<T>* find(BTreeNode<T>* node, BTreeNode<T>* obj) const
{
BTreeNode<T>* ret = NULL;
if(node != NULL) // 判断是否为空树
{
if(node == obj) //比较根结点
{
ret = node;
}
else
{
if(ret == NULL)
{
//递归查找左子树
ret = find(node->m_left, obj);
}
if(ret == NULL)
{
//递归查找右子树
ret = find(node->m_right, obj);
}
}
}
return ret;
}
BTreeNode<T>* find(TreeNode<T>* node) const
{
return find(root(), dynamic_cast<BTreeNode<T>*>(node));
}
思考:是否能在二叉树的任意结点处插入子结点?
因为二叉树的定义中,每个结点最多只能有两个子结点,所以必然不能在任意结点处插入,因此需要制定新的数据元素(新结点)的插入位置。
二叉树结点的位置定义:
enum BTreeNodePos
{
ANY,
LEFT,
RIGHT
};
1.定义功能函数,指定位置的结点插入:virtual bool insert(BTreeNode<T>* newnode, BTreeNode<T>* node, BTNodePos pos)
virtual bool insert(BTreeNode<T>* n, BTreeNode<T>* np, BTreeNodePos pos)
{
bool ret = true;
//指定的插入位置为ANY(没有指定插入位置)
if(pos == ANY)
{
if(np->m_left == NULL) // 左子树结点为空,插入到左子树
{
np->m_left = n;
}
else if(np->m_right == NULL) // ...
{
np->m_right = n;
}
else
{
ret = false;
}
}
// 指定插入到左孩子结点
if(pos == LEFT)
{
if(np->m_left == NULL)
{
np->m_left = n;
}
else
{
ret = false;
}
}
// 指定插入到右孩子结点
if(pos == RIGHT)
{
if(np->m_right == NULL)
{
np->m_right = n;
}
else
{
ret = false;
}
}
return ret;
}
2.插入新结点
bool insert(TreeNode<T>* node, BTreeNodePos pos)
bool insert(TreeNode<T>* node)
//插入结点,并指定位置
bool insert(TreeNode<T>* node, BTreeNodePos pos)
{
bool ret = true;
if(node != NULL)
{
if(root() == NULL) //判断根结点处是否可以插入
{
node->m_parent = NULL;
this->m_root = node;
}
else
{
BTreeNode<T>* np = find(node->m_parent); //查找父节点是否存在
if(np != NULL)
{
// 调用二叉树插入操作功能函数
ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
}
else
{
THROW_EXCEPTION(InvaildParameterException, "invalid parent tree node...");
}
}
}
else
{
THROW_EXCEPTION(InvaildParameterException, "param con't be NULL...");
}
return ret;
}
//插入结点,无位置要求
bool insert(TreeNode<T>* node)
{
return insert(node, ANY);
}
3.插入数据元素
bool insert(const T& value,TreeNode<T>* parent, BTreeNodePos pos)
bool insert(const T& value,TreeNode<T>* parent)
//插入数据元素,指定位置
bool insert(const T& value,TreeNode<T>* parent, BTreeNodePos pos)
{
bool ret = true;
BTreeNode<T>* node = BTreeNode<T>::NewNode();
if(node != NULL)
{
node->value = value;
node->m_parent = parent;
insert(node, pos);
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree node...");
}
return ret;
}
bool insert(const T& value,TreeNode<T>* parent)
{
return insert(value, parent, ANY);
}
测试技巧:从叶结点到根结点为线性数据结构,可以使用链表的遍历方式。
总结:
1.二叉树的插入操作需要指明插入的位置;
2.插入操作必须正确处理指向父节点的指针
3.插入数据元素时需要从堆空间中创建结点,让数据元素插入失败时,需要释放结点空间。
1.删除操作功能定义
void remove(BTreeNode<T> node, BTree<T>& ret)
将node为根结点的子树从原来的二叉树中删除,ret作为子树返回(ret指向堆空间中的二叉树对象)
virtual void remove(BTreeNode<T>* node, BTree<T>*& ret)
{
ret = new BTree();
if(ret != NULL)
{
if(root() == node)
{
this->m_root = NULL;
}
else
{
BTreeNode<T>* np = dynamic_cast<BTreeNode<T>*>(node->m_parent);
if(np->m_left == node)
{
np->m_left = NULL;
}
else if(np->m_right == node)
{
np->m_right = NULL;
}
node->m_parent = NULL;
}
ret->m_root = node;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree...");
}
}
2.基于数据元素的删除
SharedPointer< Tree<T> > remove(const T& value)
SharedPointer< Tree<T> > remove(const T& value)
{
BTree<T>* ret = NULL;
BTreeNode<T>* node = find(value);
if(node != NULL)
{
remove(node, ret);
m_queue.clear();
}
return ret;
}
3.基于结点的删除
SharedPointer< Tree<T> > remove(TreeNode<T>* node)
SharedPointer< Tree<T> > remove(TreeNode<T>* node)
{
BTree<T>* ret = NULL;
node = find(node);
if(node != NULL)
{
remove(dynamic_cast<BTreeNode<T>*>(node), ret);
m_queue.clear();
}
return ret;
}
测试技巧:直接打印已经删除的子树。
总结:
删除操作将目标界定啊所在的子树移除,必须完善处理父子结点的关系
void clear() // 将二叉树中的所有节点清除(释放堆中的结点)
1.清除操作功能定义
free(node) // 清除node为根结点的二叉树,释放二叉树中的每个结点
// 清空树的功能函数定义
void free(BTreeNode<T>* node)
{
if(node != NULL)
{
free(node->m_left);
free(node->m_right);
//cout << node->value << endl;
if(node->flag())
{
delete node;
}
}
}
void clear()
{
free(root());
this->m_root = NULL;
}
测试技巧:可以在free函数中打印删除的每一个结点
总结:
清除操作用于销毁树中的每个结点,销毁时要判断是否释放对应的内存空间(工厂模式)。
定义功能函数:cout(node) // 在node为根结点的二叉树中递归统计结点数目
// 获取树的结点个数,递归实现
int count(BTreeNode<T>* node) const
{
int ret = 0;
if(node != NULL)
{
// 左子树的结点个数 + 右子树的结点个数 + 1(根结点)
ret = count(node->m_left) + count(node->m_right) + 1;
}
return ret;
}
int count() const
{
return count(root());
}
定义功能函数:height(node) // 递归获取node为根结点的二叉树的高度
// 获取树的结点个数,递归实现
int height(BTreeNode<T>* node) const
{
int ret = 0;
if(node != NULL)
{
int hl = height(node->m_left);
int hr = height(node->m_right);
// 左右子树高度的最大值 + 1(根结点)
ret = ((hl > hr) ? hl : hr) + 1;
}
return ret;
}
int height() const
{
return height(root());
}
定义功能函数:degree(node) // 获取node为根结点的二叉树的度数
// 获取二叉树的度,递归实现
int degree(BTreeNode<T>* node) const
{
int ret = 0;
if(node != NULL)
{
/*
// 普通思路
int dl = degree(node->m_left); // 左子树的度
int dr = degree(node->m_right); // 右子树的度
ret = !!node->m_left + !!node->m_right; //根结点的度
if(dl > ret)
{
ret = dl;
}
else if(dr > ret)
{
ret = dr;
}
*/
/*
* 优化效率,二叉树的最大度数为2,如果ret已经为2,则不需要继续遍历
ret = !!node->m_left + !!node->m_right; //根结点的度
if(ret < 2)
{
int dl = degree(node->m_left); // 左子树的度
if(dl > ret)
{
ret = dl;
}
}
if(ret < 2)
{
int dr = degree(node->m_right); // 左子树的度
if(dr > ret)
{
ret = dr;
}
}
*/
// 优化冗余代码
ret = !!node->m_left + !!node->m_right; //根结点的度
BTreeNode<T>* child[] = {node->m_left, node->m_right};
for(int i=0; i<2 && ret<2; i++)
{
int d = degree(child[i]);
if(d > ret)
{
ret = d;
}
}
}
return ret;
}
int degree() const
{
return degree(root());
}
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有节点,使得每个结点被访问一次。
思考:通用树结构的层次遍历算法是否可以用在二叉树结构上?如果可以需要做什么改动?
不同之处在于二叉树最多只有两个孩子。
设计思路:
在树中定义一个新游标(BTreeNode<T>*),遍历开始将游标指向根结点(root()),获取游标指向的数据元素,通过结点中的child成员移动游标;
提供一组遍历相关的函数,按层次访问树中的数据元素。
层次遍历算法:
原料:class LinkQueue<T>; 游标:LinkQueue<T>::front();
思想:
begin() 将根结点压人队列中
current() 访问队头指向的数据元素
next() 队头元素弹出,将队头元素的孩子(左孩子、右孩子)压入队列中(核心)
end() 判断队列是否为空
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)
{
BTreeNode<T>* node = m_queue.front();
m_queue.dequeue();
// 二叉树的左右孩子入队列
if(node->m_left != NULL)
{
m_queue.enqueue(node->m_left);
}
if(node->m_right != NULL)
{
m_queue.enqueue(node->m_right);
}
}
return ret;
}
// 获取游标所执行的元素
T current()
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号