Java implements threaded binary tree and traverses (pre-order, mid-order, post-order)

Posted Jun 28, 20206 min read

/**
* Threaded binary tree nodes
*/
public class IndexNode {
public int id;
public String name;
public IndexNode left;
public IndexNode right;
public IndexNode parent = null; //need to be used when post-order clues
public boolean isLeftIndexed; //0 means the left pointer points to the left subtree, 1 means the left pointer points to the predecessor node
public boolean isRightIndexed; //0 means the right pointer points to the right subtree, 1 means the right pointer points to the successor node

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

    @Override
    public String toString() {
        return "[" + id + "," + name + "]";
    }

    //preorder traversal
    public void preOrder() {
        System.out.println(this);
        if(left != null) left.preOrder();
        if(right != null) right.preOrder();
    }
    //In-order traversal
    public void infixOrder() {
        if(left != null) left.infixOrder();
        System.out.println(this);
        if(right != null) right.infixOrder();
    }
    //Post-order traversal
    public void postOrder() {
        if(left != null) left.postOrder();
        if(right != null) right.postOrder();
        System.out.println(this);
    }
}

/**
 * Binary tree with clue function
 */
public class IndexBinaryTree {
    IndexNode root;
    //In order to achieve clueing, a pre pointer is needed, pointing to the precursor of the current node
    //When clueing, pre always points to the previous node
    IndexNode pre = null;

    /** Preorder traversal */
    public void preOrder() {
        if(root == null) {
            System.out.println("Empty tree, unable to traverse");
            return;
        }
        root.preOrder();
    }

    /** In-order traversal */
    public void infixOrder() {
        if(root == null) {
            System.out.println("Empty tree, unable to traverse");
            return;
        }
        root.infixOrder();
    }

    /** Post-order traversal */
    public void postOrder() {
        if(root == null) {
            System.out.println("Empty tree, unable to traverse");
            return;
        }
        root.postOrder();
    }

    /** In-order clueing of binary trees */
    public void infixOrderIndexTree() {
        if(root == null) return;
        infixOrderIndexTree(root);
    }

    /** Pre-leading the binary tree */
    public void preOrderIndexTree() {
        if(root == null) return;
        preOrderIndexTree(root);
    }

    /** Post-order clueing of binary tree */
    public void postOrderIndexTree() {
        if(root == null) return;
        postOrderIndexTree(root);
    }

    /** Traverse the binary tree after mid-order clue */
    public void showInfixOrderIndexedTree() {
        IndexNode cur = root;
        while(cur != null) {
            //cur keeps looking down, find the node with leftType = 1
            while(!cur.isLeftIndexed) cur = cur.left;
            //print cur
            System.out.println(cur);
            //If the right pointer of cur points to a successor node, it will be updated all the time, and then output
            while(cur.isRightIndexed) {
                cur = cur.right;
                System.out.println(cur);
            }
            //Update cur node
            cur = cur.right;
        }
    }

    /** Traverse the binary tree after preorder clue */
    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;
            }
        }
    }
    /** Traverse the binary tree after the post-order clue */
    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;
            }
        }
    }

    //The process of in-order clueing, node is the node that needs clueing
    private void infixOrderIndexTree(IndexNode node) {
        //1. Recursively clue left
        if(node.left != null && !node.isLeftIndexed) infixOrderIndexTree(node.left);
        //2. Clue the current node
        indexCurrentNode(node);
        //3. Recursively clue right
        if(node.right != null && !node.isRightIndexed) infixOrderIndexTree(node.right);
    }

    //The pre-leading process
    private void preOrderIndexTree(IndexNode node) {
        //1. Clue the current node
        indexCurrentNode(node);
        //2. Recursively clue left
        if(node.left != null && !node.isLeftIndexed) preOrderIndexTree(node.left);
        //3. Recursively clue right
        if(node.right != null && !node.isRightIndexed) preOrderIndexTree(node.right);
    }

    //The process of post-order clue
    private void postOrderIndexTree(IndexNode node) {
        //1. Recursively clue left
        if(node.left != null && !node.isLeftIndexed) postOrderIndexTree(node.left);
        //2. Recursively clue right
        if(node.right != null && !node.isRightIndexed) postOrderIndexTree(node.right);
        //3. Clue the current node
        indexCurrentNode(node);
    }

    //Clue the current node
    private void indexCurrentNode(IndexNode current) {
        if(current.left == null) {
            //Let the left pointer of the current node point to the predecessor(the left pointer is empty, it can be done, if it is not empty, it means that it has already pointed to the left subtree)
            current.left = pre;
            current.isLeftIndexed = true; //type is set to 1, and it is marked to point to the predecessor node
        }
        if(pre != null && pre.right == null) {
            //Let the right pointer of the predecessor point to the current node(the right pointer of the predecessor is empty, it can be carried out, if it is not empty, it means that it has already pointed to the right subtree)
            pre.right = current;
            pre.isRightIndexed = true; //type is set to 1, and it is marked as a successor node
        }
        //After processing is completed, pre should be updated to the current node,(let the current node be the precursor of the next node)
        pre = current;
    }
}


/**
 * Test
 * 1. Mid-order traversal of binary tree, first-order traversal, second-order traversal
 * 2. Mid-order indexing of binary tree, indexing first, indexing later
 * 3. Mid-order index traversal of binary tree, first-order index traversal, then-order index traversal
 */
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(); //Reset test data
        System.out.println("Post-order traversal result:");
        tree.postOrder(); //print the result of traversal
        tree.postOrderIndexTree(); //Pre-index the binary tree

        //Predecessor and successor of test node [10, King]
        System.out.println("\n[10,King]'s predecessor and successor:");
        System.out.println("Precursor:"+ node5.left); //[8,Mary]
        System.out.println("Successor:"+ node5.right); //[6,Smith]
        //Test traversal results after mid-order clues
        System.out.println("\nThe traversal result after post-order clue:");
        tree.showPostOrderIndexedTree();
    }

    private static void testPrefix() {
        IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();
        app.resetTree(); //Reset test data
        System.out.println("Sequential traversal result:");
        tree.preOrder(); //print the result of traversal
        tree.preOrderIndexTree(); //Pre-index the binary tree

        //Predecessor and successor of test node [10, King]
        System.out.println("\n[10,King]'s predecessor and successor:");
        System.out.println("Precursor:"+ node5.left); //[8,Mary]
        System.out.println("Successor:"+ node5.right);//[6,Smith]
        //Test traversal results after mid-order clues
        System.out.println("\nThe traversal result after pre-order clue:");
        tree.showPreOrderIndexedTree();
    }

    private static void testInfix() {
        IndexBinaryTreeDemo app = new IndexBinaryTreeDemo();
        app.resetTree(); //Reset test data
        System.out.println("Sequence traversal result");
        tree.infixOrder(); //print mid-order traversal result
        tree.infixOrderIndexTree(); //In-order traversal indexing of binary tree
        //Predecessor and successor of test node [10, King]
        System.out.println("\n[10,King]'s predecessor and successor:");
        System.out.println("Predecessor:"+ node5.left); //[3, Jack]
        System.out.println("Successor:"+ node5.right);//[1, Tom]
        //Test traversal results after mid-order clueing
        System.out.println("\nThe traversal result after mid-sequence clueing:");
        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; //for testing
        //Manually create a binary tree, the parent pointer is used to assist in post-order clueing
        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;
    }
}