Рекурсия - Двоичное дерево

Question

У меня есть этот код, чтобы найти диаметр двоичного дерева. Диаметр бинарного дерева: диаметр дерева (иногда называемый шириной) - это число узлов на самом длинном пути между двумя листьями в дереве.

Я пытаюсь понять приведенный ниже код и рекурсию в целом. Я пытаюсь сушить пробег с этим простым деревом. Я понимаю, что когда root составляет 20, высота станет 1 (Max (0,0) +1), а затем вернет Math.Max ​​(0 + 0 + 1, Max (0,0)). Мое понимание здесь - это установить ldiameter в 1 с этим возвращаемым значением, а root = 10. Правильно ли это? и в этот момент lh изменяется на 1. Как он изменяется на 1? Кроме того, если вы можете помочь мне сухим запустить это простое дерево шаг за шагом, это будет очень полезно.

10 
/ \ 
20 30 


public int FindDiameter_util(Node root, ref int height) 
     { 
      /* lh --> Height of left subtree 
      rh --> Height of right subtree */ 
      int lh = 0, rh = 0; 

      /* ldiameter --> diameter of left subtree 
       rdiameter --> Diameter of right subtree */ 
      int ldiameter = 0, rdiameter = 0; 
      if (root == null) 
      { 
       height = 0; 
       return 0; /* diameter is also 0 */ 
      } 
      /* Get the heights of left and right subtrees in lh and rh 
       And store the returned values in ldiameter and ldiameter */ 
      ldiameter = FindDiameter_util(root.left, ref lh); 
      rdiameter = FindDiameter_util(root.right, ref rh); 

      /* Height of current node is max of heights of left and 
       right subtrees plus 1*/ 
      height = Math.Max(lh, rh) + 1; 

      return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 
     } 

Answer 1

Последняя строка наиболее важным здесь:

return Math.Max(lh + rh + 1, Math.Max(ldiameter, rdiameter)); 

Есть 3 случая для текущего дерева:

1) самый длинный простой путь (для дерева currenet) в левом поддереве

2) самый длинный простой путь (для дерева currenet) в правом поддереве

3) lo Простой простой путь состоит из трех частей: путь от самого глубокого узла к корню в левом поддереве, текущий узел, путь от корня до самого глубокого узла в правом поддереве.

Мы можем вычислить 3 возможных диаметра рекурсивно и после этого выбрать максимум из них.

Answer 2

Давайте рекурсию через простое дерево:

[]  <---- root 
/ \ 
[] [] <---- children 

Когда функция изначально называется, root == 0 будет истинным, поэтому высота входной инициализируется 0:

[h=0]  <---- root 
/ \ 
    [] [] <---- children 

Тогда вы будете устанавливать высота в корне для левого и правого поддеревьев до 0:

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     []  []   <---- children 

Тогда y НУ рекурсию на левом ребенка, переходя в lh в качестве параметра высоты:

[h = 0, lh = 0, rh = 0]  <---- root 
     / \ 
     [h=0] []   <---- children 

Левый ребенок будет инициализировать свои переменные высоты для своих собственных левых и правых поддеревьев:

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

Тогда левый ребенок будет попытка рекурсировать на левом поддереве (хотя его нет; это null):

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
     /
     null 

В этом нулевой узел, мы признаем его как таковой, и вернуться 0, идя обратно к родителю, lh получает значение 0 (опять же, так без изменений):

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

Тогда мы рекурсию на правом поддереве, но это тоже нуль:

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 
       \ 
      null 

Так мы возвращаемся 0 Ф.О. г его высоты к родителю, который устанавливает rh к 0 (снова):

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=0, lh=0, rh=0] []   <---- children 

До сих пор довольно неинтересный. Но теперь, когда мы знаем высоту дочерних поддеревьев, мы можем вычислить высоту в текущем дереве как max(lh, rh) + 1, что дает нам высоту 1 для этого листа (дерево с только корнем имеет высоту 1, поэтому имеет смысл, что поддерево с только корнем имеет высоту 1).

 [h = 0, lh = 0, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

Однако h на этом уровне на самом деле ссылка на lh на корню, так что это тоже становится 1:

 [h = 0, lh = 1, rh = 0]  <---- root 
      /  \ 
    [h=1, lh=0, rh=0] []   <---- children 

Теперь левое поддерево сделано, поэтому мы рекурсию на праве поддерево таким же образом (подробности опущены):

  [h = 0, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

Теперь, когда мы Рекурсия на обоих поддеревьев, мы возвращаемся к корню, который теперь знает высота его левого и правого поддеревьев (оба 1), так что он может вычислить:

height = Math.Max(lh, rh) + 1; 

который

height = Math.Max(1, 1) + 1 = 2 

Так корень получает ее высота устанавливается в 2:

  [h = 2, lh = 1, rh = 1]   <---- root 
      /    \ 
    [h=1, lh=0, rh=0] [h=1, lh=0, rh=0] <---- children 

Answer 3

Рекурсия - это подход на основе стека. Рекурсивные вызовы функции будут выполняться раньше, чем эмитент. Вы можете лучше понять рекурсию, если подумать о концепции композиции функций. Давайте посмотрим на этот вызов функции например:

f(g(x)) 

Как вы можете видеть, параметр f является g(x), что означает, что g(x) должна быть рассчитана, прежде чем один выполняет f(g(x)), поэтому g(x) является зависимость f(g(x)). Теперь представьте, что g является f, так что вы звоните

f(f(x)) 

Подобным же образом, f(x) является зависимость f(f(x)), так как вы не можете рассчитывать f(f(x)) без результата f(x).

Если вы понимаете эту чисто математическую концепцию, то следующим шагом будет добавить алгоритм в f в качестве контекста. В программировании f(f(x)) не обязательно является только вычислением, но некоторые изменения состояния могут возникать в процессе.

Следующий шаг - понять концепцию повторной рекурсии. В нашем случае мы не знаем заранее, сколько раз мы должны называть FindDiameter_util с FindDiameter_util, так как он должен работать для любого дерева. Итак, давайте немного проанализируем эту функцию.

Факты:

• листовые узлы признаваемые из того, что root == null, это конец знак, а также (см return)
• высота листа узлов 0
• в не- тривиальный случай, когда узел не является листовым узлом, задача делится на две подзадачи (левое поддерево и правое поддерево)
• , когда вычисляется результат подзадач, дерево большего дерева + 1 (мы добавляем текущий узел) - это максимум h восемь

Используемая здесь стратегия называется Divide et Impera. Это состоит из нескольких этапов: - разделите задачу на аналогичную, но меньшую подзадачу, пока не достигнете тривиальности. - покорите результаты, получив ответ на постепенно более сложные подзадачи, пока не получите ответ на начальный вопрос

В нашем случае алгоритм, вкратце, идет от корня до листьев, пока он не достигнет тривиальности во всех поддисках, который определяется конечным знаком root == null, а затем используйте тривиальный ответ, чтобы получить ответ к следующим тривиальным вопросам. Итак, вы переходите от корня к листу, чтобы разделить, а затем вернуться от листа к корню, чтобы победить.