向BST有序遍历插入数组

Question

我想使用有序遍历遍历给定的树。将排序后的数组插入BST（保持相同的形状）

这是我的任务：

public static BinTreeNode<Integer> ARR_TO_BST(BinTreeNode<Integer> root, int[] arr, int ind){


    if (root.GetLeft() != null) 
        ARR_TO_BST(root.GetLeft(), arr, ind);

    root.SetInfo(arr[ind]);
    ind+=1;

    if (root.GetRight() != null)
        ARR_TO_BST(root.GetRight(), arr, ind);

    return root;

问题是，如果数组为arr = {10,20,30,40,50,60}树是：

返回输出是一棵树，如果我对其进行有序遍历，则是：10 20 10 20 10 20 ...而不是10 20 30 40 50 60

我需要输出为图片的相同形状，但使用arr的值时，算法将在树上依次遍历：左子树-顶点-右子树但我们不读取值，而是将值从arr插入到root

非常感谢您的帮助！谢谢

Answer 1

您永远不会更改ind。首次调用ARR_TO_BST之后，它仍然保持调用前的状态。使ARR_TO_BST返回它放置的元素数：

    if (root.GetLeft() != null)
        ind = ARR_TO_BST(root.GetLeft(), arr, ind);
    root.SetInfo(arr[ind]);
    if (root.GetLeft() != null)
        ind = ARR_TO_BST(root.GetLeft(), arr, ind + 1);
    return ind;

您应该没事。

Answer 2

您可以通过跟踪每个元素的索引来使用完成，将其添加回结果数组中>]

   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() {
            Queue<Node> queue = new ArrayDeque<>();
            int[] result = new int[size];
            queue.add(root);
            while (!queue.isEmpty()) {
                Node node = queue.poll();
                result[node.index] = node.key;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            return result;
        }
    }
，Main

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

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

10 20 5 40 1 60