前序,中序,后序C语言非递归
时间: 2024-06-03 12:05:42 浏览: 13
前序、中序和后序遍历是树的三种常用遍历方式。在非递归的实现中,需要借助栈来模拟递归的过程,下面给出各种遍历方式的非递归实现代码。
前序遍历:
```c
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
printf("%d ", node->val); // 访问根节点
if (node->right != NULL) s.push(node->right); // 先压右子树
if (node->left != NULL) s.push(node->left); // 再压左子树
}
}
```
中序遍历:
```c
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
TreeNode* node = root;
while (!s.empty() || node != NULL) {
if (node != NULL) {
s.push(node);
node = node->left; // 左子树不断入栈
} else {
node = s.top();
s.pop();
printf("%d ", node->val); // 访问根节点
node = node->right; // 右子树入栈
}
}
}
```
后序遍历:
```c
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node); // 将节点压入s2中
if (node->left != NULL) s1.push(node->left);
if (node->right != NULL) s1.push(node->right);
}
while (!s2.empty()) {
TreeNode* node = s2.top();
s2.pop();
printf("%d ", node->val); // 访问节点
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)