存储结构二叉树

存储结构二叉树

大家好,又见面了,我是全栈君,今天给大家准备了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)
blank

相关推荐

  • pycharm安装教程和使用_vmware安装教程

    pycharm安装教程和使用_vmware安装教程一:pycharm的介绍PyCharm是一种PythonIDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单元测试、版本控制。此外,该IDE提供了一些高级功能,以用于支持Django框架下的专业Web开发。二:pycharm的下载安装1…在python的官网下载python对应版本:http:/…

  • 木马产业链 安全新忧患

    木马产业链 安全新忧患

  • php接口转发_php发送get请求

    php接口转发_php发送get请求php实现URL转发代码的方法:1、使用“$_SERVER[“SERVER_NAME”]”变量;2、通过“header(“location:http://youname.com”);”函数;3、利用frame元素。推荐:《PHP视频教程》PHP实现URL转发代码花了一点时间研究了一下,发现还是蛮有意思的主要是依靠3个东西:1.$_SERVER[“SERVER_NAME”]这个变量2.head…

    2022年10月19日
  • 解决Tomcat启动后404的问题

    概述当我遇到这个问题的时候,我真是操**的崩溃了,你懂我意思吧,就是那种各种百度也找不到答案,然后有好多回答都是帮我解释什么叫”404”????Excuseme???????我用你解释吗???我觉的真挺逗的,还有一大堆说程序有问题的,就是这个说法啊不能排除,确实有的开发人员给运维的war包就是有问题的,不过在我这儿跟包没关系,纯粹就是自己的问题,所以运维人员如果查到网上说让你去怪开…

  • 模型选择–网格搜索

    模型选择–网格搜索首先使用训练数据训练模型,然后使用交叉验证数据挑选最佳模型,最后使用测试数据测试模型是否完好。下面举一个训练逻辑回归模型的例子。假设有四个模型,第一个是一次模型,然后二次,三次,四次模型。我们使用训练数据训练,并算出多项式的斜率和系数等等。然后使用交叉验证数据计算所有这些模型的F1分数,然后选择F1得分最高的模型,最后使用测试数据确保模型效果完好。算法的参数就是多项式的系数,但是多…

  • pycharm 设置环境变量_电脑环境变量怎么设置

    pycharm 设置环境变量_电脑环境变量怎么设置今天运行tensorflow的时候,发现在pycharm下,程序无法找到CUDA的libcupti.so文件。而在添加完环境变量:exportLD_LIBRARY_PATH=$LD_LIBRARY_PATH/usr/local/cuda/extras/CUPTI/lib64:后,在命令行可以运行程序。然而,在Pycharm中运行程序,仍无法找到CUDA库文件。经过下午的折腾,终于

发表回复

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

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