C语言实现非递归后序遍历核心代码

非递归后序遍历的核心代码如下:

void postorder_traversal(Node* root) {
  if (root == NULL) return;

  // 创建一个栈用于存储遍历过程中的结点
  stack<Node*> stk;

  // 创建两个指针: curr 和 pre
  Node* curr = root;
  Node* pre = NULL;

  // 将根结点压入栈中
  stk.push(root);

  while (!stk.empty()) {
    // 将当前结点赋值给 curr
    curr = stk.top();

    // 如果当前结点没有子结点或者已经访问过了,就可以访问当前结点
    if ((curr->left == NULL && curr->right == NULL) ||
        (pre != NULL && (pre == curr->left || pre == curr->right))) {
      // 访问当前结点
      printf("%d ", curr->val);
      // 将当前结点从栈中弹出
      stk.pop();
      // 将当前结点赋值给 pre
      pre = curr;
    } else {
      // 如果当前结点有右子结点,就将右子结点压入栈中
      if (curr->right != NULL) stk.push(curr->right);
      // 如果当前结点有左子结点,就将左子结点压入栈中
      if (curr->left != NULL) stk.push(curr->left);
    }
  }
}

上述代码实现了对二叉树的非递归后序遍历。在遍历过程中,使用了一个栈来辅助实现非递归遍历。

需要注意的是,在代码中需要判断当前结点是否有子结点以及当前结点的子结点是否已经访问