0

我正在尝试从 0 和 1 的输入创建二叉树。例如，如果输入是 11010010，那么输出的树将以 1 作为根。2 是 1 的左孩子， 4 是右孩子。2 将有一个正确的孩子，它将是 3。那是树的尽头。当树按前序遍历时，数字 1-n（n 是输入中 1 的数量）被分配给被访问的节点。1 表示根有孩子。例如，第一个 1 表示访问了根，并将 1 放置为根。第二个 1 表示根有一个左孩子，而 2 则放在那里。后面的 0 表示它没有左孩子。下一个 1 表示它确实有一个正确的孩子，并且 3 被放置在那里，等等。我对如何创建这棵树感到困惑。我了解在创建树后遍历树，但不了解如何通过遍历树来创建树。任何帮助，将不胜感激。

package tree;

import java.io.*;

public class BinaryTree<ArrayList> implements Serializable
{   
private static final long serialVersionUID = 1L;

protected static class Node<ArrayList> implements Serializable
{
    private static final long serialVersionUID = 1L;

    protected int data;
    protected Node<ArrayList> left;
    protected Node<ArrayList> right;

    public Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }

    public boolean isLeft() 
    {
        return (left == null);
    }
}

protected Node<ArrayList> root;;

public BinaryTree(int x)
{
    Node<ArrayList> node = new Node<ArrayList>(x);
    this.root = node;
}

public boolean isLeft()
{
    return(root.left == null);
}

public void addLeft(int m, BinaryTree.Node<ArrayList> node)
{
    root = new Node<ArrayList>(m);
    node.left = root;
}   

 public void preorder(Node<ArrayList> temp)  
 {  
      if (temp!=null)  
      {  
           System.out.println(temp.data);  
           preorder(temp.left);  
           preorder(temp.right);  
      }  
      else  
           return;  
 }

}

4

1 回答 1

0

听起来您正在以默认的广度优先方式构建树，根据字符串的内容为每个节点分配值。

如果有帮助，首先将字符串转换ArrayList<int>为要放入节点的值 - 例如，11010010将变为{1, 2, 4, 7}字符串中每个集合 1 的索引。

现在，我们必须构建树 - 但我们将始终以完全相同的方式构建树，称为广度优先，因为在深入之前先完全填充浅层。我们制作一个节点，然后告诉它“制作您的左节点，然后制作您的右节点，然后告诉您的左节点执行此操作，然后告诉您的右节点执行此操作”。（这与深度优先相反，在此处创建左节点，告诉左节点创建节点，然后创建右节点并告诉右节点创建节点）

所以你会有一个类似于这个伪代码的递归方法：

void continueTree(ArrayList<int> numbers)
{
    if (numbers.count() == 0) return;
    this.left = new Node(numbers.get(0));
    numbers.remove(0);
    if (numbers.count() == 0) return;
    this.right = new Node(numbers.get(0));
    numbers.remove(0);
    this.left.continueTree(numbers);
    this.right.continueTree(numbers);
}
于 2013-04-11T02:02:04.270 回答