树遍历中，preorder 以以下顺序访问节点：当前节点，其所有左子节点（preorder 排序），其所有右子节点（preorder 排序）。在 C 语言中，preorder 可用递归或迭代实现：1. 递归：当前节点、左子节点（preorder）、右子节点（preorder）；2. 迭代：使用栈，当前节点、右子节点入栈、左子节点入栈、弹出当前节点并访问、重复步骤 2-4。

什么是 preorder

在计算机科学中，preorder 是树遍历的一种方法，它根据以下顺序访问树中的节点：

• 当前节点
• 当前节点的所有左子节点（以 preorder 排序）
• 当前节点的所有右子节点（以 preorder 排序）

preorder 在 C 语言中

在 C 语言中，preorder 遍历可以用递归或迭代实现。

立即学习“C语言免费学习笔记（深入）”；

递归实现

<code class="c">void preorder(struct node *root) {
  if (root != NULL) {
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
  }
}</code>

迭代实现

使用一个栈来实现 preorder 遍历：

<code class="c">void preorder(struct node *root) {
  stack<struct node *> s;
  s.push(root);

  while (!s.empty()) {
    struct node *curr = s.top();
    s.pop();

    printf("%d ", curr->data);

    if (curr->right != NULL) {
      s.push(curr->right);
    }

    if (curr->left != NULL) {
      s.push(curr->left);
    }
  }
}</code>