二叉树 BinaryTree 顺序存储线索化

二叉树 BinaryTree

二叉树BinaryTree是每个节点最多只有两个节点的树形结构，两个节点分别称为左子树和右子树。

为什么要使用树结构？
通过另外一篇文章Hash哈希表散列表我们可以看到数组和链表这两种数据结构的优点和缺点，为了提高读取、操作的效率，除了使用Hash表外，我们还可以选择树结构，比如利用二叉树既可以保证读取检索速度同时也能保证插入、删除、修改的速度。

树的常用术语

BinaryTree

节点
根节点（root节点）
父节点
子节点
叶子节点（没有子节点的节点）
节点的权（节点的值）
路径（从root节点找到该节点的路线）
层
子树
树的高度（树的最大层数）
森林（多颗子树构成森林）

二叉树的特点

每个节点最多只能有2个子节点，子节点分为左节点、右节点
满二叉树：如果二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1（n为层数）。
完全二叉树：如果二叉树的所有叶子节点都在最后一层或倒数第二层，最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续。

满二叉树
FullBinaryTree

完全二叉树
CompleteBinaryTree

二叉树的遍历

二叉树可以使用前序、中序、后序进行遍历。（看父节点输出顺序来确定是前序、中序、后序。）

前序遍历
先输出父节点，再遍历左子树，最后遍历右子树。

输出当前节点（初始开始时是root节点）
如果左子树不为空，递归进行前序遍历
如果右子树不为空，递归进行前序遍历

中序遍历
先遍历左子树，再输出父节点，最后遍历右子树。

如果左子树不为空，递归进行中序遍历
输出当前节点
如果右子树不为空，递归进行中序遍历

后序遍历
先遍历左子树，在遍历右子树，最后输出父节点。

如果左子树不为空，递归进行后序遍历
如果右子树不为空，递归进行后序遍历
输出当前节点

二叉树的查找

二叉树的有三种（前序、中序、后序）遍历方案，对应查找具体节点也对应有前序查找、中序查找、后续查找。

下面是二叉树遍历、查找代码：

/**
 * 二叉树节点
 * @author jyoryo
 */
public class BinaryTreeNode {
    private int id;
    private String name;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    
    public BinaryTreeNode(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "BinaryTreeNode [id=" + id + ", name=" + name + "]";
    }
    /**
     * 前序遍历
     * <pre>
     * 1. 输出当前节点（初始开始时是root节点）
     * 2. 如果左子树不为空，递归进行前序遍历
      * 3. 如果右子树不为空，递归进行前序遍历
     * </pre>
     */
    public void preOrder() {
        // 1、输出当前节点
        System.out.println(this);
        // 2、左子树不为空，递归进行前序遍历
        if(null != left) {
            left.preOrder();
        }
        // 3、右子树不为空，递归进行前序遍历
        if(null != right) {
            right.preOrder();
        }
    }
    /**
     * 中序遍历
     * <pre>
     * 1. 如果左子树不为空，递归进行中序遍历
      * 2. 输出当前节点
      * 3. 如果右子树不为空，递归进行中序遍历
     * </pre>
     */
    public void infixOrder() {
        // 1. 如果左子树不为空，递归进行中序遍历
        if(null != left) {
            left.infixOrder();
        }
        // 2. 输出当前节点
        System.out.println(this);
        // 3. 如果右子树不为空，递归进行中序遍历
        if(null != right) {
            right.infixOrder();
        }
    }
    /**
     * 后序遍历
     * <pre>
     * 1. 如果左子树不为空，递归进行后序遍历
      * 2. 如果右子树不为空，递归进行后序遍历
      * 3. 输出当前节点
     * </pre>
     */
    public void postOrder() {
        // 1. 如果左子树不为空，递归进行后序遍历
        if(null != left) {
            left.postOrder();
        }
        // 2. 如果右子树不为空，递归进行后序遍历
        if(null != right) {
            right.postOrder();
        }
        // 3. 输出当前节点
        System.out.println(this);
    }
    
    /**
     * 前序查找
     * @param id
     * @return
     */
    public BinaryTreeNode preOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        // 遍历左子树进行查找
        if(null != left) {
            resultNode = left.preOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 遍历右子树进行查找
        if(null != right) {
            resultNode = right.preOrderSearch(id);
        }
        return resultNode;
    }
    
    /**
     * 中序查找
     * @param id
     * @return
     */
    public BinaryTreeNode infixOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 遍历左子树进行查找
        if(null != left) {
            resultNode = left.infixOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        // 遍历右子树
        if(null != right) {
            resultNode = right.infixOrderSearch(id);
        }
        return resultNode;
    }
    
    /**
     * 后续查找
     * @param id
     * @return
     */
    public BinaryTreeNode postOrderSearch(int id) {
        BinaryTreeNode resultNode = null;
        // 遍历左子树
        if(null != left) {
            resultNode = left.postOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 遍历右子树
        if(null != right) {
            resultNode = right.postOrderSearch(id);
        }
        if(null != resultNode) {
            return resultNode;
        }
        // 当前节点
        if(id == this.getId()) {
            return this;
        }
        return resultNode;
    }
    
    // getter setter method
}

/**
 * 二叉树
 * @author jyoryo
 */
public class BinaryTree {
    private BinaryTreeNode root;

    public BinaryTree(BinaryTreeNode root) {
        super();
        this.root = root;
    }
    public void setRoot(BinaryTreeNode root) {
        this.root = root;
    }
    // 前序遍历
    public void preOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树，无法执行该操作！");
        }
        root.preOrder();
    }
    // 中序遍历
    public void infixOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树，无法执行该操作！");
        }
        root.infixOrder();
    }
    // 后序遍历
    public void postOrder() {
        if(null == root) {
            throw new RuntimeException("空二叉树，无法执行该操作！");
        }
        root.postOrder();
    }
    
    // 前序查找
    public BinaryTreeNode preOrderSearch(int id) {
        return root.preOrderSearch(id);
    }
    
    // 中序查找
    public BinaryTreeNode infixOrderSearch(int id) {
        return root.infixOrderSearch(id);
    }
    
    // 后序查找
    public BinaryTreeNode postOrderSearch(int id) {
        return root.postOrderSearch(id);
    }
}

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTreeNode node0 = new BinaryTreeNode(0, "零"),
            node1 = new BinaryTreeNode(1, "壹"),
            node2 = new BinaryTreeNode(2, "贰"),
            node3 = new BinaryTreeNode(3, "叁"),
            node4 = new BinaryTreeNode(4, "肆"),
            node5 = new BinaryTreeNode(5, "伍"),
            node6 = new BinaryTreeNode(6, "陆"),
            node7 = new BinaryTreeNode(7, "柒"),
            node8 = new BinaryTreeNode(8, "捌"),
            node9 = new BinaryTreeNode(9, "玖");
        node0.setLeft(node1);    node0.setRight(node2);
        node1.setLeft(node3);    node1.setRight(node4);
        node2.setLeft(node5);    node2.setRight(node6);
        node3.setLeft(node7);    node3.setRight(node8);
        node4.setLeft(node9);
        BinaryTree binaryTree = new BinaryTree(node0);
        // 前序遍历
        System.out.println("前序遍历");
        binaryTree.preOrder();
        // 中序遍历
        System.out.println("中序遍历");
        binaryTree.infixOrder();
        // 后序遍历
        System.out.println("后续遍历");
        binaryTree.postOrder();
        
        int findVal1 = 5, findVal2 = 15;
        // 前序查找
        System.out.println("前序查找");
        System.out.printf("查找%d，结果为：%s\n", findVal1, binaryTree.preOrderSearch(findVal1));
        System.out.printf("查找%d，结果为：%s\n\n", findVal2, binaryTree.preOrderSearch(findVal2));
        // 中序查找
        System.out.println("中序查找");
        System.out.printf("查找%d，结果为：%s\n", findVal1, binaryTree.infixOrderSearch(findVal1));
        System.out.printf("查找%d，结果为：%s\n\n", findVal2, binaryTree.infixOrderSearch(findVal2));
        // 后序查找
        System.out.println("后序查找");
        System.out.printf("查找%d，结果为：%s\n", findVal1, binaryTree.postOrderSearch(findVal1));
        System.out.printf("查找%d，结果为：%s\n\n", findVal2, binaryTree.postOrderSearch(findVal2));
    }
}

顺序存储二叉树

基本说明：从数据存储来看，数组存储方式和树的存储方式可以相互转换，及数组可以转换成树，树也可以转换成数组。

顺序存储二叉树的特点

顺序存储二叉树通常只考虑完全二叉树
n:表示二叉树中的第几个元素，按0开始编号
第n个元素的左子节点为2n + 1
第n个元素的右子节点为2n + 2
第n个元素的父节点为(n - 1) / 2

比如上面的树以数组方式存储为：array[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
顺序存储二叉树的遍历（前序遍历、中序遍历、后序遍历）：

public class ArrayBinaryTree {
    private int [] array;    // 顺序存储完全二叉树节点值的数组

    public ArrayBinaryTree(int[] array) {
        super();
        this.array = array;
    }
    
    // 前序遍历
    public void preOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空，不允许执行该操作！");
        }
        // 1、输出当前元素
        System.out.println(array[index]);
        // 2、向左递归
        if((2 * index + 1) < array.length) {
            preOrder(2 * index + 1);
        }
        // 3、向右递归
        if((2 * index + 2) < array.length) {
            preOrder(2 * index + 2);
        }
    }
    
    // 中序遍历
    public void infixOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空，不允许执行该操作！");
        }
        // 1、向左递归
        if((2 * index + 1) < array.length) {
            infixOrder(2 * index + 1);
        }
        // 2、输出当前元素
        System.out.println(array[index]);
        // 3、向右递归
        if((2 * index + 2) < array.length) {
            infixOrder(2 * index + 2);
        }
    }
    
    // 后序遍历
    public void postOrder(int index) {
        if(null == array || 0 >= array.length) {
            throw new RuntimeException("数组为空，不允许执行该操作！");
        }
        // 1、向左递归
        if((2 * index + 1) < array.length) {
            postOrder(2 * index + 1);
        }
        // 2、向右递归
        if((2 * index + 2) < array.length) {
            postOrder(2 * index + 2);
        }
        // 3、输入当前元素
        System.out.println(array[index]);
    }
}

public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        int [] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(array);
        // 前序遍历
        arrayBinaryTree.preOrder(0);
        // 中序遍历
        arrayBinaryTree.infixOrder(0);
        // 后序遍历
        arrayBinaryTree.postOrder(0);
    }
}

二叉树 BinaryTree 顺序存储线索化