用inOrder和preOrder数据构建二叉树

Question

我看过这个节目好几次了，但我看不出有什么问题。基本上，它应该从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。在下面的代码中，数组按照它们应该是的顺序排列(或者我假设的是什么)。

构建树代码：

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

BinaryTreeNode：

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());

}

Answer 1

至少有以下问题：

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

除此之外，上述问题的逻辑是有效的，至少与您提供的测试。