1

我有一个由 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;
}

binaryNode 是一个具有右孩子、左孩子和信息的节点。

现在，当我尝试打印出三个遍历（有序、前序和后序）时，这就是我得到的：

按顺序：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 24 25 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() + " ");               
        }
    }

}

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

4

1 回答 1

0

您的构建步骤看起来不错。但是，您的遍历比它们需要的要复杂得多。如果您想进行迭代遍历而不是使用递归，则只需要一个队列。

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

public static void printInOrder(binaryNode current)
{

    if(current == null)
    {
        return;
    }
    printInOrder(current.getLeftChild());
    System.out.print(current.getInfo() + " ");
    printInOrder(current.getRightChild());
}
于 2012-11-02T22:17:39.663 回答