如何旋转二叉树递归给定一个空stopper

Question

我正在从文件中读取字符串，并且每当节点的子节点为空时都记录了'~'。然后我把这些字符串加到二叉树中。但是我的代码只是简单地将所有字符串(包括'~')添加到左树节点中。

我如何让算法停止添加左节点时，一个'~'到达并插入一个右节点(除非当然下一个字符串也是一个'~')?

下面是我的代码:

// Reads the elements in the tree in pre-order
public void fromFile()
{
   BufferedReader in;
   String s = null;
   try {
        in = new BufferedReader(new FileReader("animal_game.txt"));
        StringBuffer stringBuffer = new StringBuffer();
        while( (s=in.readLine()) != null )
        {
            stringBuffer.append(s);
            stringBuffer.append("n");
        }
        fromFile(stringBuffer.toString());

        in.close();
   } 
   catch (IOException ex) 
   {
           Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
   } 
}
public void fromFile(String s)
{
    if (root == null)
    {
        root = new Node<>((T)s);
        size++;
    } 
    else 
    {
        fromFile(root, s);   
    }
}
// helper function
private void fromFile( Node<T> node, String s) 
{
        // if null tree node reached, 
        if(s==NULL_TREE_NODE)
        {
            fromFile(node, s);
        }
        // insert left node
        if (node.no == null) 
        {
            node.no = new Node<>((T)s);
        } 
        else 
        {
            fromFile(node.no, s);
        }
        // insert right node
        if (node.yes == null) 
        {
            node.yes = new Node<>((T)s);
        } 
        else{
            fromFile(node.yes, s);
        }
}

这是我保存树到一个文件的代码:

// Writes the elements in the tree in pre-order
public void toFile()
{
    // Writes in preorder starting with the root node
    if (root != null) 
    {
        BufferedWriter out;
        try {
            out = new BufferedWriter(new FileWriter("animal_game.txt"));
            toFile(out, root);
            out.close();
        } 
        catch (IOException ex) 
        {
            Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
        } 
    }
}
// Helper function
private void toFile(BufferedWriter out, Node<T> node) 
{
    try {
        if (node == null) {
        out.write(NULL_TREE_NODE); // null
        out.newLine();
        return;
    }
    //assert !node.data.equals(NULL_TREE_NODE); // Reserver for us..
    out.write((String)node.data); // these nodes hold Strings
    out.newLine();
    toFile(out, node.no);
    toFile(out, node.yes);
    } 
    catch (IOException ex) 
    {
        Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
    }
}

这是我的文件

---

它是哺乳动物吗?

是爬行动物吗?

它是一条鱼吗?

鹈鹕

~

~

鲨鱼

~

~

它灭绝了吗?

乌龟

~

~

迅猛龙

~

~

它有毛吗?

大象

~

~

猫

Answer 1

您应该更改fromFile()以匹配toFile():不接受代表整个文件的Node和String，而是使用BufferedReader，允许它轻松地读取单个行。此外，将helper构建函数更改为返回Node，以便在~ Node的情况下返回null。然后，可以递归地构建整个树，当到达~节点时返回null:

 private Node<T> fromFile(BufferedReader s) throws IOException
    {
            String line = s.readLine();
            if(line == null) throw new IllegalArgumentException("File does not specify complete tree");
            // if null tree node reached, 
            if(line.equals(NULL_TREE_NODE)) return null;
            Node<T> node = new Node<>();
            node.data = line;
            node.no = fromFile(s);
            node.yes = fromFile(s);
            return node;
    }

然后，稍微调整一下fromFile():

public void fromFile()
{
   try(BufferedReader in = new BufferedReader(new FileReader("animal_game.txt"))) 
   {
        root = fromFile(in);
   } 
   catch (IOException ex) 
   {
           Logger.getLogger(Tree.class.getName()).log(Level.SEVERE, null, ex);
   } 
}

我还修改了它，使用try-with-resources语句，以方便，并保证在异常时适当的资源释放。见http://docs.oracle.com/javase/tutorial/essential/exceptions/tryResourceClose.html