Структуры данных на основе деревьев

Прямой (pre-order) обход бинарного дерева:

• Обработать узел
• Обойти левое поддерево
• Обойти правое поддерево

void preorder(Node* n)
{ if(!n) return;
  print(n->value);
  preorder(n->left);
  preorder(n->right);
}

(+ (* 3 (- 7 4)) 6) // используется в функциональных языках (Scheme)

Симметричный (in-order) обход бинарного дерева:

• Обойти левое поддерево
• Обработать узел
• Обойти правое поддерево

void inorder(Node* n)
{ if(!n) return;
  inorder(n->left);
  print(n->value);
  inorder(n->right);
}

((3 * (7 - 4)) + 6)

Обратный (post-order) обход бинарного дерева:

• Обойти левое поддерево
• Обойти правое поддерево
• Обработать узел

void postorder(Node* n)
{ if(!n) return;
  postorder(n->left);
  postorder(n->right);
  print(n->value);
}

((3 (7 4 -) *) 6 +)
3 7 4 - * 6 + // обратная польская (бесскобочная) запись, используется в языке Forth и некоторых калькуляторах