1.二叉树的定义
二叉树是另一种树形结构,其特点是每个结点至多只有两颗子树,并且二叉树的子树有左右之分,其次序不能任意点到。
2.特殊的二叉树
满二叉树
完全二叉树
二叉排序树
平衡二叉树
3.二叉树的性质
非空二叉树上的叶子结点树等于度为2的结点树加1
非空二叉树上第k层至多2的k-1次方个结点
高度为h的二叉树至多有2的h次方减1个结点
对完全二叉树按丛上到下,从左到右的顺序依次编号
当i大于1时,结点i的双亲编号为i除以2向下取整
结点i的左孩子为2i
结点i的右孩子为2i+1
结点i所在层次为对i取以2为底的对数向下取整后加1
具有n个结点的完全二叉树的高度为n+1取对数向上取整,或对n取对数加1向下取整
4.二叉树的存储结构
顺序存储结构
链式存储结构
网友评论