数组顺序存储二叉树-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

数组顺序存储二叉树

简介: 1.完全二叉树     完全二叉树由于其结构上的特点,通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号,就得到结点的一个线性系列。     如下图:完全二叉树除最下面一层外,各层都被结点充满了,每一层结点的个数恰好是上一层结点个数的2倍,因此通过一个结点的编号就可以推知它的双亲结点及左,右孩子结点的编号: ① 当 2i ≤ n 时,结点 i 的左孩子是 2i,否则结

1.完全二叉树


    完全二叉树由于其结构上的特点,通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号,就得到结点的一个线性系列。

    如下图:完全二叉树除最下面一层外,各层都被结点充满了,每一层结点的个数恰好是上一层结点个数的2倍,因此通过一个结点的编号就可以推知它的双亲结点及左,右孩子结点的编号:

当 2i ≤ n 时,结点 i 的左孩子是 2i,否则结点i没有左孩子;

② 当 2i+1 ≤ n 时,结点i的右孩子是 2i+1,否则结点i没有右孩子;

③ 当 i ≠ 1 时,结点i的双亲是结点 i/2;

wKioL1VxFQexJ6rQAADyoOXy9yc156.gif


注意:由于数组下标从0开始,用数组模拟二叉树(当然也包括堆)的话,如果根节点的下标为0的话,则对于每个结点i,其左孩子下标为2*i+1;其右孩子下标为2*i+2。


2.一般二叉树


    对于一般的二叉树,如果仍按照从上至下,从左到右的顺序将树中的结点顺序存储在一维数组中,则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系。

    这时假设将一般二叉树进行改造,增添一些并不存在的空结点,使之成为一棵完全二叉树的形式,然后再用一维数组顺序存储。在二叉树中假设增添的结点在数组中所对应的元素值为"空"用^表示。

wKiom1VxE9ay_VjbAADLEAsJrFA338.gif



参考博文:

http://tech.ddvip.com/2014-05/1400680475210602.html

 

本文出自 “点滴积累” 博客,请务必保留此出处http://tianxingzhe.blog.51cto.com/3390077/1658816

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章
最新文章
相关文章