赞
踩
之所以会出现完全二叉树的概念,是因为可由此在物理上,以线性表的方式实现逻辑上的完全二叉树。
对于一棵高度为
我自己得到的一些结论如下:
- 从 0 开始编号,编号为奇数的必定在左子节点,编号为偶数的必定在右子节点;
- 对某一个内部结点(internal node)而言,不可能出现有右子节点,而没有左子节点的情况;
- 完全二叉树与线性结构有自然的双向映射;
n 个结点的完全二叉树的叶节点的范围是n2∼n
- 也即对完全二叉树而言,(后)一半是叶节点,(前)一半是内部结点(包括根节点)
证,设完全二叉树
也即
(完全二叉树)如果
证明如下,使用数学归纳法,
同样,分
完全二叉树的一个重要特性,如上证明,它可以十分方便地存入一个表或数组,直接根据元素下标(index)就能找到下标对应结点的子节点或父节点,无须以其他方式记录树的结构信息。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。