13.3.2 遍历前序线索树

我的个人理解：所谓的前序遍历就是每读到一个节点，就输出他的值，先左后右，这是一般二叉树的思路，但是，线索二叉树，子叶节点可能存在前驱和后继结点，那么，我们可以利用这一点，如果当前节点存在后继节点，我们直接在输出完当前节点后直接指向后继结点（按照一点的递归思想我们是一步一步返回去，然后再向右查找，由于存在后继节点，那么我们可以直接利用，大大缩短了查询效率）

package tree.threadedbinarytree;


public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        // 测试 把中序线索二叉树
        Node1 root = new Node1(1, "12");
        Node1 node2 = new Node1(3, "13");
        Node1 node3 = new Node1(6, "16");
        Node1 node4 = new Node1(8, "18");
        Node1 node5 = new Node1(10, "114");
        Node1 node6 = new Node1(14, "114");

        // 二叉树后面要递归创建,现在手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        infixThreadedBinaryTree infixThreadedBinaryTree = new infixThreadedBinaryTree();


        // 测试前序线索化
        infixThreadedBinaryTree.setRoot(root);
        infixThreadedBinaryTree.preNodes();

        // 测试:以10号结点为测试
        Node1 leftNode = node5.getLeft();
        Node1 rightNode = node5.getRight();
        System.out.println("10号结点的前驱结点时:" + leftNode);
        System.out.println("10号结点的后继结点" + rightNode);

        System.out.println("前序线索树遍历");
        infixThreadedBinaryTree.preThreadedList();
    }
}
// 线索化二叉树 实现了线索化功能的二叉树
class infixThreadedBinaryTree{
    private Node1 root;

    // 为了实现线索化,需要创建要给指向当前节点的前驱结点的指针
    // 在递归的进行线索时,pre 总是保留一个结点
    private Node1 pre = null;

    // 遍历中序线索二叉树
    public void infixThreadedList(){
        // 定义一个变量，存储当前遍历的节点，从root开始
        Node1 node = root;
        while(node != null){
            // 循环的找到leftType == 1的节点，第一个找到的就是8
            // 后面随着遍历node会变化，
            // 因为当leftType == 1时，说明该节点时按照线索化处理后的有效节点
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            // 打印当前节点
            System.out.println(node);
            // 如果当前节点的右指针指向的是后继结点，就一直输出
            while (node.getRightType() == 1){
                // 说明当前节点指向后继结点
                // 获取当前节点的后继结点
                node = node.getRight();
                System.out.println(node);
            }
            // 替换这个便利的节点
            node = node.getRight();
        }
    }

    // 遍历前序线索二叉树
    public void preThreadedList(){
        Node1 node = root;
        System.out.println(node); // 先输出当前node的值
        while (node != null){
            // 然后判断左节点是否是前驱结点，如果不是且不为空，就输出它的左孩子，并且指针指向左节点，进行下一次循环
            if (node.getLeftType() == 0 && node.getLeft() != null){
                System.out.println(node.getLeft());
                node = node.getLeft();
                continue;
            }
            // 判断右节点是否是后继结点，如果不是且为不为空，就输出它的右孩子，并且指针指向右节点，进行下一次循环
            if (node.getRightType() == 0 && node.getRight() != null){
                System.out.println(node.getRight());
                node = node.getRight();
                continue;
            }
            // 判断当前节点的右节点是否是后继结点，如果是，直接输出它的后继结点，然后指针指向后继结点
            if (node.getRightType() == 1){
                System.out.println(node.getRight());
                node = node.getRight();
            }

        }
    }
    // 重载一把threadeNodes方法
    public void threadeNodes(){
        this.threadedNodes(root);
    }
    // 编写二叉树进行中序线索化的方法
    /**
     *
     * @param node 就是当前需要线索化的结点
     */
    public void threadedNodes(Node1 node){
        // 如果 node == null,不能进行线索化
        if (node == null){
            return;
        }
        // 1. 先线索化左子树
        threadedNodes(node.getLeft());
        // 2. 线索化当前结点
        // 2.1 先处理当前节点的前驱结点
        if (node.getLeft() == null){
            // 让当前节点的左指针指向前驱结点
            node.setLeft(pre);
            // 修改当前节点的左指针的类型,指向前驱结点
            node.setLeftType(1);
        }
        // 2.2 处理当前节点的后继结点
        if (pre != null && pre.getRight() == null){
            // 让前驱结点的右指针指向当前结点
            pre.setRight(node);
            // 修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        // 没处理一个节点后,让当前结点时下一个节点的前驱结点
        pre = node;
        // 3. 再线索化右子树
        threadedNodes(node.getRight());
    }

    public void preNodes(){
        this.preNodes(root);
    }
    // 前序线索化
    public void preNodes(Node1 node){
        if (node == null){
            return;
        }
        if (node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        if (node.getLeftType() == 0){
            preNodes(node.getLeft());
        }

        if (node.getRightType() == 0){
            preNodes(node.getRight());
        }

    }
    // 后序线索化
    public void postNodes(){
        this.postNodes(root);
    }
    public void postNodes(Node1 node){
        if (node == null){
            return;
        }
        postNodes(node.getLeft());
        postNodes(node.getRight());
        if (node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if ( pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }

        pre = node;
    }
    public void setRoot(Node1 root) {
        this.root = root;
    }


}
// 先创建节点
class Node1{
    private int id;
    private String name;
    private Node1 left;
    private Node1 right;
    // 说明
    // 1. 如果leftType == 0 表示的指向的是左子树,如果1则表示指向前驱结点
    // 2. 如果rightType == 0 表示指向的是右子树,如果1则表示指向的是后继结点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public Node1(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node1 getLeft() {
        return left;
    }

    public void setLeft(Node1 left) {
        this.left = left;
    }

    public Node1 getRight() {
        return right;
    }

    public void setRight(Node1 right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Node1{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

}