我是否正确设置了这个BST?如果是这样，我如何在其他方法中使用它? [英] Did I set up this BST correctly? If so, how can I use it in other methods?

问题描述

我的目标是使用预定序遍历从给定的字符串创建二进制搜索树(BST).最终，我将使用BST使用霍夫曼编码/解码来解码二进制消息.我的问题/问题与树本身的设置有关. (设置完成后，我已经弄清楚了如何解码消息.)

My goal is to create a Binary Search Tree (BST) from a given string, using a preorder traversal. Eventually, I will use the BST to decode a binary message using Huffman encoding/decoding. My question/issue pertains to setting up the tree itself. (I already figured out how to decode the message after the set up.)

这是我要完成的工作的一个示例. (注意:这是在给我们的作业中提供的.

Here is an example of what I'm trying to accomplish. (NOTE: This was provided in the assignment we were given.

字符串:^ a ^^！^ dc ^ rb

String: ^a^^!^dc^rb

这是树的样子:

我的问题是设置树并在其他方法中使用它.我希望能够以其他方法使用树的根，但是每次使用它时，它将给我一个空值.

My issue comes with setting up the tree and using it in the other methods I have. I want to be able to use the root of the tree in the other methods, but every time I would use it, it would give me a null value.

这是我的代码:

公共类MsgTree {

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的任何方法外，尝试使用根值或BST都会给我一个空值.我尝试使用"newTree.root"或"MsgTree.root"但这不起作用.

Attempting to use the root value or the BST in any method besides where it was created will give me a null value. I've tried using "newTree.root" or "MsgTree.root" but that doesn't work.

在此方面的任何帮助，我将不胜感激.谢谢.

I would appreciate any help with this. Thank you.

推荐答案

您绝不会将null以外的任何东西分配给left和right，因此您实际上并没有在构建树.

You never assign anything other than null to left and right, so you aren't actually building a tree.

看起来输入字符串具有递归定义:

It looks like the input string has a recursive definition:

• 如果字符为'^'，则节点有效载荷为空(或'^')，left是我们从解析下一个字符开始的字符串中获得的节点，而right是我们得到的节点通过解析从我们为left阅读的内容之后的下一个字符开始的字符串获得.
• 否则，节点有效载荷是字符，而left和right是null.

• If the character is '^' then the node payload is empty (or '^'), left is the node that we get from parsing the string starting at the next character, and right is the node we get by parsing the string starting at the next character after whatever we read for left.
• Otherwise, the node payload is the character, and left and right are null.

您对staticCharIdx有个正确的想法.这就是您跟踪下一个字符"的方式.但是，您不想遍历MsgTree构造函数中的整个字符串.如果staticCharIdx将是静态的，则也可以将encodingString设置为静态，并使用如下所示的静态树构建方法:

You have the right idea with staticCharIdx. This is how you keep track of the "next character." But you don't want to loop through the whole string in the MsgTree constructor. And if staticCharIdx is going to be static, might as well make encodingString static too, and make a static tree-building method something like this:

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

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

The function buildNextMsgTree implements the two cases above, in the first case recursively calling itself to create the left and right nodes.

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构造函数以接受有效载荷.

You'll have to adjust the MsgTree constructor to accept the payload.

这篇关于我是否正确设置了这个BST?如果是这样，我如何在其他方法中使用它?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！