How to implement threaded binary tree in Java data structure?

1. Introduction to clued binary tree

Construct the sequence {1, 3, 6, 8, 10, 14} into a binary tree.

Problem Analysis:

1. When we perform in-order traversal on the above binary tree, the array is {8, 3, 10, 1, 6, 14}

2. But 6, The left and right pointers of these nodes 8, 10, 14 are not fully utilized.

3. If we want to make full use of the left and right pointers of each node, so that each node can point to its own previous and next nodes, What to do?

4. Solution - Clue Binary Tree

Concept: When using a binary linked list as the storage structure of the binary tree, it is easy to find the left and right children of a node; but In general, it is impossible to directly find the predecessor and successor nodes of the node in a certain traversal sequence. Therefore, threading is used, and the null pointer field of the binary tree structure linked list is used for threading.

2. Basic characteristics of threaded binary trees

A binary linked list of n nodes contains n 1 [formula 2n-(n-1)=n 1] null pointer fields. Use the null pointer field in the binary linked list to store pointers to the predecessor and successor nodes of the node in a certain traversal order (such additional pointers are called "clues")

This kind of addition The binary linked list with a clue is called a clue linked list, and the corresponding binary tree is called a threaded binary tree (Threaded BinaryTree). According to the different nature of clues, clue binary trees can be divided into three types: preorder clue binary tree, midorder clue binary tree and postorder clue binary tree

3. Application cases of clueed binary trees

Midorder clue Transform the binary tree and traverse

Application case description: Convert the following binary tree into an in-order clue binary tree. The number sequence for in-order traversal is {8, 3, 10, 1, 14, 6}

Idea analysis

The result of in-order traversal: {8 , 3, 10, 1, 14, 6}

#Then the left and right pointers of the binary tree after threading are as shown in the figure above↑

Explanation: When threading After the binary tree, the attributes left and right of the Node node have the following situations:

• left points to the left subtree, or it may be the predecessor node pointed to. For example, ① The node left points to the left subtree, and the left of the ⑩ node points to the predecessor node.

• right points to the right subtree, or it may point to the successor node. For example, the ① node right points to the right subtree. tree, and the right of the ⑩ node points to the successor node.

So we need to change the node structure of the original binary tree

package com.studySelf.tree.threadedBinaryTree;

/**
 * @author wang
 * @version 1.0
 * @packageName com.studySelf.tree.tree01
 * @className Node
 * @date 2022/4/19 20:15
 * @Description Node结点
 */
public class Node {
    //唯一编号
    private int num;
    //结点的值
    private String name;
    //左结点
    private Node left;
    //右节点
    private Node right;

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;


    //构造方法

    public Node(int num, String name) {
        this.num = num;
        this.name = name;
    }

    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 int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

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

    public Node getLeft() {
        return left;
    }

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

    public Node getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "Node{" +
                "num=" + num +
                ", name='" + name +
                '}';
    }

    /**
     * 前序遍历
     */
    public void preSelect() {
        //首先输出根结点
        System.out.println(this);
        //其次判断是否有左结点
        if (this.left != null) {
            //没有左结点，就递归调用本方法输出该结点。
            this.left.preSelect();
        }
        if (this.right != null) {
            this.right.preSelect();
        }
    }

    /**
     * 中序遍历
     */
    public void infixSelect() {
        //首先判断左结点
        if (this.left != null) {
            //如果左结点不为空，递归向左子树调用
            this.left.infixSelect();
        }
        //当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
        System.out.println(this);
        if (this.right != null) {
            //右节点同样如此，递归调用。直到没有结点为止。
            this.right.infixSelect();
        }
    }

    /**
     * 设二叉树有三个结点，根结点，左结点，右节点。
     * 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
     * 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
     * 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
     * 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
     * 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
     * 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
     */

    public void afterSelect() {
        if (this.left != null) {
            this.left.afterSelect();
        }

        if (this.right != null) {
            this.right.afterSelect();
        }
        System.out.println(this);
    }

    /**
     * @param num
     * @Date 2022/4/21 17:51
     * @Param
     * @Return Node
     * @MetodName preSearchByNum
     * @Author wang
     * @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右
     */
    public Node preSearchByNum(int num) {
        //首先判断传进来的num与该结点的num是否相等
        //如果相等，那该结点就是我们要找的结点。
        if (this.num == num) {
            return this;
        }

        //如果不相等，该结点就不是我们要找的结点
        //那么我们就遍历该结点的左子节点，和右子结点
        //定义一个结点用于接收最后的返回结果
        Node resultNode = null;
        //如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
        if (this.left != null) {
            resultNode = this.left.preSearchByNum(num);
        }

        //如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
        if (resultNode != null) {
            return resultNode;
        }

        //如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
        if (this.right != null) {
            resultNode = this.right.preSearchByNum(num);
        }
        //最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/21 17:58
     * @Param
     * @Return Node
     * @MetodName infixSearchByNum
     * @Author wang
     * @Description 中序遍历查找，左，根，右进行查询即可。
     */
    public Node infixSearchByNum(int num) {
        //首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
        Node resultNode = null;
        if (this.left != null) {
            resultNode = this.left.infixSearchByNum(num);
        }

        //如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点
        if (this.num == num) {
            return this;
        }

        //判断右子结点，
        if (this.right != null) {
            resultNode = this.right.infixSearchByNum(num);
        }
        //最后返回我们的结果即可。
        return resultNode;
    }


    /**
     * @param num
     * @Date 2022/4/21 19:15
     * @Param
     * @Return Node
     * @MetodName afterSearchNum
     * @Author wang
     * @Description 后续遍历结点进行查找结点。左，右，根
     */
    public Node afterSearchNum(int num) {
        Node resultNode = null;
        //首先遍历左结点
        if (this.left != null) {
            resultNode = this.left.afterSearchNum(num);
        }

        //判断左结点是否找到哦啊
        if (resultNode != null) {
            return resultNode;
        }

        //判断右节点是否为空
        if (this.right != null) {
            resultNode = this.right.afterSearchNum(num);
        }

        //判断右节点是否找到
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点是否为我们找的结点
        if (this.num == num) {
            return this;
        }
        //最后返回
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/25 19:30
     * @Param
     * @Return void
     * @MetodName delNodeByNum
     * @Author wang
     * @Description 根据结点的编号删除结点
     */
    public void delNodeByNum(int num) {
        //首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
        if (this.left != null && this.left.num == num) {
            //如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
            this.left = null;
            return;
        }

        //如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
        //那么就对右节点进行判断
        if (this.right != null && this.right.num == num) {
            this.right = null;
            return;
        }

        //如果左右结点均没有找到目标结点
        //那么就对左子树进行递归删除操作
        if (this.left != null) {
            this.left.delNodeByNum(num);
        }

        //同理，如果左子树没有目标结点，向右子树进行递归删除操作
        if (this.right != null) {
            this.right.delNodeByNum(num);
        }

    }
}

You can see that we have this extra Two attributes:

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;

In-order threaded binary tree

  /**中序线索化二叉树*/
    /**
     * @param node 该结点为根结点，从根节点开始线索化二叉树，中序
     */
    public void infixThreadNodes(Node node) {
        /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/
        if (node == null) {
            return;
        }

        /**接着对左子树进行线索化*/
        infixThreadNodes(node.getLeft());

        /**对当前结点进行线索化*/
        /**首先判断当前结点的左子结点是否为空*/
        if (node.getLeft() == null) {
            //如果左子结点为空，说明就找到了我们需要线索化的结点
            //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点，
            //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空
            node.setLeft(pre);
            //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点
            node.setLeftType(1);
        }

        /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/
        if (pre != null && pre.getRight() == null) {
            //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点，
            // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继，
            //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。
            //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化
            pre.setRight(node);
            pre.setRightType(1);
        }

        //当前两步走完之后，就可以将pre结点赋值为当前结点，
        // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束
        //这步十分重要，这一步不写，整个线索化就连接不上
        pre = node;

        /**对右子树进行线索化*/
        infixThreadNodes(node.getRight());
    }

In-order threaded binary tree idea

1. Because the order of the binary tree traversed in in-order is left The root is right. Therefore, first clue the left subtree and recursively clue it;

2. When the recursion reaches the leftmost node of the left subtree, its left node The point must be empty, then assign its left node to pre (the pre node is assigned to the current node in the last step of threading, so that the recursion can continue). Note that the type of the left node must be changed to 1 means that it is the predecessor node. The predecessor node has lost its clue.

3. The processing of successor nodes is to determine the predecessor node. If the current node is not empty, and the right node of the predecessor node is empty, then set the predecessor node. The right node is the current node, that is, the right node of the previous node that has not been set. The type must also be set to successor

4. . Finally, assign a value to the pre node and assign it to the current node. point, because in the next recursion, the current node becomes the previous node, which is the pre

5. . Finally, the right child node of the binary tree is threaded.

Traversal of an in-order threaded binary tree

1. When traversing an in-order threaded binary tree, it should first be clear that its traversal order must be the same as the original traversal The traversal is successful if the results of the in-order binary tree traversal are the same.

2. Then the first step should be to determine that the root node is not empty, which is the loop end condition

3. Then it loops to find the left child node of the current node whose type is 0, that is, the node that has not been threaded. As long as it is 0, the node will always assign values ​​to the left child node. . Until we find the first threaded node and output it, it will be our first threaded node and the first left child node of in-order traversal.

4. After output, determine whether its right child node is threaded. If it is threaded, then the current node node is assigned as its own right child node, and Output, if the type of the right child node of the node after it is 1 again, then continue to go back and assign a value, indicating that it has the successor

5. until the type of the right child node is 0. After exiting the loop, you should also assign values ​​to the right and continue to traverse backwards

Code Demonstration

    /**遍历中序线索化二叉树*/
    public void infixThreadNodesSelect() {
        /**第一个结点为根结点*/
        Node node = root;
        while(node != null) {
            /**当结点不为空，就一直遍历*/
            /**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点,
             * 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个
             * 左子结点类型为1的结点。*/
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            /**当左子结点的类型为1,输出左子结点*/
            System.out.println(node);

            /**当右子结点类型为1，当前结点输出完毕后
             * 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动
             * 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点，
             * 因此要在循环结束以后向后移动。*/
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            /**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/
            node = node.getRight();
        }

4. Preorder threaded binary tree, traversal

Threaded Binary Tree

 /**
     * 前序线索化二叉树
     */
    public void preThreadNodes(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() != 1) {
            preThreadNodes(node.getLeft());
        }


        /**对右子结点进行递归线索化*/
        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

 遍历线索化二叉树

/**
     * 前序遍历线索二叉树*/
    public void preThreadNodeSelect() {
        Node node = root;
        while(node !=null) {
            while(node.getLeftType() == 0) {
                /**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
                 * 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
                System.out.println(node);
                /**再最左子结点进行遍历*/
                node = node.getLeft();
            }
            /**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
             * 之后结点向右移动继续遍历*/
            System.out.println(node);
            node = node.getRight();
        }
  }

图解

5.后序线索化二叉树

后续线索化二叉树

/**
 * 后序线索化二叉树的方法
 */
public void postThreadedBinaryTree(Node node) {
    /**首先判断结店不能为空*/
    if (node == null) {
        return;
    }

    /**先后续线索化左子结点*/
    postThreadedBinaryTree(node.getLeft());
    /**在后续线索化右子结点*/
    postThreadedBinaryTree(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;
}

The above is the detailed content of How to implement threaded binary tree in Java data structure?. For more information, please follow other related articles on the PHP Chinese website!