如何在 java 二叉搜索树中实现 returns 中序排序数组的方法？

Question

这是我试过的：

public int[] sortedArray() {
    int[] array = new int[size()];
    int index = 0;
    traverseInorder(root, array, index);
    return array;
}

private void traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        traverseInorder(n.left, array, index);
        array[index++] = n.value;
        traverseInorder(n.right, array, index);
    }
}

但是输出不正确。

如果我用这个输入创建一棵树：

{1,5,8,10,12,15,20,22,25,36,30,40,28,38,48,45,50}

我用 sortedArray 得到的输出是这样的：

[1, 5, 8, 10, 12, 15, 20, 22, 25, 36, 40, 48, 50, 0, 0, 0, 0]

我做错了什么？我意识到它跳过了根右侧的所有左子树，但我不明白为什么......

Answer 1

您正在覆盖写入数组的所有左子树元素。

假设您以指定的顺序将节点添加到树中，您将得到以下（极度不平衡的）树：

   1
    \
     5
      \
       8
        \
         10
          \
           12
            \
             15
               \
                20
                 \
                  22
                   \
                    25
                     \
                     36
                    /  \
                   30   40
                  /    /  \
                 28   38   48
                          /  \
                         45   50

可以看到中序输出中缺失的4个元素（28,30,38&45）都属于左子树

该行为的原因是在 traverseInorder(n.left, array, index); 将左子树写入数组和 returns 之后，它对 index 所做的任何更改都是本地的，因此array[index++] = n.value; 和 traverseInorder(n.right, array, index) 覆盖之前写入数组的左子树的值。

要解决此问题，您的递归方法应该 return 更新后的索引：

private int traverseInorder(Node n, int[] array, int index) {
    if (n != null) {
        index = traverseInorder(n.left, array, index);
        array[index++] = n.value;
        index = traverseInorder(n.right, array, index);
    }
    return index;
}

Answer 2

将您的 "traverseInorder" 函数更改为下面给出的函数。希望这个递归能起作用。

 private int traverseInorder(Node n, int[] array, int index)
 {
 if(n.left != null)
 index =  traverseInorder(n.left, array, index);

 array[index++] = n.value;

 if(n.right != null)
 index =  traverseInorder(n.right, array, index);

   return index;
}

如何在 java 二叉搜索树中实现 returns 中序排序数组的方法？

How do I implement a method that returns an inorder sorted array in a java binary search tree?

java

recursion

binary-search-tree

inorder