二叉树是一类非常重要的特殊的树形结构
二叉树 的定义
在二叉树中，每个结点至多有2个儿子，并且有左、右之分。
位于左边的孩子叫做左孩子
位于右边的孩子叫做右孩子
二叉树的性质
若二叉树的层次从 1 开始计数, 则，在二叉树的第i 层最多有 2i－1个结点。( i>=1)
高度为 k 的二叉树最多有2k-1个结点
具有n (n>=1) 个结点的二叉树的高度最多为n
对任何一棵二叉树, 如果其叶结点有n0 个, 度为2的结点有n2 个, 则有n0＝n2＋1
两种特殊的二叉树
满二叉树:一棵高度为h且有2h-1个结点的二叉树。
完全二叉树 (也叫近似满二叉树 ):若将满二叉树最后一层的结点，从右向左连续缺若干结点，就是完全二叉树。
二叉树的存储结构（重点）
二叉树的顺序存储结构
二叉树的链式存储结构
二叉树的遍历
先序遍历 中序遍历 后序遍历
① 访问根结点 ① 按中序遍历左子树 ① 按后序遍历左子树
② 按先序遍历左子树 ② 访问根结点 ② 按后序遍历右子树
③ 按先序遍历右子树 ③ 按中序遍历右子树 ③ 访问根结点
由遍历序列确定二叉树
|
两种遍历序列的组合
|
是否能唯一确定二叉树
|
|
先序 + 中序
|
是 |
|
后序 + 中序
|
是 |
|
先序 + 后序
|
否 |