判断二叉树函数f()属于前序遍历还是后序遍历？

遍历规则理解 #

• 前序遍历：先访问根节点，再遍历左子树，最后遍历右子树
• 后序遍历：先遍历左子树，再遍历右子树，最后访问根节点

考题函数分析 #

期末考题要求判断以下C++函数f()采用的是前序遍历还是后序遍历：

template <typename T>
int f(treeNode* t)
{
   int n=0, leftValue, rightValue;
   if (t != NULL) {
      if (t->leftChild != NULL || t->rightChild != NULL)
         n++;
      leftValue = f(t->leftChild);
      rightValue = f(t->rightChild);
      return n + leftValue + rightValue;
   } else
      return 0;
}

这个函数的执行逻辑是：先对当前节点做了一次子节点存在性判断（有子节点则n加1），随后递归遍历左子树，再递归遍历右子树，最后才将当前节点的n值与左右子树的返回值合并后返回。

判断遍历类型的核心是当前节点核心处理动作的执行时机。这里函数的核心计算逻辑（将当前节点贡献与子树结果合并）是在左右子树都遍历完成后才执行的，完全符合后序遍历的特征。

对比节点删除函数clear #

这个逻辑和二叉树节点删除函数clear的遍历逻辑完全一致：

clear(Node* curr) {
   if (!curr)
      return;

   clear(curr->left);
   clear(curr->right);
   delete curr;
}

clear函数先递归处理左子树，再处理右子树，最后才执行当前节点的核心操作（删除节点），是典型的后序遍历实现。

结论：函数f()采用的是后序遍历。

内容的提问来源于stack exchange，提问作者Hofbr