обход по порядку в BST

Question

как отследить предыдущий узел при рекурсивном обходе дерева двоичного поиска?

eq ... при поиске пола любого нет ... в bst ... iam попыткинайти первое число в bst, которое больше заданного значения ... и в этот момент вывести данные узла prev, которые равны или меньше заданного значения, так как это обход по порядку ...

так почему вопрос в том, как мы можем отслеживать предыдущий узел в bst при рекурсивном обходе по порядку ??

Answer 1

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

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

В вашем случае, вероятно, лучше всего делать последнее. например:

Node* floor_node(int x, Node *subtree) {
  if (subtree) {
    if(subtree->value > x) {
      return floor_node(x, subtree->left);
    } else {
      return floor_node(x, subtree->right) || subtree;
    }
  } else {
      return subtree;
  }
}

Answer 2

Бинарное дерево рекурсии работает, спускаясь вниз по левому дереву, а затем направо. Inorder / preorder / postorder - это соглашение, которое определяется просто упорядочением некоторого локального действия в рекурсивной процедуре: временем «посещения» самого текущего узла в отношении двух рекурсивных вызовов.

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

Когда вы вернетесь в дерево, последний узел, посещенный в "inorder", будет просто самым правым узлом! Следовательно, ваша рекурсия должна просто вернуть самый правый узел.

Кроме того, если дерево T в целом имеет некоторый предыдущий узел P, то левое поддерево T, а именно левое (T), также имеет тот же предыдущий узел P. P является предшественником самого левого узла T.

Более того, предыдущий узел по правому краю (T) является самим узлом T.

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

псевдокод:

# a recursive function that is given its previous node,
# and returns the rightmost node

recurse_with_previous (tree previous-in):
   # skip empty link. No leaf to see here!
   # previous-in is the rightmost node still
   if null(tree)
      return previous-in

   # if we are at a leaf, then that leaf is rightmost
   if leaf(tree)
      print "visiting leaf node " tree " with previous node " previous-in
      return tree

   # the previous node (previous-in) of this tree is actually the left
   # subtrees previous node, so we just pass that parameter down
   previous = recurse_with_previous (left(tree) previous-in)

   # inorder visit: visit this node between the subtrees
   print "visiting " tree " with previous node " previous

   # now the right subtree. what is ITS previous? Why, we are!!!
   # we return whatever this returns causing the return value
   # to be the rightmost node.
   return recurse_with_previous (right(tree) tree)

 # how to call
 recurse_with_previous(some-tree nil)