Java实现线索化二叉树并遍历前序中序后序

/** * 线索化二叉树的节点 */public class IndexNode {    public int id;    public String name;    public IndexNode left;    public IndexNode right;    public IndexNode parent = null; // 后序线索化的时候需要使用    public boolean isLeftIndexed;  // 0 表示left指针指向左子树， 1 表示left指针指向前驱节点    public boolean isRightIndexed; // 0 表示right指针指向右子树， 1 表示right指针指向后继节点    public IndexNode(int id, String name) {        this.id = id;        this.name = name;    }    @Override    public String toString() {        return "[" + id + "," + name + "]";    }    // 前序遍历    public void preOrder() {        System.out.println(this);        if (left != null) left.preOrder();        if (right != null) right.preOrder();    }    // 中序遍历    public void infixOrder() {        if (left != null) left.infixOrder();        System.out.println(this);        if (right != null) right.infixOrder();    }    // 后序遍历    public void postOrder() {        if (left != null) left.postOrder();        if (right != null) right.postOrder();        System.out.println(this);    }}

/** * 实现线索化功能的二叉树 */public class IndexBinaryTree {    IndexNode root;    // 为了实现线索化，需要一个pre指针，指向当前节点的前驱    // 进行线索化的时候，pre总是指向前一个节点    IndexNode pre = null;    /** 前序遍历 */    public void preOrder() {        if (root == null) {            System.out.println("空树，无法遍历");            return;        }        root.preOrder();    }    /** 中序遍历 */    public void infixOrder() {        if (root == null) {            System.out.println("空树，无法遍历");            return;        }        root.infixOrder();    }    /** 后序遍历 */    public void postOrder() {        if (root == null) {            System.out.println("空树，无法遍历");            return;        }        root.postOrder();    }    /** 对二叉树进行中序线索化 */    public void infixOrderIndexTree() {        if (root == null) return;        infixOrderIndexTree(root);    }    /** 对二叉树进行前序线索化 */    public void preOrderIndexTree() {        if (root == null) return;        preOrderIndexTree(root);    }    /** 对二叉树进行后序线索化 */    public void postOrderIndexTree() {        if (root == null) return;        postOrderIndexTree(root);    }    /** 遍历经过中序线索化后的二叉树 */    public void showInfixOrderIndexedTree() {        IndexNode cur = root;        while (cur != null) {            // cur一直循环向下找，找到 leftType = 1 的节点            while (!cur.isLeftIndexed) cur = cur.left;            // 打印cur            System.out.println(cur);            // 若cur的右指针指向的是后继节点，就一直更新，然后输出            while (cur.isRightIndexed) {                cur = cur.right;                System.out.println(cur);            }            // 更新cur节点            cur = cur.right;        }    }    /** 遍历经过前序线索化后的二叉树 */    public void showPreOrderIndexedTree() {        IndexNode cur = root;        while (cur != null) {            while (cur.left != null && !cur.isLeftIndexed) {                System.out.println(cur);                cur = cur.left;            }            System.out.println(cur);            if (cur.isLeftIndexed) cur = cur.right;            while (cur != null && cur.isRightIndexed) {                System.out.println(cur);                cur = cur.right;            }        }    }    /** 遍历经过后序线索化后的二叉树 */    public void showPostOrderIndexedTree() {        IndexNode cur = root;        while (cur != null) {            while (!cur.isLeftIndexed) cur = cur.left;            while (cur != null && cur.isRightIndexed) {                System.out.println(cur);                pre = cur;                cur = cur.right;            }            if (cur == root) {                System.out.println(cur);                return;            }            while (cur != null && cur.right == pre) {                System.out.println(cur);                pre = cur;                cur = cur.parent;            }            if (cur != null && !cur.isRightIndexed) {                cur = cur.right;            }        }    }        // 中序线索化的过程，node是当前需要线索化的节点    private void infixOrderIndexTree(IndexNode node) {        // 1.递归向左线索化        if (node.left != null && !node.isLeftIndexed) infixOrderIndexTree(node.left);        // 2.对当前节点进行线索化        indexCurrentNode(node);        // 3.递归向右线索化        if (node.right != null && !node.isRightIndexed) infixOrderIndexTree(node.right);    }    // 前序线索化的过程    private void preOrderIndexTree(IndexNode node) {        // 1.对当前节点进行线索化        indexCurrentNode(node);        // 2.递归向左线索化        if (node.left != null && !node.isLeftIndexed) preOrderIndexTree(node.left);        // 3.递归向右线索化        if (node.right != null && !node.isRightIndexed) preOrderIndexTree(node.right);    }    // 后序线索化的过程    private void postOrderIndexTree(IndexNode node) {        // 1. 递归向左线索化        if (node.left != null && !node.isLeftIndexed) postOrderIndexTree(node.left);        // 2. 递归向右线索化        if (node.right != null && !node.isRightIndexed) postOrderIndexTree(node.right);        // 3. 对当前节点线索化        indexCurrentNode(node);    }    // 对当前节点进行线索化    private void indexCurrentNode(IndexNode current) {        if (current.left == null) {            // 让当前节点的左指针指向前驱（左指针为空，才可以进行，不空则说明已经指向左子树）            current.left = pre;            current.isLeftIndexed = true; // type 置为1,标记为指向的是前驱节点        }        if (pre != null && pre.right == null) {            // 让前驱的右指针，指向当前节点(前驱的右指针为空，才可进行，不空则说明已经指向右子树)            pre.right = current;            pre.isRightIndexed = true; // type 置为1,标记为指向的是后继节点        }        // 处理完成后，要更新pre 为 当前节点，（让当前节点称为下一个节点的前驱）        pre = current;    }}

/** * 测试 *     1. 二叉树的中序遍历，先序遍历，后序遍历 *     2. 二叉树的中序索引化，先序索引化，后序索引化 *     3. 二叉树的中序索引化遍历，先序索引化遍历，后序索引化遍历 */public class IndexBinaryTreeDemo {    private static IndexBinaryTree tree;    private static IndexNode node5;    public static void main(String[] args) {        testInfix();        System.out.println("************************");        testPrefix();        System.out.println("************************");        testPost();    }    private static void testPost() {        IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();        app.resetTree(); // 重置测试数据        System.out.println("后序遍历结果:");        tree.postOrder(); // 打印先序遍历结果        tree.postOrderIndexTree(); // 对二叉树进行先序索引化        // 测试节点[10, King]的前驱和后继        System.out.println("\n[10,King]的前驱和后继: ");        System.out.println("前驱: " + node5.left); // [8,Mary]        System.out.println("后继: " + node5.right);// [6,Smith]        // 测试经过中序线索华后的遍历结果        System.out.println("\n经过后序线索化后的遍历结果:");        tree.showPostOrderIndexedTree();    }    private static void testPrefix() {        IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();        app.resetTree(); // 重置测试数据        System.out.println("先序遍历结果:");        tree.preOrder(); // 打印先序遍历结果        tree.preOrderIndexTree(); // 对二叉树进行先序索引化        // 测试节点[10, King]的前驱和后继        System.out.println("\n[10,King]的前驱和后继: ");        System.out.println("前驱: " + node5.left); // [8,Mary]        System.out.println("后继: " + node5.right);// [6,Smith]        // 测试经过中序线索华后的遍历结果        System.out.println("\n经过前序线索化后的遍历结果:");        tree.showPreOrderIndexedTree();    }    private static void testInfix() {        IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();        app.resetTree();   //重置测试数据        System.out.println("中序遍历结果");        tree.infixOrder(); //打印中序遍历结果        tree.infixOrderIndexTree(); // 对二叉树进行中序遍历索引化        // 测试节点[10, King]的前驱和后继        System.out.println("\n[10,King]的前驱和后继: ");        System.out.println("前驱: " + node5.left); // [3, Jack]        System.out.println("后继: " + node5.right);// [1, Tom]        // 测试经过中序线索化后的遍历结果        System.out.println("\n经过中序线索化后的遍历结果:");        tree.showInfixOrderIndexedTree();    }    private void resetTree() {        IndexNode root = new IndexNode(1, "Tom");        IndexNode node2 = new IndexNode(3, "Jack");        IndexNode node3 = new IndexNode(6, "Smith");        IndexNode node4 = new IndexNode(8, "Mary");        IndexNode node5 = new IndexNode(10, "King");        IndexNode node6 = new IndexNode(14, "Dim");        IndexBinaryTreeDemo.node5 = node5; // 供测试用        // 手动创建二叉树, parent指针用来辅助后序线索化        root.left = node2; node2.parent = root;        root.right = node3; node3.parent = root;        node2.left = node4; node4.parent = node2;        node2.right = node5; node5.parent = node2;        node3.left = node6; node6.parent = node3;        tree = new IndexBinaryTree();        tree.root = root;    }}