Обход дерева в Java

Question

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

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

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

     5
  4     7
3  1  4

, тогда обход Inorder будет 341547, но я не могу понять код для возврата нужного мне узла (ради аргументаЯ предполагаю, что номер обхода по порядку равен 2 - это означает, что я хочу узел значения 1).

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

public int findNode(root, position){
   Stack<Integer> s = new Stack<Integer>();
   cNode = root; //cNode = current Node

   while(cNode.left != null)
      cNode = cNode.left;

     s.push(cNode);

   while(cNode.right != null)
     cNode = cNode.right;

   //stuck here.
}

Рекурсивный подход был проще, но я не могу понять, как проверить, есть ли у меня #, который я ищу:

public int findNode(root, position){
    cNode = root;   
    if(cNode != null){ 
       findNode(cNode.left, position);
       System.out.print(cNode.data);
       findNode(cNode.right, position);
   }
}

Я знаюэто пересекает дерево, но все еще не делает именно то, что я хочу.Любая помощь будет оценена.

Answer 1

Вы можете сделать это так:

public Node findNode(Node root, int position) {
    ArrayList<Node> a = new ArrayList<Node>();
    populateNodes(root, a);
    return a.get(position);
}

private void populateNodes(Node node, ArrayList<Node> a) {
    if (node == null) return;
    populateNodes(node.left, a);
    a.add(node);
    populateNodes(node.right, a);
}

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

Примечание 2: Как отметил Джим Гаррисон, вы можете оптимизировать алгоритм, если у вас есть счетчик потомков.

Answer 2

Вопрос неоднозначный. «Inorder» имеет смысл для двоичных деревьев, в этом случае «количество дочерних элементов» всегда равно двум, если только они не означают «количество потомков», и в этом случае вы можете использовать это, чтобы избежать выполнения линейного поиска по списку внутренних элементов (O * n) поскольку на каждом узле вы можете решить, какую ветвь взять (O * log n), исходя из количества потомков.

Answer 3

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

Nodeptr nthInInorder(Nodeptr root, int x){
 Nodeptr curr = root;
 int countedIn = 0, leftchildren = 0, currIn=0;

 while(curr!=NULL){
  if(curr->left == NULL)
   leftchildren = 0;
  else
   leftchildren = (curr->left)->data + 1;

  currIn = countedIn + leftchildren + 1;

  if(currIn == x)
   return curr;
  else if(currIn > x)
   curr = curr->left;
  else if(currIn < x)
   { countedIn = currIn + 1;
     curr = curr->right;
   }
  }
  return NULL;
 }

Сложность этого алгоритма O (log n)

Answer 4

Вместо прохождения позиции передайте номер обхода inorder и добавляйте к нему в каждом рекурсивном методе.