java - 线程二叉树

Question

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

我知道通过将每个空左子节点设置为中序遍历中节点的前任节点并将每个空右子节点设置为中序遍历中节点的后继节点来获得二叉树的线程二叉树。

但是我的问题从构造函数开始 // 当您获得根时，将二叉树线程化 public ThreadedNode(BinaryNode root)

我知道它接收一个 binaryNode 并且我必须使它成为一个线程树，但我如何创建新的线程树？

Answer 1

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

因此，您的构造函数可能看起来像：

public class ThreadedNode {

    private BinaryNode head;

    public ThreadedNode(BinaryNode root) {

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

    }
}

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