黑马程序员技术交流社区

标题: 关于java的二叉树 [打印本页]

作者: 陈晓东 时间: 2011-10-13 18:16
标题: 关于java的二叉树
二叉树什么时候可以用数组存储。为什么？

作者: 苏志伟 时间: 2011-10-13 19:42
我觉得我碰见爱婴斯坦了！
二叉树是java底层的一个数据结构啊！~结构怎么和数组扯上关系了....
老兄，是java相对论么？

作者: 陈晓东 时间: 2011-10-13 22:03
本帖最后由陈晓东于 2011-10-13 22:06 编辑

数据结构包括逻辑结构和存储结构啊哥哥。存储结构一般分为链式存储和顺序存储。
对于完全二叉树来说根据完全二叉树的性质可以通过当前节点的位置计算出父节点的位置，左右孩子节点位置。公式如下：
从1开始的下标
父节点=当前节点的位置编号/2 取证
左孩子节点= 当前节点的位置编号*2 如果大于数组的长度就没有左孩子节点。
右孩子节点=当前节点的位置编号*2+1 如果大于数组长度就没有右孩子节点。
因此可以用顺序存储来存储一个完全二叉树。因此可以用数组存储一个完全二叉树。
麻烦你看懂了再说好么？

作者: 陈晓东 时间: 2011-10-14 19:40
完全二叉树不一定是满二叉树，而满二叉树一定是完全二叉树。引用百度百科的说法：
http://baike.baidu.com/view/427107.htm

作者: 陈晓东 时间: 2011-10-15 16:42

苏志伟发表于 2011-10-13 19:42
我觉得我碰见爱婴斯坦了！
二叉树是java底层的一个数据结构啊！~结构怎么和数组扯上关系了....
...

这个是和同寝室黑马3期的人探讨二叉树的时候，他看过一些课外的资料。数据结构研究的比较深，懂的比较多。这些关于数据结构的是他自己抽出的课外时间和我们寝室讲解的。

作者: 邵新瑜 时间: 2012-12-6 15:58
楼上的你们说的都不太对，二叉树是可以用数组存储的！

二叉树是可以分为顺序存储和链式存储，链式存储是需要用到指针，顺序存储可以使用数组

对于二叉树来说，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点让其每个结点与完全二叉树的结点相对照，再存储到一维数组的相应分量中。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2