本文共 2258 字，大约阅读时间需要 7 分钟。

顺序存储二叉树

基本说明

从数据存储来看，数组存储方式和树的存储方式可以相互转换

数组    《------》    树

要求：在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式来完成对结点的遍历。

概念

1. 顺序存储二叉树通常仅仅考虑完全二叉树
2. 第n个元素的左子节点为2 * n + 1；
3. 第n个元素的右子节点为2 * n + 2；
4. 第n个节点的父节点为（n - 1） /2；
5. n表示为二叉树中第几个元素（注意：编号是从0开始记的）

图示：

应用实例

八大排序算法中的堆排序，使用的就是顺序存储为叉树。

用顺序存储二叉树实现树的三种遍历

1. 前序遍历：

• 思路分析：
  • 判断树是否为空
  • 先输出根节点，
  • 在判定左子节点是否为空，在进行左子结点的递归输出
  • 最后判定右子结点是否为空，在进行递归输出
  • 没有了就return
• 代码实现：

public void preOrder(){
       this.preOrder(0);}//重载方法，是程序看起来更加干净简洁/**\ * * @param index  标识为数组的下标 * */public void preOrder(int index){
       if (arr == null || arr.length == 0){
           //有没有数组长度为0，还不为空的数组        //经过实验发现，确实存在如此蛋疼的数组        //两种情况，数组未初始化；已经初始化了，但是长度为0        System.out.println("树为空，无法遍历");        return;    }    System.out.println(arr[index]);    if (2 * index + 1 < arr.length){
           //下标小于数组的长度，说明没有越界        preOrder(2 * index + 1);    }    if (2 * index + 2 < arr.length){
           preOrder(2 * index + 2);    }}

2. 中序遍历

• 思路分析
  • 先判定树是否为空，包含两种情况：数组没有初始化或者是初始化的长度为0
  • 判定左子节点是否为空，不为空进行递归遍历
  • 输出当前节点
  • 在判定右子节点是否为空，不为空在进行递归遍历
  • 完全都没有在return退出当前语句
• 代码实现：

public void midOrder(){
           this.midOrder(0);    }public void midOrder(int index){
           //判定树是否存在或者是未初始化        if (arr == null || arr.length == 0){
               System.out.println("the tree is empty");            return;        }        if (2 * index + 1 < arr.length){
               midOrder(2 * index + 1);        }        System.out.print(arr[index]  + "---");        if(2 * index + 2 < arr.length){
               midOrder(2 * index + 2);        }        return;    }

3. 后序遍历

• 思路分析
  • 先判定数组是否为空，或者初始化长度为0
  • 左子结点是否空，不为空，进行递归调用
  • 右子结点是否空，不为空，进行递归调用
  • 输出当前节点
• 代码实现：

public void postOrder(){
           this.postOrder(0);    }  public void postOrder(int index){
           if(arr == null || arr.length == 0){
               System.out.println("树为空，无法遍历");            return;        }        if (2 * index + 1 < arr.length){
               postOrder(2 * index + 1);        }        if (2 * index + 2 < arr.length){
               postOrder(2 * index + 2);        }        System.out.print(arr[index] + "---");    }

分析与总结

1. 熟练使用顺序存储二叉树的基础是建立在左下表之间的关系熟练运用的基础上的
2. 会使用return给没有返回值的方法设置终端出口
3. 对比树的三种遍历方式递归，是采用this.left != null,采用左子节点是否为空的基础判定是否为叶子节点。二叉树的顺序存储结构使用数组的角标是否越界来判定的
4. 用二叉树的顺序存储结构判定数组的为空，两种特殊情况，一种是数组未初始化，另外一种是数组初始化了，但是长度为0

转载地址：http://sqgpb.baihongyu.com/