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

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

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), и отслеживание вашей глубины. Если вам задан только узел и вы хотите найти его глубину, вам нужно либо выполнить двоичный поиск узла из корня, либо вам нужно будет отслеживать родительский узел.

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

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);
}

Функция нерегулярности выглядит примерно так:

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;
}

РЕДАКТИРОВАТЬ:

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

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);
            }
        }

    }

}

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

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;
}

Вот самое эффективное решение, с которым я столкнулся (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;
}