存储结构二叉树

存储结构二叉树

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

二叉树的存储结构有两种:顺序存储结构和链式存储结构。
顺序存储结构
对于满二叉树和全然二叉树来说,能够将其数据元素逐层存放到一组连续的存储单元中,如图6-3 所看到的。

用一维数组来实现顺序存储结构时。将二叉树中编号为i 的结点存放到数组中的第i 个分量中。如此依据性质6.7,能够得到结点i 的父结点、左右孩子结点分别存放在、2i 以及2i+1 ⎣i / 2⎦ 分量中。

图6-3 顺序存储结构
存储结构二叉树 
这样的存储方式对于满二叉树和全然二叉树是非常合适也是高效方便的。由于满二叉树和全然二叉树採用顺序存储结构既不浪费空间,也能够依据公式非常快的确定结点之间的关系。
可是对于一般的二叉树而言,必须用“虚结点”将一棵二叉树补成一棵全然二叉树来存储,否则无法确定结点之间的前驱兴许关系,可是这样一来就会造成空间的浪费。一种极端的情况是,为了存储k个结点,须要2k-1 个存储单元。图6- 4 说明了这一情况。此时存储空间浪费巨大,这是顺序存储结构的一个缺点。


图6-4 单支二叉树的顺序存储结构
存储结构二叉树 
链式存储结构
设计不同的结点结构可构成不同的链式存储结构。

在二叉树中每一个结点都有两个孩子,则能够设计每一个结点至少包含3 个域:数据域、左孩子域和右孩子域。数据域存放数据元素,

左孩子域存放指向左孩子结点的指针。右孩子域存放指向右孩子结点的指针。如图6-5(a)所看到的。

利用此结点结构得到的二叉树存储结构称为二叉链表。easy证明在具有n 个结点的二叉链表中有n+1 个空链域。

图6-5 二叉树的链式存储结构
存储结构二叉树 
为了方便找到父结点,能够在上述结点结构中添加一个指针域,指向结点的父结点。

如图6-5(b)所看到的。

採用此结点结构得到的二叉树存储结构称为三叉链表。在具有n 个结点的三叉链表中也有n+1 个空链域。

不同的存储结构实现二叉树操作的方法也不同。比如要找某个结点的父结点,在三叉链表中非常easy实现;在二叉链表中则需从根结点出发一一查找。

在实际应用中,要依据二叉树的主要操作来选择存储结构。

为了方便的找到父结点。我们以三叉链表作为二叉树的存储结构。而且在6.3 节中,二叉树的基本操作的实现也是基于三叉链表来实现的。以下我们首先给出具有四个域的结点结构的定义。

代码6-1 二叉树存储结构结点定义
public class BinTreeNode implements Node {
private Object data; //数据域
private BinTreeNode parent; //父结点
private BinTreeNode lChild; //左孩子
private BinTreeNode rChild; //右孩子
private int height; //以该结点为根的子树的高度
private int size; //该结点子孙数(包含结点本身)
102
public BinTreeNode() { this(null); }
public BinTreeNode(Object e) {
data = e; height = 0; size = 1;
parent = lChild = rChild = null;
}
/******Node 接口方法******/
public Object getData() { return data; }
public void setData(Object obj) { data = obj;}
/******辅助方法,推断当前结点位置情况******/
//推断是否有父亲
public boolean hasParent(){ return parent!=null;}
//推断是否有左孩子
public boolean hasLChild(){ return lChild!=null;}
//推断是否有右孩子
public boolean hasRChild(){ return rChild!=null;}
//推断是否为叶子结点
public boolean isLeaf(){ return !hasLChild()&&!hasRChild();}
//推断是否为某结点的左孩子
public boolean isLChild(){ return (hasParent()&&this==parent.lChild);}
//推断是否为某结点的右孩子
public boolean isRChild(){ return (hasParent()&&this==parent.rChild);}
/******与height 相关的方法******/
//取结点的高度,即以该结点为根的树的高度
public int getHeight() { return height; }
//更新当前结点及其祖先的高度
public void updateHeight(){
int newH = 0;//新高度初始化为0,高度等于左右子树高度加1 中的大者
if (hasLChild()) newH = Math.max(newH,1+getLChild().getHeight());
if (hasRChild()) newH = Math.max(newH,1+getRChild().getHeight());
if (newH==height) return; //高度没有发生变化则直接返回
height = newH; //否则更新高度
if (hasParent()) getParent().updateHeight(); //递归更新祖先的高度
}
/******与size 相关的方法******/
//取以该结点为根的树的结点数
public int getSize() { return size; }
//更新当前结点及其祖先的子孙数
public void updateSize(){
size = 1; //初始化为1,结点本身
if (hasLChild()) size += getLChild().getSize(); //加上左子树规模
if (hasRChild()) size += getRChild().getSize(); //加上右子树规模
if (hasParent()) getParent().updateSize(); //递归更新祖先的规模
}
/******与parent 相关的方法******/
//取父结点
public BinTreeNode getParent() { return parent; }
//断开与父亲的关系
public void sever(){
if (!hasParent()) return;
if (isLChild()) parent.lChild = null;
else parent.rChild = null;
parent.updateHeight(); //更新父结点及其祖先高度
parent.updateSize(); //更新父结点及其祖先规模
parent = null;
}
/******与lChild 相关的方法******/
//取左孩子
public BinTreeNode getLChild() { return lChild; }
//设置当前结点的左孩子,返回原左孩子
public BinTreeNode setLChild(BinTreeNode lc){
BinTreeNode oldLC = this.lChild;
if (hasLChild()) { lChild.sever();} //断开当前左孩子与结点的关系
if (lc!=null){
lc.sever(); //断开lc 与其父结点的关系
this.lChild = lc; //确定父子关系
lc.parent = this;
this.updateHeight(); //更新当前结点及其祖先高度
this.updateSize(); //更新当前结点及其祖先规模
}
return oldLC; //返回原左孩子
}
/******与rChild 相关的方法******/
//取右孩子
public BinTreeNode getRChild() { return rChild; }
//设置当前结点的右孩子,返回原右孩子
public BinTreeNode setRChild(BinTreeNode rc){
BinTreeNode oldRC = this.rChild;
if (hasRChild()) { rChild.sever();} //断开当前右孩子与结点的关系
if (rc!=null){
rc.sever(); //断开lc 与其父结点的关系
this.rChild = rc; //确定父子关系
104
rc.parent = this;
this.updateHeight(); //更新当前结点及其祖先高度
this.updateSize(); //更新当前结点及其祖先规模
}
return oldRC; //返回原右孩子
}
}
代码6-1 说明:代码中推断当前结点位置情况的辅助方法以及简单的get 方法都在常数时间内能够完毕。实现也对应很easy。以下主要讨论updateHeight ()、updateSize ()、sever()、setLChild(lc)、getRChild(rc)的实现与时间复杂度。
⑴ updateHeight ():若当前结点v 的孩子发生变化,就须要使用updateHeight ()方法更新当前结点及其祖先结点的高度。请注意。由于一个结点的高度发生变化,会影响到其祖先结点的高度,在这里我们同意直接对不论什么结点运行这一操作。

由于在二叉树中不论什么一个结点的高度,都等于其左右子树的高度中大者加1,而左右子树的高度仅仅须要获取该结点左右孩子的高度就可以获得,仅仅须要Θ(1)时间。续而从v 出发沿parent 引用逆行向上,依次更新各祖先结点的高度就可以。

假设在上述过程中。发现某个结点的高度没有发生变化,算法能够直接终止。综上所述。当对一个结点v 调用updateHeight ()方法时,若v 的层数为level(v),则最多仅仅须要更新level(v)+1 个结点的高度。因此算法的时

间复杂度T(n) = Ο(level(v))。
⑵ updateSize ():相同假设结点v 的孩子发生变化,应该更新当前结点以及其祖先的规模。

由于在二叉树中不论什么一个结点的规模。都等于其左右子树的规模之和加上结点自身,而左右子树的规模仅仅须要获取该结点左右孩子的规模就可以获得,仅仅须要Θ(1)时间。

因此算法的时间复杂度T(n) = Ο(level(v))。

⑶ sever():切断结点v 与父结点p 之间的关系。

该算法须要改动v 与p 的指针域,须要常数时间。除此之外因为p 结点的孩子发生了变化,因此须要调用updateHeight ()和updateSize ()来更新父结点p 及其祖先的高度与规模。其时间复杂度T(n) = Ο(level(v))。

⑷ setLChild(lc)、getRChild(rc):两个算法的功能相对,一个是设置结点v 的左孩子。
一个是设置结点v 的右孩子。

两个算法的实现是类似的,以setLChild()为例说明。首先,假设v 有左孩子oldLC。则应当调用oldLC. sever()断开v 与其左孩子的关系。

其次,调用lc. sever()断开其与父结点的关系。

最后,建立v 与lc 之间的父子关系,并调用v. updateSize ()与v.updateHeight ()更新v 及其祖先的规模与高度。

很多其它精彩内容请关注:http://bbs.superwu.cn
关注超人学院微信二维码:存储结构二叉树
关注超人学院java免费学习交流群:存储结构二叉树

版权声明:本文博主原创文章。博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117027.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 光场相机介绍_光场相机是什么

    光场相机介绍_光场相机是什么魅族在flyme3.3上推出光场相机:

  • MCTS (Monte Carlo Tree Search)[通俗易懂]

    MCTS (Monte Carlo Tree Search)[通俗易懂]以下文章摘录自:《机器学习观止——核心原理与实践》京东:https://item.jd.com/13166960.html当当:http://product.dangdang.com/29218274.html(由于博客系统问题,部分公式、图片和格式有可能存在显示问题,请参阅原书了解详情)MCTS(MonteCarloTreeSearch)1.1MCTS概述在前面的学习中,我们分析了蒙特卡洛方法,本章节将为大家解开蒙特卡洛树搜索的“面纱”。虽…

  • linux基本操作命令_vim常用命令

    linux基本操作命令_vim常用命令1.查找文件find/-name*文件名*2.开始、重启、结束进程#开始进程systemctlstartfilebeat#重启systemctlrestartfilebeat#结束systemctlstopfilebeat3.转到目录#从根目录开始搜索文件夹cd/文件名/#从当前目录开始cd文件名/4.编辑文件#编辑vim文件名vi文件名#查看cat文件名5.从编辑状态退出#先按Esc

  • python计算坐标点欧式距离_计算Python Numpy向量之间的欧氏距离实例

    python计算坐标点欧式距离_计算Python Numpy向量之间的欧氏距离实例计算PythonNumpy向量之间的欧氏距离,已知vec1和vec2是两个Numpy向量,欧氏距离计算如下:importnumpydist=numpy.sqrt(numpy.sum(numpy.square(vec1-vec2)))或者直接:dist=numpy.linalg.norm(vec1-vec2)#补充知识:Python中计算两个数据点之间的欧式距离,一个点到数据集中其他点的距离之和#如下所示:#计算数两个数据点之间的欧式距离importn

  • phpstorm xdebug不成功_vscode配置php开发环境

    phpstorm xdebug不成功_vscode配置php开发环境phpstorm —— Xdebug 的配置和使用

  • Numpy中ndim、shape、dtype、astype的用法

    Numpy中ndim、shape、dtype、astype的用法本文介绍numpy数组中这四个方法的区别ndim、shape、dtype、astype。1.ndimndim返回的是数组的维度,返回的只有一个数,该数即表示数组的维度。2.shapeshape:表示各位维度大小的元组。返回的是一个元组。对于一维数组:有疑问的是为什么不是(1,6),因为arr1.ndim维度为1,元组内只返回一个数。对于二维数组:前面的是行,后面的是列,他的ndim为2,所以返回两…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号