算法test008

实现线索二叉树
public class test008 {
private Node preNode; //线索化时记录前一个节点

    //节点存储结构
    public static class Node {
        int data;        //数据域
        Node left;          //左指针域
        Node right;         //右指针域
        boolean isLeftThread = false;   //左指针域类型  false：指向子节点、true：前驱或后继线索
        boolean isRightThread = false;  //右指针域类型  false：指向子节点、true：前驱或后继线索

        Node(int data) {
            this.data = data;
        }
    }

    /**
     * 通过数组构造一个二叉树（完全二叉树）
     * @param array
     * @param index
     * @return
     */
    public static Node createBinaryTree(int[] array, int index) {
        Node node = null;

        if(index < array.length) {
            node = new Node(array[index]);
            node.left = createBinaryTree(array, index * 2 + 1);
            node.right = createBinaryTree(array, index * 2 + 2);
        }

        return node;
    }

    /**
     * 中序线索化二叉树
     * @param node  节点
     */
    public void inThreadOrder(Node node) {
        if(node == null) {
            return;
        }

        //处理左子树
        inThreadOrder(node.left);

        //左指针为空,将左指针指向前驱节点
        if(node.left == null) {
            node.left = preNode;
            node.isLeftThread = true;
        }

        //前一个节点的后继节点指向当前节点
        if(preNode != null && preNode.right == null) {
            preNode.right = node;
            preNode.isRightThread = true;
        }
        preNode = node;

        //处理右子树
        inThreadOrder(node.right);
    }

}
欢迎交流指正~