二叉树线索化和前序、中序、后序的遍历

二叉树的中序线索化

public void threadedNodes(Node node) {
        //如果node == null，不能线索化
        if (node == null) {
            return;
        }

        //1.先线索化左子树
        if (node.getLeftType() == 0) {
            threadedNodes(node.getLeft());
        }

        //2.线索化当前节点
        if (node.getLeft() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前结点的左指针的类型
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre!= null && pre.getRight() == null) {
            //让前驱节点的右指针指向当前结点
            pre.setRight(node);
            //修改前驱节点的右指针类型
            pre.setRightType(1);
        }
        //!!!每处理一个结点后，让当前结点是下一个前驱节点
        pre = node;

        //3.线索化右子树
        if (node.getRightType() == 0) {
            threadedNodes(node.getRight());
        }
    }

总体来看，线索化的顺序和遍历的顺序类似，比如中序线索化，就按照中序遍历的顺序，先递归线索化左子树，再线索化当前结点，再递归线索化右子树。注意在判断是否进入递归加上 if (node.getRightType() == 0)这种条件，否则可能会栈溢出。

中序线索化二叉树的遍历

public void threadedList() {
        //定义一个变量，存储当前遍历的结点，从root开始
        Node node = root;
        while (node != null) {
            //循环找到leftType == 1的结点，第一个找到的就是8结点
            //后面随着遍历而变化,因为当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();
        }
    }

虽然说线索化的步骤大同小异，但是遍历的方法却是各有各的特点。对于中序遍历，首先需要通过node = node.getLeft()找到按照中序遍历最左端的元素，从最左端的开始，只要右指针指向后继结点，就一直输出。如果当前结点右指针指向的不是后继结点，就把当前结点转移到右指针指向的结点，重复循环操作。

二叉树的前序线索化

public void threadedNodes2(Node 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) {
            threadedNodes2(node.getLeft());
        }

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

前序线索化二叉树的遍历

public void threadedList2() {
        Node node = root;
        while (node != null) {

            System.out.println(node);

            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }

            if (node.getLeftType() == 0) {
                node = node.getLeft();
            } else {
                node = node.getRight();
            }
        }
    }

对于前序线索化的遍历，由于前序遍历首先输出的肯定是根节点，所以根结点本身就是前序遍历顺序的头节点。然后从根结点开始，只要右指针指向后继结点，就一直输出。当右指针指向的不是后继结点时，就判断当前结点左边的结点类型，如果不是前驱节点，就把当前结点左移至下一结点。如果是前驱节点，则右移，循环操作。

二叉树的后序线索化

public void threadedNodes3(Node node) {
        if (node == null) {
            return;
        }

        if (node.getLeftType() == 0) {
            threadedNodes3(node.getLeft());
        }

        if (node.getRightType() == 0) {
            threadedNodes3(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 threadedList3() {
        if (node.getLeftType() == 0) {
            threadedList3(node.getLeft());
        }
        if (node.getRightType() == 0) {
            threadedList3(node.getRight());
        }
       System.out.println(node);
}

用递归就体现不出线索化的特点了，线索化相对于递归，在遍历时显然更节约资源。

public void threadedList3() {
        Node node = root;
        while (node != null) {
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            if (node != root) {
                node = node.parent.getRight();
            } else {
                return;
            }

        }
    }

后序遍历最后输出的必然是根结点，但是后序遍历相对来讲总是更麻烦一些。思路类似，只是后继结点链断掉以后，需要把结点从当前节点的移到当前结点父节点的右端结点。父节点作为一个成员变量定义到结点类中，初始化可参照如下：

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        node2.parent = root;
        node3.parent = root;
        node4.parent = node2;
        node5.parent = node2;
        node6.parent = node3;

二叉树线索化和前序、中序、后序的遍历

原文：https://www.cnblogs.com/LostSecretGarden/p/14730174.html