java - 线程二叉树

Question

大家好，我应该编写 ThreadedNode() 类，但我遇到了一些问题。

据我所知，二叉树的线程二叉树是通过将每个空左子节点设置为中序遍历中节点的前驱节点和每个空右子节点来获得的到中序遍历中该节点的后继节点。

但是我的问题是从构造函数开始的//当给定根时对二叉树进行线程化 public ThreadedNode(BinaryNode根)

我知道它接收到一个binaryNode，并且我必须将其设为线程树，但是我如何创建新的线程树？

Answer 1

创建线程二叉树的常见方法是使用假头。这使得单节点树更容易理解，构造函数也更简单。

因此您的构造函数可能如下所示:

public class ThreadedNode {

    private BinaryNode head;

    public ThreadedNode(BinaryNode root) {

        head = new BinaryNode();
        root.makeThreaded();
        root.setRight(head);
        head.setRight(root);

    }
}

请记住，稍后您需要在插入、删除等操作中考虑这个假头。