【❤️算法系列之顺序二叉树的实现（前序遍历、中序遍历、后序遍历）❤️】

• 1.何为顺序二叉树
• 2.顺序二叉树的特点
• 3.顺序二叉树的遍历
• • 3.1.前序遍历
  • 3.2.中序遍历
  • 3.3.后序遍历
• 4.顺序二叉树的注意点

顺序二叉树本质上维护了一个数组，也就是通过数组存储实现的，适用于完全二叉树

(1)顺序二叉树通常只考虑完全二叉树
(2)第n个元素的左子节点为 2 * n + 1
(3)第n个元素的右子节点为 2 * n + 2
(4)第n个元素的父节点为 (n - 1) / 2

n为数组中元素的下标

    protected void preOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        System.out.print(arr[n]+"->");
        preOrder(2 * n + 1);
        preOrder(2 * n + 2);
    }

    protected void infixOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        preOrder(2 * n + 1);
        System.out.println(arr[n] + "->");
        preOrder(2 * n + 2);
    }

    
    public void sufOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        preOrder(2 * n + 1);
        preOrder(2 * n + 2);
        System.out.println(arr[n] + "->");
    }

全代码

public class SeqBinaryTree {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        System.out.println("前序遍历结果如下:");
        ArrBinaryTree binaryTree = new ArrBinaryTree(arr);
        binaryTree.preOrder(0);
        System.out.println();
        System.out.println("中序遍历结果如下:");
        binaryTree.infixOrder(0);
        System.out.println();
        System.out.println("后续遍历结果如下:");
        binaryTree.sufOrder(0);
    }


}
class ArrBinaryTree {
    private int[] arr;
    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }
    
    protected void preOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        System.out.print(arr[n]+"->");
        preOrder(2 * n + 1);
        preOrder(2 * n + 2);
    }

    
    protected void infixOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        preOrder(2 * n + 1);
        System.out.println(arr[n] + "->");
        preOrder(2 * n + 2);
    }

    
    public void sufOrder(int n) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历!");
        }
        if (n > arr.length - 1) {
            return;
        }
        preOrder(2 * n + 1);
        preOrder(2 * n + 2);
        System.out.println(arr[n] + "->");
    }
}

1.对于完全二叉树，使用数组来实现节省空间，对于其他类型的二叉树就不适用了。
2.对于顺序二叉树底层维护了一个数组，这个数组需要提前确定大小，所以增删节点会很麻烦.