二叉树 Binary Tree

概述

满二叉树和完全二叉树

检索

顺序存储二叉树

堆排序会用到

1. 通常只考虑完全二叉树
2. 当前左子节点：2*n+1
3. 当前右子节点：2*n+2
4. 当前父节点: (n-1)/2

以树的三种顺序读取数组

class arrToTree{
    private int[] arr;

    public arrToTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder(int index){
        if(arr == null || arr.length == 0){
            System.out.println("empty array");
        }
        System.out.println(arr[index]);
        if((index*2+1)< arr.length){
            preOrder(2*index+1);
        }
        if((index*2+2)< arr.length){
            preOrder(2*index+2);
        }
    }

    public void inOrder(int index){
        if(arr == null || arr.length == 0){
            System.out.println("empty array");
        }
        if((index*2+1)< arr.length){
            preOrder(2*index+1);
        }
        System.out.println(arr[index]);
        if((index*2+2)< arr.length){
            preOrder(2*index+2);
        }
    }
    public void postOrder(int index){
        if(arr == null || arr.length == 0){
            System.out.println("empty array");
        }
        if((index*2+1)< arr.length){
            preOrder(2*index+1);
        }

        if((index*2+2)< arr.length){
            preOrder(2*index+2);
        }
        System.out.println(arr[index]);
    }
}

测试

public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        arrToTree tree = new arrToTree(arr);
        tree.preOrder(0);
        tree.postOrder(0);
        tree.inOrder(0);
    }

线索化二叉树

1. n个节点的二叉树中有n+1个空指针。
2. 利用空指针存放当前节点前驱和后继节点，称为线索
3. 线索分为前序，中序，后序
4. left有可能指向左子树而不是前驱
5. right有可能指向右子树而非后继