Построить BST от Preorder

Question

Как и многие новички, моя голова взрывается от рекурсии. Я посмотрел много ответов/объяснений на SO. но я все еще не понимаю эту концепцию. (Это не домашнее задание, я пытаюсь переучивать то, что я не получил, и рекурсия никогда не была строкой)

При обходе предзаказов создайте двоичное дерево. С рекурсией это должно быть обманчиво простым :), но я просто не могу это получить.

I см., что порядок arr должен быть в узлах заказа. Какие ошибки я:

1. Что делать, если узел уже имеет левый/правый? Как это работает?

2. Как могут узлы вставки рекурсии, например, в следующем порядке?

   12, 10, 6, 13 
   

15 является корнем, 5, 3 и оставили

Как 6 вставляются правильно, так как левый ребенок 10-х годов?

12 
10 13 
6* 

Вот код скелета:

main() 
{ 
    int[] arr = {}; 
    //make the first node a root node. 
    node n = new node(arr[0]); 
    buildbst(n, arr, 0) 
} 

buildbst(node root, int[] arr, int i) 
{ 
    if (i == arr.length) return; 

    if (arr[i] < root.data) 
     root.left = new node (arr[i]); 
    else 
     root.right = new node(arr[i]); 

    buildbst(root.left, arr, i++); 
    buildbst(root.right, arr, i++); 
} 

EDIT:

Я просто понял, если я прохожу в рекурсивном вызове buildbst(root.left, arr+i, i++) является то, что правильный путь? Или я приближается это все неправильно - мешанину динамического программирования и рекурсии и разделяй и властвуй ...

Answer 1

1. Он уже не может иметь левый/правый ребенка. Вы называете это для корня, у которого нет детей, чтобы начать. Затем вы вызываете его для левого ребенка и создаете детей, где это необходимо, и вызывайте функцию для этих детей и так далее. Вы никогда не посещаете левого ребенка снова, как только вы идете вправо, и вы не можете добраться до узла из функции, вызванной его дочерним элементом (поскольку соединение с деревом отсутствует, за исключением стека рекурсии).

2. Это то, что должно произойти, когда данный 12, 10, 6, 13:

   • Создает корень 12
   • вызовы buildbst(node(12), arr, 1)
     • Создать node(12).left = node(10)
     • вызовы buildbst(node(10), arr, 2)
       • Создать node(10).left = node(6)
       • вызовы buildbst(node(6), arr, 3)
         • 13 > 12, должен быть правильным ребенком 12, так что ничего
       • 13 > 12, должен быть правильным ребенком 12, поэтому ничего не делать
     • Создать node(12).right = node(13)
     • Звонки buildbst(node(13), arr, 3)
       • О, посмотри, больше нет элементов, все готово.

выше не то, что произойдет с вашим кодом по 2 причинам:

• Ваш код будет только создавать либо левый или правый ребенка, а не как (из-за if-else))
• Ваш код не содержит must be right child of '12', который является небольшим комплексом

Приведенный ниже код должен охватывать его.

node buildbst(int[] arr) 
{ 
    node n = new node(arr[0]); 
    // 9999999999 is meant to be > than the biggest element in your data 
    buildbst(n, arr, 1, 9999999999); 
    return node; 
} 

int buildbst(node current, int[] arr, int i, int biggestSoFar) 
{ 
    if (i == arr.length) return i; 

    // recurse left 
    if (arr[i] < current.data) 
    { 
     current.left = new node(arr[i++]); 
     i = buildbst(current.left, arr, i, current.data); 
    } 

    // recurse right 
    if (i < arr.length && arr[i] < biggestSoFar) 
    { 
     current.right = new node(arr[i++]); 
     i = buildbst(current.right, arr, i, biggestSoFar); 
    } 

    return i; 
} 

Объяснение:

Целью biggestSoFar является предотвращение:

15       15 
/       /\ 
    5  versus (the correct) 5 20 
/\      /
1 20      1 

Когда рекурсии слева от 15, например, нам нужно прекратить обработку элементов, как только мы получаем элемент > 15, который произойдет, когда мы получим 20. Таким образом, мы передаем current.data и прекращаем обработку элементов, если получим большее значение.

При рекурсии с 5, например, нам необходимо прекратить обработку элементов, как только мы получим элемент > 15, который произойдет, когда мы получим 20. Таким образом, мы пропускаем biggestSoFar и останавливаем обрабатывающие элементы, если получим большее значение.