如何递归地构建最低高期二进制搜索树

Question

i有一个26个整数的数组，1-26，顺序为a [0] = 1 ... a [25] = 26。我已经使用此代码了一段时间了，我似乎无法确定为什么当前的代码无法正常工作。这是我的构建方法：

public static binaryNode buildBalanced(int[] a, int low, int high)
{
    if(low > high)
    {
        return null;
    }
double mid = Math.floor((low + high)/2);
int iMid = (int)mid;
binaryNode node = new binaryNode(a[(int)iMid]);
node.setLeftChild(buildBalanced(a, low, (int)(iMid-1)));
node.setRightChild(buildBalanced(a, (int)(iMid+1), high));
return node;
}

二进制节点是一个有正确的孩子，左孩子和信息的节点。

现在，当我尝试打印出三个遍历（按秩序，预订和后订单）时，这就是我得到的：

inorder：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

预订：13 1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 23 24 26 26

邮寄：1 2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 13

在我看来，该代码无法正常工作。还是我的内部，预订单和后订单方法是错误的？

这是我正在使用的三种打印方法：inorder：

public static void printInOrder(binaryNode current, Queue<binaryNode> queue)
{
    if(current == null)
    {
        queue.add(current);
        return;
    }
    if (current.getLeftChild() != null)
    {
        printInOrder(current.getLeftChild(), queue);
    }
    queue.add(current);
    if(current.getRightChild() != null)
    {
        printInOrder(current.getRightChild(), queue);
    }
    if(current.getParent() == null)
    {
        while(!queue.isEmpty())
        {
            System.out.print(queue.remove().getInfo() + " ");               
        }
    }
}

预订：

public static void printPreOrder(binaryNode current, Queue<binaryNode> queue)
{
     if(current == null)
        {
            queue.add(current);
            return;
        }
        queue.add(current);
        if (current.getLeftChild() != null)
        {
            printInOrder(current.getLeftChild(), queue);
        }
        if(current.getRightChild() != null)
        {
            printInOrder(current.getRightChild(), queue);
        }
        if(current.getParent() == null)
        {
            while(!queue.isEmpty())
            {
                System.out.print(queue.remove().getInfo() + " ");               
            }
        }
}

邮政：

public static void printPostOrder(binaryNode current, Queue<binaryNode> queue)
{
    if(current == null)
    {
        queue.add(current);
        return;
    }
    if (current.getLeftChild() != null)
    {
        printInOrder(current.getLeftChild(), queue);
    }
    if(current.getRightChild() != null)
    {
        printInOrder(current.getRightChild(), queue);
    }
    queue.add(current);
    if(current.getParent() == null)
    {
        while(!queue.isEmpty())
        {
            System.out.print(queue.remove().getInfo() + " ");               
        }
    }
}

您可以提供的任何帮助将不胜感激！谢谢！

Answer 1

您的构建步骤看起来不错。但是，您的遍历比需要的要复杂。只有在要进行迭代遍历而不是使用递归时，您才需要队列。

由于您正在使用递归，因此遍历不需要队列：

public static void printInOrder(binaryNode current)
{
    if(current == null)
    {
        return;
    }
    printInOrder(current.getLeftChild());
    System.out.print(current.getInfo() + " ");
    printInOrder(current.getRightChild());
}