(Java implementation) Binary tree --- threading

Overview

  • Ordinary binary tree, with left and right child nodes, as shown below

    • For a leaf node, its left and right child nodes are empty, and some non-leaf nodes may have only one child node, and each node will occupy a space, which will waste the created space.
  • Threaded binary tree, exploiting these spaces

Threaded Binary Tree

  • Threaded Binary Tree

    • If the node's left child is empty, point to the node's predecessor
    • If the node's right child is empty, point to the node's successor
  • Precursor and Successor:

    • predecessor: the predecessor of a node
    • successor: a node's successor
  • A binary linked list of n nodes contains n+1 empty spaces
  • According to the different traversal order (that is, the clues are different), the clue binary tree can be divided into: pre-order clue binary tree, in-order clue binary tree and post-order clue binary tree
  • For example, thread the ordinary binary tree in the above figure, as shown in the following figure:According to the result of preorder traversal, the predecessor node of 16 is 20, so the left child node of 16 points to 20, the successor node of 16 is 42, so the right child node of 16 points to 42, and so on

create

  • The basic idea:

    • The in-order threading method is adopted, first threading the left subtree, then threading the current node, and finally threading the right subtree
    • 1) Threaded left subtree
    • 2) Process the predecessor node of the current node: determine whether the left child node of the current node is empty, if it is empty, point the left child node of the current node to the previous node
    • 3) Process the successor node of the current node: determine whether the predecessor node of the current node is empty, if the previous node is not empty and the right child node of the previous node is empty, then point the right child node of the previous node to the current node
    • 4) Let the predecessor node point to the current node
    • 5) Threaded right subtree
  • Note: Each recursion can only judge the left child node of the current node and the right child node of the predecessor node, because there is no way to know the next node of the current node, only the previous node

traverse

  • The basic idea:

    • First find the clued node from the left subtree in a loop, and then from the found node, loop to find her clued right child node
    • Finally, let the current node point to the successor node
  • Note: Since we are an inorder threaded binary tree, the first node must be a leaf node of a left subtree

code show as below

data structure:

package Tree;
public class TreeNode {
     private Integer val;//serial number
     private TreeNode left;//left child
     private TreeNode right;//right child
     //leftType: 0 means the left subtree pointed to, if 1 means pointing to the predecessor node
     private int leftType;
     //rightType: 0 means it points to the right subtree, if 1 means it points to the successor node
     private int rightType;
     public TreeNode(int val){
            this.val = val;
     }
        public Integer getVal() {
            return val;
     }
        public void setVal(Integer val) {
            this.val = val;
     }
        public TreeNode getLeft() {
            return left;
     }
        public void setLeft(TreeNode left) {
            this.left = left;
     }
        public TreeNode getRight() {
            return right;
     }
        public void setRight(TreeNode right) {
            this.right = right;
     }
        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;
     }
        @Override
     public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
     }
}

Specific algorithm:

package Tree;
public class ThreadedBinaryTree {
        //The previous node of the current node
     private static TreeNode pre = null;
     //root node
     private static TreeNode root;
     private static final int IS_LEFT_CHILD = 0; //0 means that the left child of the current node points to the left subtree
     private static final int IS_RIGHT_CHILD = 0; //0 means that the right child of the current node points to the right subtree
     private static final int IS_PRE_NODE = 1; //1 means that the left child node of the current node points to the predecessor node
     private static final int IS_AFTER_NODE = 1; //1 means that the right child of the current node points to the successor node
     public static void setRoot(TreeNode root) {
            ThreadedBinaryTree.root = root;
     }
        //Threaded traversal of binary tree
     public static void threadedList(){
            //set current node
     TreeNode node = root;
     if (node == null) return;
     while (node != null){
                //Find nodes with leftType == 1
     while (node.getLeftType() == IS_LEFT_CHILD){
                    node = node.getLeft();
     }
                //print current node
     System.out.println(node.getVal());
     //If the right child node of the current node points to the successor node, it will be output consistently
     while (node.getRightType() == IS_AFTER_NODE){
                    node = node.getRight();
     System.out.println(node.getVal());
     }
                //replace this traversed node
     node = node.getRight();
     }
        }
        //A method for inorder threading of binary tree
     public static void threadedNodes(TreeNode node){
            if (node == null) return;
     //1. Thread the left subtree first
     threadedNodes(node.getLeft());
     //2. Thread the current node
     //2.1 Process the predecessor node of the current node
     if (node.getLeft() == null){
                //Modify the left child node of the current node to point to the predecessor node
     node.setLeft(pre);
     node.setLeftType(IS_PRE_NODE);
     }
            //2.2 Process the successor nodes of the current node
     if (pre != null && pre.getRight() == null){
                //Make the right child of the predecessor node point to the current node
     pre.setRight(node);
     pre.setRightType(IS_AFTER_NODE);
     }
            //After each node is processed, let the predecessor node of the next node point to the current node
     pre = node;
     //3. Threaded right subtree
     threadedNodes(node.getRight());
     }
        public static void main(String[] args) {
            TreeNode node1 = new TreeNode(1);
     TreeNode node2 = new TreeNode(3);
     TreeNode node3 = new TreeNode(6);
     TreeNode node4 = new TreeNode(8);
     TreeNode node5 = new TreeNode(10);
     TreeNode node6 = new TreeNode(14);
     node1.setLeft(node2);
     node1.setRight(node3);
     node2.setLeft(node4);
     node2.setRight(node5);
     node3.setLeft(node6);
     setRoot(node1);
     threadedNodes(node1);
    //        TreeNode right = node3.getRight();
    //        TreeNode preNode = node5.getLeft();
    //        TreeNode afterNode = node5.getRight();
    //        System.out.println(right);
    //        System.out.println(preNode);
    //        System.out.println(afterNode);
    //
     threadedList();
     }
}

Because the algorithm may not be clear if the number of words is used, it is recommended to go through the process by combining the code and pictures

Tags: Java Binary tree

Posted by zackcez on Sun, 15 May 2022 12:04:10 +0300