Преобразовать отсортированный массив в двоичное дерево поиска с минимальной высотой

java recursion binary-search-tree

526 просмотра

1 ответ

18 Репутация автора

Я хочу преобразовать отсортированный целочисленный массив в двоичное дерево поиска. Я разместил свой код ниже. То, что я не могу изобразить, это то, как рекурсия на самом деле работает с циклом for как вставка.

Так что, если мой массив [1,3,4, 5,8,10], я делаю 4, который является серединой массива, становится корнем моего BST, затем делаю цикл с начала массива и вставляю в дерево корень только что создан. Мой вопрос, почему порядок вставленных результатов не так, как отсортированный массив?введите описание изображения здесь

public TreeNode sortedArrayToBST(int[] A) {  
    if (A == null || A.length == 0){
       return null;
    }
    TreeNode root = new TreeNode(findMid(A));
    for (int i = 0; i < A.length; ++i){
        insert(root, A[i]);
    }      
 return root;
}




private int findMid(int[] A){

    int left = 0;
    int right = A.length -1;
    int mid = A[left + (right - left)/2];
    return mid;
}

private void insert (TreeNode root, int val){

    if (root == null || root.val == val){
        return;
    }
    if (val < root.val){
            TreeNode left = new TreeNode(val);
            root.left = left;
        }
    if (val > root.val){
            TreeNode right = new TreeNode(val);
            root.right = right;
        }

    insert(root.left,val);
    insert(root.right,val);

}
Автор: wenjing li Источник Размещён: 04.08.2016 07:50

Ответы (1)

0 плюса

5973 Репутация автора

У вас есть пара проблем с вашим рекурсивным insertметодом. Во-первых, каждый раз, когда значение valне равно значению корня, вы создаете новый узел. Это неверно, потому что, делая это, вы создаете несколько узлов и устанавливаете дочерний элемент корня на каждом шаге рекурсии для этих новых узлов, что является избыточным. Давайте рассмотрим ваш метод для каждого узла.

Добавление 4

   4

Добавление 1

   4
  / 
 1

Добавление 3

   4
  /
 3

На данный момент, мы можем точно определить ошибку. Почему левого ребенка 4 заменили на 3? Давайте рассмотрим ваш insertметод, где rootнаходится узел со значением 4 и val3.

  • Первое условие if-оператора оценивается как ложное, поэтому перейдем к
  • Второе условие if-оператора оценивается как true, поэтому создайте новый узел с valи установите root.left равным этому новому узлу
  • Третье условие if-оператора оценивается как ложное, поэтому продолжаем
  • Рекурсивный вызов insert(3.left, 3)просто возвращается с3 == 3
  • Рекурсивный вызов insert(null, 3)просто возвращается сroot == null

Так в чем же дело? Прекратите создавать новые узлы при каждом рекурсивном вызове в стеке вызовов. Хотите верьте, хотите нет, вы должны создавать новый узел только тогда, когда он rootравен нулю, потому что это означает, что вы прошли дерево до пустого дочернего элемента. Как насчет рекурсивных вызовов? Нет необходимости делать рекурсивный вызов для каждого из дочерних элементов root, потому что вы проходите только один путь обхода в BST. Вы поворачиваете налево или направо на каждом узле. Так что вы делаете только рекурсивный вызов в зависимости от значения valотносительно значения корня. Вот как это должно выглядеть,

private TreeNode insert (TreeNode root, int val){

    if (root == null){
        return new TreeNode(val);
    }
    if (val == root.val){
        //if you don't want to add repeats in the tree, then
        //add your own code to deal with that here
        //although as it stands now, this code will not add repeats
    }
    if (val < root.val){
            root.left = insert(root.left, val);
    }
    if (val > root.val){
            root.right = insert(root.right, val);
    }
    return root;
}
Автор: Chris Gong Размещён: 04.08.2016 08:09
Вопросы из категории :
32x32