二叉树的存储和遍历

目录

• 二叉树
• • 一、二叉树的概念
  • 二、二叉树的性质
  • 三、二叉树的存储结构
  • • 1. 顺序存储
    • 2. 链式存储
  • 四、二叉树的遍历
  • • 1. 前序遍历方式
    • 2. 中序遍历方式
    • 3. 后序遍历方式
  • 五、小结

二叉树 一、二叉树的概念

1. 二叉树由根节点、左子树和右子树三部分组成，二叉树中的每一个节点的度都不大于2，即每个根节点最多只能有两棵子树。
2. 二叉树的节点数是有限的，左右子树有次序且不可颠倒，没有子节点的节点称为叶子节点。
3. 二叉树可以是一棵空树，可以是只包含根节点的二叉树，也可以缺失左子树或者右子树。
4. 二叉树的两种特殊形态：完全二叉树和满二叉树，任意一棵满二叉树必定是完全二叉树，但任一完全二叉树不一定是满二叉树。

图1. 满二叉树与完全二叉树 二、二叉树的性质

1. 性质1：二叉树第 i {i} i 层上的节点数最多为 2 i − 1 \bm{2^{i-1}} 2i−1 ( i {i} i > 0)。
2. 性质2：深度为k的二叉树最多有 2 k − 1 \bm{2^k-1} 2k−1个节点。二叉树的每一层节点排满时即为整个二叉树节点数最多的时候，根据性质1可得：总结点数 = 2 0 2^0 20 + 2 1 2^1 21 + 2 2 2^2 22 + 2 3 2^3 23 +…+ 2 k − 1 2^{k-1} 2k−1 = 2 k − 1 2^k-1 2k−1
3. 性质3：二叉树中，叶子节点数目等于度为2的节点数目加1。
4. 性质4：具有n个节点的完全二叉树的深度为( log ⁡ 2 n \log_2n log2​n)+1。
5. 性质5：如果对一棵有n个节点的完全二叉树按层序自左向右、自上向下编号，则树中任一节点 i i i (1 < i i i < n) 满足：
     (1) 若 i i i > 1 , 其父节点的编号为 i / 2 i/2 i/2。
     (2) 若 2 i 2i 2i > n , 则 i i i 没有左孩子。
     (3) 若 2 i 2i 2i+1 > n , 则 i i i 没有右孩子。
     (4) 若 i i i 为奇数，则 i i i 的左兄弟编号为 i i i-1。
     (5) 若 i i i 为偶数，则 i i i 的右兄弟编号为 i i i+1。

三、二叉树的存储结构 1. 顺序存储

  完全二叉树采用顺序存储结构，使用数组存储。非完全二叉树要使用数组存储，就要存许多空节点，会造成空间浪费。

图2. 补充满的非完全二叉树

按层序将二叉树存储在数组中：

图3. 二叉树存储在数组中的形式 2. 链式存储

  二叉树也可以采用链式存储结构，由一个包含数据域、左孩子链域和右孩子链域三个部分的二叉链表存储。

按层序将二叉树存储在二叉链表中：

图4. 二叉树存储在二叉链表中的形式 四、二叉树的遍历

图5. 二叉树遍历例图 1. 前序遍历方式

  前序遍历算法：若二叉树非空，先访问根节点，然后前序遍历左子树，最后前序遍历右子树。如图5，前序遍历的结果为：ABDGHECFI

图6. 前序遍历二叉树步骤图 2. 中序遍历方式

  中序遍历算法：若二叉树非空，先中序遍历左子树，然后访问根节点，最后中序遍历右子树。如图5，中序遍历的结果为：GDHBEACIF

3. 后序遍历方式

  后序遍历算法：若二叉树非空，先后序遍历左子树，然后后序遍历右子树，最后访问根节点。如图5，后序遍历的结果为：GHDEBIFCA

五、小结

   二叉树虽然不是线性结构，但采用顺序存储结构和链式存储结构都可以存储。二叉树可以采用多种遍历方式，所以遍历的结果是不唯一的。