用非递归实现二叉树的前序、中序、后序遍历算法。
时间: 2023-07-10 18:04:48 浏览: 35
非递归实现二叉树的遍历算法需要借助栈结构完成,以下是具体实现方法:
前序遍历:
1. 创建一个栈,并将根节点压入栈中。
2. 当栈不为空时,弹出栈顶元素,并输出该元素的值。
3. 如果该元素有右子树,则将右子树压入栈中。
4. 如果该元素有左子树,则将左子树压入栈中。
5. 重复步骤2-4,直到栈为空。
中序遍历:
1. 创建一个栈,并将根节点压入栈中。
2. 如果当前节点不为空,则将该节点压入栈中,并将当前节点指向其左子树。
3. 如果当前节点为空,则弹出栈顶元素,并输出该元素的值,然后将当前节点指向该元素的右子树。
4. 重复步骤2-3,直到栈为空。
后序遍历:
1. 创建一个栈,并将根节点压入栈中。
2. 创建一个辅助栈。
3. 当栈不为空时,弹出栈顶元素,并将其压入辅助栈中。
4. 如果该元素有左子树,则将左子树压入栈中。
5. 如果该元素有右子树,则将右子树压入栈中。
6. 重复步骤3-5,直到栈为空。
7. 依次输出辅助栈中的元素值。
具体实现可以参考以下代码(以前序遍历为例):
```
void preorderTraversal(TreeNode* root) {
if (!root) return;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
cout << node->val << " ";
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
}
```