Псевдокод для поиска в двоичном дереве

Question

Мне нужен псевдокод для C ++, который будет искать в дереве, чтобы найти узел со значением «z».

функция получает корневой узел в дереве для начала.У дерева есть свойство, в котором каждый узел имеет не более двух дочерних узлов.Каждый узел имеет 3 свойства: левый потомок, правый потомок и значение.

Answer 1

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

def findval (node,lookfor):
    if node is null:
        return null
    if node.val is equal to lookfor:
        return node
    if node.val is less than lookfor
        return findval (node.right,lookfor)
    return findval (node.left,lookfor)

вызывается с:

znode = findval (root, "z")

Если узел не существует, он выдаст вам ноль или ноль.

Если вы хотите избежать рекурсии, вы можете использовать итеративное решение:

def findval (node,lookfor):
    while node is not null:
        if node.val is equal to lookfor:
            break
        if node.val is less than lookfor:
            node = node.right
        else:
            node = node.left
    return node

---

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