我是否正确设置了这个 BST？如果是这样，我如何在其他方法中使用它？

Question

我的目标是使用先序遍历从给定的字符串创建二叉搜索树 (BST)。最终，我将使用 BST 来使用 Huffman encoding/decoding 解码二进制消息。我的 question/issue 与设置树本身有关。（我已经想出了如何在设置后解码消息。）

这是我正在尝试完成的示例。（注意：这是在给我们的作业中提供的。

字符串：^a^^!^dc^rb

树应该是这样的：

我的问题在于设置树并在我拥有的其他方法中使用它。我希望能够在其他方法中使用树的根，但每次我使用它时，它都会给我一个空值。

这是我的代码：

public class MsgTree {

public char payloadChar;
public MsgTree left;
public MsgTree right;
public MsgTree root;
public String encodingString;
private static int staticCharIdx = 0; //Need static char idx in the tree string for recursive solution


public MsgTree(String encodingString) { //Constructor building the tree from a string
    this.encodingString = encodingString;
    for(staticCharIdx = 0; staticCharIdx < encodingString.length(); staticCharIdx++) { //The for loop loops through every character in the string one char at a time
        char charToTest = encodingString.charAt(staticCharIdx); //The program creates a charToTest variable to use for creating the new MsgTree node.
        MsgTree newNode = new MsgTree(charToTest); //A new MsgTree node is created for every new char in the encodingString. It does this by calling the second MsgTree constructor 
        if(staticCharIdx == 0) {
            root = newNode;
        }       
        preOrderTraversal(newNode); //The program then calls a private function to perform a preOrder traversal of the tree
    }
}

public MsgTree(char payloadChar) { //Constructor for a single node with null children
    left = null; //This method assigns two children (left and right) to the char node and sets them both to null
    right = null;
    this.payloadChar = payloadChar; //A payloadChar value is utilized to avoid naming conflicts and for use in other methods
} 

private void preOrderTraversal(MsgTree newNode) { //This method performs a preOrder traversal of the string and creates it into a BST
    if(newNode == null) { //If the newNode taken from the constructor is null, then nothing happens. This happens when it is past the last char of the string.
        return;
    }
    System.out.printf("%s", newNode.payloadChar); //Prints the char value of the NewNode
    preOrderTraversal(newNode.left); //Calls the same method, but focuses instead on the left child of the newNode
    preOrderTraversal(newNode.right); //Calls the same method, but focuses instead on the right child of the newNode
}

public static void printCodes(MsgTree root, String code) { //method to print characters and their binary codes
  //DOES THE PRINTING HERE
}

public void decode(MsgTree codes, String msg) { //Prints the decoded message to the console
  //DOES THE DECODING HERE
}

public static void main(String args[]) throws FileNotFoundException { //Main method putting the tree and message into two separate strings and implementing the above methods
        
        String treeString = "^a^^!^dc^rb";
        String messageString = "10100101010110110111100";
        
MsgTree newTree = new MsgTree(treeString); //A new tree is created using the new tree string derived from the arch file
        
        String code = "";
                
        System.out.println();
        System.out.println("character   code");
        System.out.println("-------------------------");
        newTree.printCodes(root, code); //WHY CANT I CALL IT HERE? IT GIVES ME A NULL VALUE
        
        newTree.decode(root, messageString); //I ALSO CAN'T USE IT HERE
    }

尝试在创建根值或 BST 以外的任何方法中使用它都会给我一个空值。我试过使用“newTree.root”或“MsgTree.root”，但这不起作用。

如有任何帮助，我将不胜感激。谢谢。

Answer 1

除了 null 之外，您从未将任何东西分配给 left 和 right，因此您实际上并没有构建树。

看起来输入字符串有一个递归定义：

如果字符是'^'则节点负载为空（或'^'），left是我们从下一个字符开始解析字符串得到的节点， right 是我们通过解析从 left.
否则节点载荷为字符，left和right为null。

您对 staticCharIdx 的想法是正确的。这就是您跟踪“下一个字符”的方式。但是您不想在 MsgTree 构造函数中遍历整个字符串。如果 staticCharIdx 将是静态的，不妨也将 encodingString 设为静态，并制作一个静态的树构建方法，如下所示：

public static MsgTree build(String encodingString) {
    MsgTree.encodingString = encodingString;
    staticCharIdx = 0;
    return buildNextMsgTree();
}

函数buildNextMsgTree实现了上述两种情况，第一种情况递归调用自身创建左右节点

private static MsgTree buildNextMessageTree() {
    char c = encodingString.charAt(staticCharIdx++);
    MsgTree tree = new MsgTree(c);
    if (c == '^') {
        tree.left = buildNextMessageTree();
        tree.right = buildNextMessageTree();
    }
    return tree;
}

您必须调整 MsgTree 构造函数以接受负载。

我是否正确设置了这个 BST？如果是这样，我如何在其他方法中使用它？

Did I set up this BST correctly? If so, how can I use it in other methods?

java

binary-search-tree