非递归中序遍历二叉树:要求从键盘输入二叉树各结点的值,并使用二叉链表来存储二叉树;使用非递归算法遍历二叉树,在屏幕上打印出二叉树中序遍历序列。
时间: 2023-11-14 11:16:32 浏览: 103
非递归前序,中序,后序遍历二叉树(优化算法).rar_nooneyh_二叉树 非递归_前序 中序 后序_树遍历算法_遍历二叉树
好的,我可以为您解答这个问题。
首先,我们需要定义二叉树的结构体,包括节点的值,左右子树指针:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
然后,我们可以使用一个栈来模拟递归的过程,将根节点及其左子树的所有节点依次压入栈中,然后依次出栈进行遍历。
具体的算法流程如下:
1. 定义一个栈和一个指针cur,初始时cur指向根节点。
2. 当cur不为空或栈不为空时,进行循环:
* 如果cur不为空,则将cur入栈,并令cur指向其左子节点。
* 如果cur为空,则从栈中弹出一个节点,并将其值打印出来,然后令cur指向其右子节点。
3. 当栈为空且cur为空时,遍历结束。
下面是代码实现:
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != NULL || !s.empty()) {
if (cur != NULL) {
s.push(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
printf("%d ", cur->val);
cur = cur->right;
}
}
}
```
这样,我们就可以从键盘输入二叉树的各节点值,使用二叉链表来存储二叉树,并使用非递归算法遍历二叉树,输出中序遍历序列了。
阅读全文