顺序二叉树

java顺序二叉树的前序、中序、后序遍历

二叉树的顺序存储是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。

二叉树的顺序存储必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。

二叉树的性质：

1、 二叉树第i层上的结点数目最多为 2^(i-1)其中 (i≥1)。

2、 深度为k的二叉树至多有2^k-1个结点(k≥1)。

3、 包含n个结点的二叉树的高度至少为log2 (n+1)。

4、 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

java代码实现：

//顺序二叉树
public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5};
        ArrBingaryTree arrBingaryTree = new ArrBingaryTree(arr);
        System.out.println("顺序二叉树前序遍历");
        arrBingaryTree.preOrder(0);
        System.out.println("顺序二叉树中序遍历");
        arrBingaryTree.infixOrder(0);
        System.out.println("顺序二叉树后序遍历");
        arrBingaryTree.postOrder(0);
    }

}


/**
 * 顺序存储二叉树的特点
 * 1.顺序二叉树通常只考虑完全二叉树
 * 2.第n个元素的左子结点为 2*n+1
 * 3.第n个元素的右子结点为 2*n+2
 * 4.第n个元素的父节点为（n-1）/2
 * 5.index:表示二叉树中的第几个元素
 */
class ArrBingaryTree{
    int[] arr;
    public ArrBingaryTree(int[] arr) {
        this.arr = arr;
    }

    //先序遍历
    public void preOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，前序遍历失败");
        }
        System.out.println(arr[index]);
        if ((index*2+1)<arr.length){
            preOrder(index*2+1);
        }
        if ((index*2+2)<arr.length){
            preOrder(2*index+2);
        }
    }


    //中序遍历
    public void infixOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，中序遍历失败");
        }
        if ((index*2+1)<arr.length){
            infixOrder(2*index+1);
        }
        System.out.println(arr[index]);
        if ((index*2+2)<arr.length){
            infixOrder(index*2+2);
        }
    }

    //后序遍历
    public void postOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，后序遍历失败");
        }
        if ((index*2+1)<arr.length){
            postOrder(2*index+1);
        }
        if ((index*2+2)<arr.length){
            postOrder(index*2+2);
        }
        System.out.println(arr[index]);
    }

}