跳到主要内容

十七：顺序储存二叉树、线索化二叉树

一、顺序储存二叉树​

1.1 概念​

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，
看下面的示意图。
 

1.2 特点​

  • 顺序二叉树通常只考虑 完全二叉树:

1、 第n个元素的左子节点为2*n+1；
2、 第n个元素的右子节点为2*n+2；
3、 第n个元素的父节点为**(n-1)/2**；

  • n : 表示二叉树中的第几个元素(按0开始编号如图所示,同时对应的也是数组的顺序)
     

复习一下完全二叉树：如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为 完全二叉树。

1.3 关系​

树的存储方式可以与数组的方式可以互换，我看出来的一个规律，二叉树的层次遍历就是数组的储存方式。

如果要将二叉树转为数组存储，既可以层次遍历然后储存到数组中即可。

1.4 案例​

1、 上图的二叉树的结点，要求以数组的方式来存放array:[1,2,3,4,5,6,7]；
2、 要求在遍历数组array时，仍然可以以**前序遍历，中序遍历和后序遍历**的方式完成结点的遍历；
3、 手写三种遍历，与代码进行比较；
前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1

1.5 代码实现​

1.5.1 ArrayBinaryTree 二叉树类​

package com.feng.ch12_tree.t2_arraybinarytree;

/*
 * 编写一个 ArrayBinaryTree， 实现顺序存储二叉树遍历
 * 数组 和 二叉树的 对应规律
 * */
class ArrayBinaryTree {
   
     

    private int[] array; // 存储数据结点的数组

    public ArrayBinaryTree(int[] array) {
   
     
        this.array = array;
    }

    // 重载perOrder（）
    public void preOrder() {
   
     
        this.preOrder(0);
    }
    public void infixOrder() {
   
     
        this.infixOrder(0);
    }
    public void postOrder() {
   
     
        this.postOrder(0);
    }

    /*
     * 编写一个方法，完成顺序储存二叉树的一个前序遍历
     * @param index 数组的下标
     * */
    public void preOrder(int index) {
   
     
        // 如果数组为空，或者 array。length = 0
        if (array == null || array.length == 0) {
   
     
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        // 输出当前这个元素
        System.out.print(array[index] + " ");
        // 向左递归遍历
        if ((index * 2 + 1) < array.length) {
   
     
            preOrder(2 * index + 1);
        }

        // 向右递归遍历
        if ((index * 2 + 2) < array.length) {
   
     
            preOrder(2 * index + 2);
        }
    }

    /*
     * 方法，完成顺序储存二叉树的一个中序遍历
     * @param index 数组的下标
     * */
    public void infixOrder(int index){
   
     
        // 如果数组为空，或者 array。length = 0
        if (array == null || array.length == 0) {
   
     
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        // 向左递归遍历
        if ((index * 2 + 1) < array.length) {
   
     
            infixOrder(2 * index + 1);
        }
        // 输出当前这个元素
        System.out.print(array[index] + " ");
        // 向右递归遍历
        if ((index * 2 + 2) < array.length) {
   
     
            infixOrder(2 * index + 2);
        }

    }

    /*
     * 方法，完成顺序储存二叉树的一个后序遍历
     * @param index 数组的下标
     * */
    public void postOrder(int index){
   
     
        // 如果数组为空，或者 array。length = 0
        if (array == null || array.length == 0) {
   
     
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        // 向左递归遍历
        if ((index * 2 + 1) < array.length) {
   
     
            postOrder(2 * index + 1);
        }
        // 向右递归遍历
        if ((index * 2 + 2) < array.length) {
   
     
            postOrder(2 * index + 2);
        }
        // 输出当前这个元素
        System.out.print(array[index] + " ");
    }
}