Найти максимальный элемент в двоичном дереве

Question

Я действительно смущен тем, что нашел элемент в binary tree.

Вопрос: Когда мы говорим, поиск элемента в бинарном дереве, максимума в этом случае, мы предполагаем, что дерево сортируются ???
Если нет, посмотрите на код ниже, я получил его от книги и почти каждый интернет гиперссылка предлагает, подобный образец

int FindMaxNmb(BinaryTreeNode root) 
    { 
     int root_val,left,right,max; 
     if(root!=null) 
     { 
      root_val = root.getData(); 

      //recursion - this is what i dont understand 

      /* 
      * 
      * This code would have made sense if binary tree contained 
      * sorted elements,like The left subtree of a node contained 
      * only nodes with keys less than the node's key The right subtree 
      * of a node contained only nodes with keys greater 
      * than the node's key. 
      * 
      * */ 
      left = FindMaxNmb(root.getLeft()); 
      right = FindMaxNmb(root.getRight()); 

      //Find max nmbr 
      if(left > right) 
      { 
       max = left; 
      } 
      else 
      { 
       max = right; 
      } 

      if(root_val > max) 
      { 
       max = root_val; 
      } 
     } 
     return max; 
    } 

Что я не undertsand: принять этот recusrion к примеру left = FindMaxNmb(root.getLeft()); это будет продолжайте вызов, если он не достигнет крайнего левого нижнего листа, а затем присваивает значение, то же самое с getRight() .... но эта вещь работает только для самого левого узла, имеющего 2 дочерних ... как он проверяет значение оставшихся узлов (i Предполагая, что двоичное дерево не отсортировано)

Я знаю, что мне не хватает чего-то очень очевидного здесь ... пожалуйста, помогите !!

Answer 1

Разница между Binary Tree и Binary Search Tree является то, что BST имеет гарантированный между каждым узлом и его левыми/правыми дочерними узлами - простой BT не имеет заказ.

Представленный код будет работать для простого двоичного дерева, потому что он пересекает все узлы в порядке depth first. (Если данные был BST алгоритм нужно только найти «правый» узел и вернуть это значение, чтобы найти максимальное значение в дереве.)

Теперь в реализации BT показано, каждый рекурсивной функции находит максимальное значение поддерева, заданного левым или правым дочерним узлом (дочерний узел является корнем из поддерева), и возвращается это значение.

Например, рассмотрим это бинарное дерево, которое не является BST в этом случае (из Википедии):

стека вызовов, как это работает так, как через дерево, будет выглядеть где - представляет уровень стека, а число представляет узел.

-2 
--7 (l) 
---2 (l) 
---6 (r) 
----5 (l) 
----11 (r) 
--5 (r) 
---9 (r) 
----4 (l) 

Стек только может «расслабиться», когда он достигает терминал случая - это после того, как максимального значение левых и правых поддерева было вычислено (с помощью рекурсии в FindMaxNmb).

На разматывания фазе ..

• .. когда узел 11 достигается там нет правильного узла, так что возвращается к 6
• , так как это заканчивает поиск в правом поддереве (из 6) он возвращается к 7
• , так как это заканчивается поиском в правом поддереве (из 7), оно возвращается к 2
• так как это заканчивается поиском в левом поддереве (из 2), правом поддереве (5) вводится ..