Двоичное дерево - найти позицию в обходе по порядку

Question

У меня есть двоичное дерево поиска, где я должен реализовать метод под названием

int valueAtPosition(int x) 

Проблема в том, что мне нужна позиция в порядке обхода.

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

public void inOrderTraverseTree(Node root){
    if(root != null){
        inOrderTraverseTree(root.leftChild);
        System.out.println(root);
        inOrderTraverseTree(root.rightChild); 
    }    
}

Answer 1

Вы также можете использовать счетчик в рекурсивном подходе. Тем не менее, вы не можете просто передать int counter Аргумент - вам нужны все вызовы, чтобы увидеть "один и тот же" счетчик, поэтому вам придется заключить его в класс (или, как в этом случае, во внутренний класс):

public static class Counter {
   private int value;
   public Counter(int initialValue) { value = initialValue; }
   public boolean decrement() { value--; return value == 0; }
   public boolean expired() { return value <= 0; }
}

public Node inOrderTraverseTree(Node root, Counter counter){
   if  (root != null && ! counter.expired()) {
       Node left = inOrderTraverseTree(root.leftChild, counter);
       if (left != null) {
            return left;
       } else if (counter.decrement()) {
            return root;
       } else {
            return inOrderTraverseTree(root.rightChild, counter); 
       }
   } else {
       return null;
   }
}

Чтобы найти 9-й узел в порядке (используя индексацию на основе 1), вы должны назвать это как

Node the9th = inOrderTraverseTree(root, new Counter(9));

Если 9-го узла нет, он вернет null, Если вы хотите использовать индексирование на основе 0, измените { value--; return value == 0; } в { return value-- == 0; }

Answer 2

Я думаю, что другие решения O(n). Все, что вам для этого нужно, - это количество дочерних элементов для каждого узла для O(log n).

Когда вы вставляете узел, для каждого пройденного вами узла вы увеличиваете счетчик на пройденном узле на единицу.

Вы должны поддерживать эти счетчики при удалении, перебалансировке и т. Д., Что обычно не сложно.

При этом вы можете получить положение узла при вставке, найти положение узла по значению или найти узел по положению.

Найти узел по позиции - это тот же тип двоичного обхода, что и при поиске по значению. Если вы хотите элемент в позиции 1000, то вы начинаете с корня. Нет корня, нет элемента в этой позиции. Затем вы смотрите на левого ребенка (вы можете сделать это и в другом порядке и переключаться по возрастанию / убыванию), слева, если существует левый ребенок, число детей слева равно 0 плюс количество детей слева узел. Пусть в этом сценарии говорят, что левые существуют и имеют 500 детей. Тогда вы знаете, что 1000 нельзя оставить, потому что слева не хватает предметов, поэтому должно быть и справа. Вы можете повторить это, также проверяя границы до конца.

Для простого O (n) в порядке обхода, если у вас есть глобальный счетчик, вы просто увеличиваете его только после обхода влево. Это должно сделать то же самое, что и поиск в глубину. Нет необходимости уменьшать и увеличивать счетчики или толкать и выталкивать в стек. Вы также можете сделать так, чтобы ваши функции возвращали счет.

public int inOrderTraverseTree(Node root){
    if(root == null)
        return 0;

    int count = inOrderTraverseTree(root.leftChild);
    count++;
    count += inOrderTraverseTree(root.rightChild);
    return count;
}

Такой подход становится раздражающим, только если вы хотите вернуть узел.

Конечно, вы можете заменить рекурсивную функцию своим собственным стеком, но это редко требуется для оптимизации производительности, и вам будет гораздо лучше использовать решение O (log n), если вам нужна производительность, чем оптимизированное решение на основе пользовательских стеков.

Answer 3

Итеративный подход обхода по порядку делает это довольно простым. Увеличивайте счетчик всякий раз, когда узел выталкивается из стека. Когда счетчик равен x, вернуть значение узла.

Integer valueAtPosition(int x, Node root) {
  int count = 0;
  List<Node> stack = new ArrayList<>();
  Node node = root;
  while (!stack.isEmpty() || node != null) {
    if (node != null) {
      stack.add(node);
      node = node.leftChild;
    } else {
      node = stack.pop();
      if (count == x) {
        return node.value;
      }
      count++;
      node = node.rightChild;
    }
  }
  return null;
}

Рекурсивная версия требует передачи изменяемой оболочки для счетчика следующим образом:

public class Counter {
   int count = 0;
}

public void inOrderTraverseTree(Node root, int index, Counter counter){
  if(root == null || counter.count > index) {
    return;
  }
  inOrderTraverseTree(root.leftChild);
  if (counter.count == index) {
    System.out.println(root);
  }
  counter.count = counter.count + 1;
  inOrderTraverseTree(root.rightChild); 
}

Answer 4

Ниже приводится рекурсивный подход к обходу по порядку: (в C++)

bool valueAtPositionUtil(struct treeNode *root, int &currIndex, int i, int &value) {
    if(root != NULL) {
        if(valueAtPositionUtil(root->left, currIndex, i, value)) {
            return true;
        }
        if(currIndex == i) {
            value = root->data;
            return true;
        }
        currIndex++;
        if(valueAtPositionUtil(root->right, currIndex, i, value)) {
            return true;
        }
    }
    return false;
}

int ValueAtPosition(int i, struct treeNode *root) {
    int value = 0;
    int currIndex = 0;
    if(valueAtPositionUtil(root, currIndex, i, value)) {
        return value;
    }
    //index out of bound
    // you can return according your problem
    return -1; 
}