1

我已经通过这个程序几次，但我真的看不出这个问题。基本上，它应该从 inOrder 和 preOrder 遍历数据（作为整数数组发送）重建二叉树。它是整数的二叉树。

这是我正在使用的树：

     234
    /   \
  98    678
 / \      \
45 124    1789

preOrder 是 234, 98, 45, 124, 678, 1789 inOrder 是 45, 98, 124, 234, 678, 1789

出现的问题是 1789。代码将树重建到 1789，但出于某种奇怪的原因将其排除在外。我决定在 inOrder 数组中切换 678 和 1789，将 1789 放在 678 的左侧，将 0 放在 678 的右侧。在下面的代码中，数组按照它们应该是的顺序（或者什么我认为应该是）。

构建树代码：

public class BuildTree
{

public static BinaryTreeNode buildTree(int inOrder[], int preOrder[], int preIndex )
{               
    if (inOrder.length > 1)  
    {
        int inIndex = 0;
        for (int i = 0; i < inOrder.length; i++)
        {
            if (preOrder[preIndex] == inOrder[i])
            {
                inIndex = i ;
                break;                  
            }
        }

        if (inIndex > 0)
        {          
            BinaryTreeNode node = new BinaryTreeNode(inOrder[inIndex]);

            if (preIndex < preOrder.length - 1 )
            {
            node.setLeft(buildTree(leftArray(inOrder, inIndex), preOrder, preIndex + 1));
            node.setRight(buildTree(rightArray(inOrder, inIndex), preOrder, inIndex + 1));  
            }

            return node;
        }           
    }       
    return new BinaryTreeNode(inOrder[0]);
}


public static int[] leftArray(int[] input, int index)
{        
    int left[] = new int [index];

    for (int i = 0 ; i < index ; i ++)
    {
        left[i] = input[i] ;
    }

    return left;        
}


public static int[] rightArray(int[] input, int index)
{               
    int right[] = new int [index];
    int x= 0;

    for (int i = index +1  ; i < input.length  ; i ++)
    {
        right[x] = input[i] ;
        ++x;
    }

    return right;       
}
} //end class

二叉树节点：

public class BinaryTreeNode
{
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;

    BinaryTreeNode()
    {

    }

    BinaryTreeNode(int data)
    {
        this.data = data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }
}

主要测试方法：

public static void main(String[] args)
{
    int[] preOrder = {234, 98, 45,  124, 678, 1789};
    int[] inOrder =  {45,  98, 124, 234, 678, 1789};

    BinaryTreeNode bsTree = BuildTree.buildTree(inOrder, preOrder, 0);

    System.out.println(bsTree.getData());
    System.out.println(bsTree.getLeft().getData());
    System.out.println(bsTree.getLeft().getLeft().getData());
    System.out.println(bsTree.getLeft().getRight().getData());
    System.out.println(bsTree.getRight().getData());
    System.out.println(bsTree.getRight().getRight().getData());
    System.out.println(bsTree.getRight().getLeft().getData());

}
4

1 回答 1

0

至少有以下几个问题：

  1. inIndex可以等于 0，则可以在 inOrder 列表的第一个位置找到一个元素。
  2. return new BinaryTreeNode(inOrder[0]);仅当 inOrder 列表中有元素时才应返回。当树不完整时，您缺少叶节点，您应该return null;
  3. rightArray您需要分配元素，而input.length-index-1不仅仅是index.

除了上述问题之外，逻辑正在运行，至少在您提供的测试中。

于 2013-04-08T21:29:51.383 回答