完全二叉树基本知识（一）

二叉树：

1. 特点是与每个结点关联的子结点至多有两个（可为0，1，2），即一个结点至多有两棵子树。
2. 二叉树的两棵子树分别称作它的左子树和右子树，即：子树有左右之分（因此二叉树与树有不同结构，不是树的特殊情况）。

概念:

• 满二叉树：树中每个分支结点（非叶结点）都有两棵非空子树

满二叉树

• 完全二叉树：对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。

两棵完全二叉树

完全二叉树最重要的性质：如果n个节点的完全二叉树的节点按照层次并按从左到右的顺序从0开始编号，对于人一个绩点都有：

• 序号为0的节点是根
• 对于i>0，其父节点的编号为(i-1)/2。
• 若2·i+1<n，其左子节点的序号为2·i+1，否则没有左子节点。
• 若2·i+2<n，其右子节点的序号为2·i+2，否则没有右子节点。

• 上述是二叉树最重要的性质：

• 使二叉树可以方便的存入表或者数组，直接根绝元素下标就可以找到一个节点的子节点或者父节点(也就是可以完全确定二叉树的结构)，无须用额外的形式记录树结构信息。
• 使其可以方便地存入一系列连续位置，一般二叉树不能方便地映射到线性结构，完全二叉树到线性结构有定义非常自然的双向映射，可以方便地从其线性结构恢复完全二叉树。

遍历二叉树：就是按照系统化的方式访问二叉树里的每一个节点。

• 这是二叉树的一个重要性质：每棵二叉树都有唯一的根节点，可以将其看做这棵二叉树的唯一标识，是基于树结构的处理入口。

• 深度优先遍历：按照一条路径尽可能的向前探索， 直至检查完一个叶节点。
  遍历左子树、遍历右子树和访问根节点。
  根据这三项工作的不同执行顺序，就可以得到三种常见遍历顺序（因为要先处理左子树，所以不是6种而是3种）

遍历实例

1. 先根序遍历：先访问根节点，而后以同样的方式顺序遍历左子树和右子树。
   结果：A -> B -> D -> H -> E -> I -> C -> F -> J -> K ->G

2.后根序遍历：先以同样的方式遍历左右子树，最后遍历根节点。
结果：H -> D -> I -> E -> B -> J -> K -> F -> G -> C -> A

3.中根序遍历：先以同样的方式遍历左子树，然后访问根节点，最后以同样的方式遍历右子树。
结果： D -> H ->B -> E -> I -> A -> J -> F -> K -> C -> G

根据给定的二叉树唯一确定它的先根序列、后根序列和中根序列，但是给定任意一棵树的任意一种遍历序列都无法唯一确定相应的二叉树。

• 宽度优先遍历：在所有路径上齐头并进。宽度优先遍历是按照路径长度由近到远访问节点。也就是说按照二叉树的层数逐层访问树中的节点。