树的后序遍历的非递归思路c语言
时间: 2023-05-10 12:56:14 浏览: 76
可以使用栈来实现树的后序遍历的非递归思路。具体实现如下:
1. 定义一个栈和一个指针p,初始时p指向根节点,将p入栈。
2. 如果栈不为空,则取出栈顶元素,如果该元素没有右子树或者右子树已经被访问过了,则访问该元素并将p指向NULL。
3. 如果该元素有右子树且右子树没有被访问过,则将p指向右子树并将p入栈。
4. 如果该元素有左子树且左子树没有被访问过,则将p指向左子树并将p入栈。
5. 重复步骤2-4,直到栈为空。
下面是具体的C语言代码实现:
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
TreeNode* p = root;
TreeNode* lastVisited = NULL;
while (!s.empty() || p != NULL) {
if (p != NULL) {
s.push(p);
p = p->left;
} else {
TreeNode* topNode = s.top();
if (topNode->right != NULL && topNode->right != lastVisited) {
p = topNode->right;
} else {
printf("%d ", topNode->val);
lastVisited = topNode;
s.pop();
}
}
}
}
阅读全文