java - 在 Java 中根据 inOrder 和 preOrder 数据构建二叉树

Question

我已经执行过该程序几次，但我无法真正看到问题所在。基本上，它应该从 inOrder 和 preOrder 遍历数据(作为整数数组发送)重建二叉树。它是整数的二叉树。

这是我正在使用的树:

     234
    /   \
  98    678
 / \      \
45 124    1789

预订时间为 234、98、45、124、678、1789顺序为 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());

}

Answer 1

至少存在以下问题:

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

除上述问题外，逻辑正常，至少在您提供的测试中是这样。