建立二叉树用非递归判断栈空的方法实现先序,中序,后序遍历
时间: 2023-07-21 14:38:08 浏览: 45
首先,我们需要定义一个二叉树结构体和一个栈结构体,代码如下:
```c++
#include <iostream>
using namespace std;
#define MAXSIZE 100
// 二叉树节点结构体
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 栈结构体
typedef struct Stack {
TreeNode *data[MAXSIZE];
int top;
} Stack;
```
接下来,我们可以实现先序、中序和后序遍历。以先序遍历为例:
```c++
// 非递归先序遍历
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
Stack s;
s.top = -1;
s.data[++s.top] = root;
while (s.top > -1) {
TreeNode *cur = s.data[s.top--];
cout << cur->val << " ";
if (cur->right != NULL) {
s.data[++s.top] = cur->right;
}
if (cur->left != NULL) {
s.data[++s.top] = cur->left;
}
}
}
```
在先序遍历中,我们首先将根节点入栈,然后不断弹出栈顶节点,输出其值,并将其右子节点和左子节点分别入栈,直到栈为空。
中序遍历和后序遍历的实现方法类似,只需要稍微调整一下入栈顺序即可。具体代码实现可以参考下面的完整代码:
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)