二叉树的先序,中序,后序遍历 非递归
时间: 2023-09-27 14:10:23 浏览: 63
可以使用栈来实现二叉树的先序、中序和后序遍历非递归算法。具体实现方法如下:
1. 先序遍历非递归算法:
先访问根节点,再访问左子树和右子树。具体实现如下:
(1) 创建一个空栈,将根节点压入栈中;
(2) 循环执行下列步骤,直到栈为空:
a. 弹出栈顶元素,访问它;
b. 如果有右孩子,将右孩子压入栈中;
c. 如果有左孩子,将左孩子压入栈中。
2. 中序遍历非递归算法:
先访问左子树,再访问根节点和右子树。具体实现如下:
(1) 创建一个空栈,将根节点压入栈中;
(2) 循环执行下列步骤,直到栈为空:
a. 如果栈顶元素存在左孩子,将左孩子压入栈中;
b. 否则,弹出栈顶元素,访问它;
c. 如果栈顶元素存在右孩子,将右孩子压入栈中。
3. 后序遍历非递归算法:
先访问左子树和右子树,再访问根节点。具体实现如下:
(1) 创建两个栈:s1和s2,将根节点压入s1中;
(2) 循环执行下列步骤,直到s1为空:
a. 弹出s1栈顶元素,将它压入s2中;
b. 如果s1栈顶元素存在左孩子,将左孩子压入s1中;
c. 如果s1栈顶元素存在右孩子,将右孩子压入s1中。
(3) 循环执行下列步骤,直到s2为空:
a. 弹出s2栈顶元素,访问它。
希望以上算法实现对你有所帮助!
相关问题
建立二叉树,先序中序后序遍历
二叉树是一种树形结构,每个节点最多有两个子节点。建立二叉树的过程可以通过前序遍历和中序遍历序列来实现。具体步骤如下:
1. 从前序遍历序列中取出第一个元素作为根节点。
2. 在中序遍历序列中找到根节点的位置,将中序遍历序列分为左子树和右子树两部分。
3. 根据左子树和右子树的元素个数,在前序遍历序列中分别找到左子树和右子树的元素,递归地建立左子树和右子树。
4. 输出二叉树的先序遍历序列,即根节点->左子树->右子树。
5. 输出二叉树的中序遍历序列,即左子树->根节点->右子树。
6. 输出二叉树的后序遍历序列,即左子树->右子树->根节点。
7. 统计二叉树的叶子节点数,即没有子节点的节点数。
除了递归算法,还可以使用非递归算法实现二叉树的遍历。具体实现方法可以参考引用中的内容。
二叉树先序、中序、后序遍历算法
二叉树的遍历有三种方式:先序遍历、中序遍历和后序遍历。
先序遍历:先遍历根节点,然后遍历左子树,最后遍历右子树。
中序遍历:先遍历左子树,然后遍历根节点,最后遍历右子树。
后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。
对于一个二叉树的遍历,可以采用递归的方式或者非递归的方式实现。
下面是三种遍历方式的递归实现代码:
先序遍历:
```
void preOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
cout << root->val << " "; //访问节点
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
```
中序遍历:
```
void inOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
inOrderTraversal(root->left);
cout << root->val << " "; //访问节点
inOrderTraversal(root->right);
}
```
后序遍历:
```
void postOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->val << " "; //访问节点
}
```
其中,TreeNode 表示二叉树的节点结构体,val 表示节点的值。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.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)