Извлечение глубины узла двоичного дерева не рекурсивно

Question

Может ли кто-нибудь указать способ получения глубины узла в двоичном дереве (не сбалансированном или BST) без использования рекурсии? В идеале в Java/C/C#

Узел представлен как:

class Node 
{ 
    Node Left; 
    Node Right; 
    string Value; 
    int Depth; 
} 

Использование уровня ордера со списком FIFO была моя первая мысль, но я был поставлен в тупик при обнаружении при изменении уровня, определенные для несбалансированной деревья.

Answer 1

Вы можете реализовать любой рекурсивный метод со стеком, так как рекурсия работает в любом случае. Представьте, что ваш resursive функция выглядит

function int getDepth (Node head, string val) 
{ 
    if (head == NULL) 
     return -1; 

    if (val == head.Value) 
     return head.Depth; 

    return MAX(getDepth(head.Left, val), getDepth(head.Right, val); 
} 

Не-resursive функция выглядит как

function int getDepth (Node head, string val) 
{ 
    Stack s = new Stack(); 

    s.push(head); 

    while(s.count > 0) 
    { 
     Node temp = s.pop(); 

     if (temp != NULL) 
     { 
      if (s.Value == val) 
       return s.Depth; 
      else 
      { 
       s.push(temp.Left); 
       s.push(temp.Right); 
      } 
     } 

    } 


    return -1; 
} 

EDIT:

Эта функция задает глубину для каждого узла

function void setDepth (Node head) 
{ 
    Stack s = new Stack(); 

    head.Depth = 0; 
    s.push(head); 

    while(s.count > 0) 
    { 
     Node temp = s.pop(); 

     if (temp != NULL) 
     { 
      if (temp.Left != NULL) 
      { 
       temp.Left.Depth = temp.Depth + 1; 
       s.push(temp.Left); 
      } 

      if (temp.Right != NULL) 
      { 
       temp.Right.Depth = temp.Depth + 1; 
       s.push(temp.Right); 
      } 
     } 

    } 

} 

Answer 2

I Предположим, вы имеете в виду заполнение значения глубины на узле и/или определение максимальной глубины. Один из способов сделать это - использовать два списка и сделать порядок уровней, как было предложено. Это было бы сродни:

int level=0; 
List<Node> currentLevel = new List<Node>{root}; 
while(currentLevel.Count != 0) 
{ 
    List<Node> nextLevel = new List<Node>{}; 
    foreach(Node node in currentLevel) 
    { 
    if(node.Right!=null) nextLevel.Add(node.Right); 
    if(node.Left != null) nextLevel.Add(node.Left); 
    node.Depth=level; 
    } 
    level++; 
    currentLevel=nextLevel; 
} 

В принципе, вы перечислить каждый узел на заданном уровне, а затем найти каждый узел на следующем уровне; пока не закончите узлы/уровни. Очевидно, что List можно заменить практически любым списком, например структурой данных (Linked List, Queue и т. Д.). И последнее значение «уровня» будет максимальной глубиной + 1. Я подозреваю.

Еще одно разъяснение, основанное на повторном рассмотрении вопроса; если вы ищете узел с определенным значением и хотите найти его глубину, вы должны изменить цикл foreach, чтобы включить «if (node.Value == searchValue) уровень возврата;». И, технически, если вы ищете определенное значение, вам не следует делать обход порядка порядка, а скорее поиск значения с использованием соответствующих свойств двоичного дерева (например, val < currentNode.Value goto left else goto right), и отслеживание вашей глубины. Если вам задан только узел и вы хотите найти его глубину, вам нужно либо выполнить двоичный поиск узла из корня, либо вам нужно будет отслеживать родительский узел.

Answer 3

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

int getDepthNoRecursion(Node n) { 
    if(n == null) { 
    return 0; 
    } 
    int retval = 0; 
    n.depth = 1; 
    Stack s = new Stack(); 
    s.push(n); 
    while(!s.isEmpty()) { 
    Node n = (Node) s.pop(); 
    int currDepth = n.depth; 
    if(currDepth > retval) { 
     retval = currDepth; 
    } 
    if(n.left != null) { 
     n.left.depth = currDepth + 1; 
     s.push(n.left); 
    } 
    if(n.right != null) { 
     n.right.depth = currDepth + 1; 
     s.push(n.right); 
    } 
    } 
    return retval; 
} 
class Node { 
    Node left; 
    Node right; 
    int depth = 0; 
} 

Answer 4

Вот наиболее эффективное решение, которое я придумал (C++). Хитрость заключается в использовании второй очереди для хранения дочерних узлов всех узлов на вашем текущем уровне. Это будет работать для сбалансированных и несбалансированных бинарных деревьев.

template <class T> 
struct TreeNode { 
    TreeNode<T>* left_; 
    TreeNode<T>* right_; 
    T* data_; 
}; 

template <class T> 
int find_depth(const TreeNode<T>* root) { 
    if (root == NULL) return 0; 
    int depth = 0; 
    std::queue<const TreeNode<T>*>* q1 = new std::queue<const TreeNode<T>*>; 
    std::queue<const TreeNode<T>*>* q2 = new std::queue<const TreeNode<T>*>; 
    q1->push(root); 
    while (!q1->empty()) { 
    // At the top of the outer loop q1 contains a complete horizontal level of the tree                     
    depth++; 

    // Swap the queue pointers to avoid any deep copies                             
    std::queue<const TreeNode<T>*>* tmpQ = q2; 
    q2 = q1; 
    q1 = tmpQ; 

    // Iterate over this level, inserting all children into q1                           
    while(!q2->empty()) { 
     const TreeNode<T>* node = q2->front(); 
     if (node->left_ != NULL) q1->push(node->left_); 
     if (node->right_ != NULL) q1->push(node->right_); 
     q2->pop(); 
    } 
    } 
    delete q1; 
    delete q2; 
    return depth; 
}