尝试将二叉搜索树转换为数组（returns Null）

Question

我想将我的二叉搜索树转换成数组（使用顺序遍历）。

要做到这一点，我有 3 种方法。

问题：java.lang.NullPointerException 在方法 1 System.out.print() 调用中。但是 returns 4 个元素成功（2 个元素为空，因此出现此错误，但为什么呢？！）

Class(1主)方法1(调用方法)

 public void top() {
    array[] unsortedList = this.bookList.returnBSTAsArray(6); // 6 is the number of nodes in tree
     for (Book book: unsortedList) {
         System.out.println("--> Title: " + book.title());
     }

class(二)方法二

// traverse BST in order and return an array of books 
public Book[] returnBSTAsArray(int totalLength) {
    Book[] list = new Book[totalLength];
    int index = 0;

    storeInOrder(this.root, list, index);  // root is node accessible to this class

    return list;
}

Class（二）方法三——有趣的顺序遍历方法

 private Book[] storeInOrder(Node root, Book[] array, int index) {
        if (root == null)
            return null;
        storeInOrder(root.leftChild, array, index);
        array[index++] = root.movie;
        storeInOrder(root.rightChild, array, index);

        return array;
    }

Answer 1

您可以通过跟踪每个元素的索引来将其添加回结果数组

  static class BST {

        private class Node {
            private Integer key;
            private Node left, right;
            private int index;

            public Node(Integer key, int index) {
                this.key = key;
                this.index = index;
            }
        }

        private Node root;
        private int size = 0;

        public void put(int[] arr) {
            if (size >= arr.length)
                return;
            root = put(root, arr[size], size);
            size++;
            put(arr);
        }

        private Node put(Node node, int key, int index) {
            if (node == null)
                return new Node(key, index);
            int cmp = Integer.valueOf(key).compareTo(node.key);
            if (cmp < 0)
                node.left = put(node.left, key, index);
            else if (cmp > 0)
                node.right = put(node.right, key, index);
            else
                node.key = key;
            return node;
        }

        public int size() {
            return size;
        }

        public int[] keys() {
            int[] result = new int[size];
            get(root, result, 0);
            return result;
        }

        public void get(Node node, int[] result, int i) {
            if (i >= result.length || node == null)
                return;
            result[node.index] = node.key;
            get(node.left, result, ++i);
            get(node.right, result, ++i);
        }
    }

, 主要

    public static void main(String[] args) {
        BST bst = new BST();
        bst.put(new int[] { 10, 20, 5, 40, 1, 60, -10, 0 });

        for (int num : bst.keys()) {
            System.out.print(num + " ");
        }
    }

，输出

10 20 5 40 1 60

Answer 2

Java 是一种 "pass by value" 语言。因此（一般来说），调用者看不到函数中参数值的任何更改。

storeInOrder 函数是问题所在。它被写成好像调用者可以看到对 index arg 的更改。

这个假设是不正确的。

此外，它return是数组，但由于数组确实是一个引用，它在方法中没有改变（但它的内容是），因此不需要return 结果数组。

因此，更好的配置文件是 storeInOrder 和 return 数组中第一个可用单元格的索引。

/**
 * insert the elements of the bst (denoted by root) into array,
 * starting at index (the first available position in array) and
 * returns the first available position after insertion)
 * pre-conditions : 
 *    - root is a bst containing n elements
 *    - array contains enough available cells
 *    - index = i0
 * post-conditions
 *    - tree is unchanged
 *    - array[i0..i0+n-1] contains elements of the bst
 *    - functions returns i0+n
 */
private int storeInOrder(Node root, Book[] array, int index) {
    if (root == null)
        return index;
    // then call on left, add root, call on right...
    int i = storeInOrder(root.leftChild, array, index);
    array[i] = root.movie;
    return storeInOrder(root.rightChild, array, i+1);
}

注意：如果你想要数组按Book的顺序排列，只需改变递归调用的顺序即可得到前缀左右遍历。

尝试将二叉搜索树转换为数组（returns Null）

Trying to Convert Binary Search Tree to Array (returns Null)

java

arrays

binary-search

inorder

binary-search-tree