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

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 

---

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