后序遍历二叉树YTU
时间: 2023-12-01 16:39:49 浏览: 39
很抱歉,根据提供的引用内容,没有直接回答您的问题。但是,我可以为您介绍一下后序遍历二叉树的方法。
后序遍历二叉树是指先遍历左子树,再遍历右子树,最后遍历根节点。具体实现可以使用递归或者栈来实现。
递归实现后序遍历二叉树的方法如下:
1. 如果当前节点为空,则返回。
2. 递归遍历左子树。
3. 递归遍历右子树。
4. 访问当前节点。
栈实现后序遍历二叉树的方法如下:
1. 将根节点入栈。
2. 初始化一个空栈。
3. 当栈不为空时,取出栈顶元素,将其压入空栈中。
4. 如果当前节点有左子树,则将左子树入栈。
5. 如果当前节点有右子树,则将右子树入栈。
6. 重复步骤3-5,直到栈为空。
7. 依次弹出空栈中的元素,即为后序遍历的结果。
相关问题
后序遍历二叉树的c语言代码
下面是后序遍历二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = createTree();
node->right = createTree();
return node;
}
// 后序遍历二叉树
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
int main() {
TreeNode* root = createTree();
postorderTraversal(root);
return 0;
}
```
输入格式为先序遍历的结果,其中 `-1` 表示空节点。输出为后序遍历的结果。
后序遍历二叉树非递归
下面是后序遍历二叉树的非递归算法,使用了栈来实现:
1. 定义一个栈stack和一个指针p,初始时p指向根节点。
2. 将p入栈,并将p指向其左子节点,重复此步骤直到p为空。
3. 取出栈顶元素,如果其右子节点存在且未被访问过,则将p指向其右子节点,并将该节点入栈,重复步骤2直到p为空。
4. 如果栈顶元素的右子节点不存在或已被访问过,则访问该节点,并将其出栈。
5. 重复步骤3和4直到栈为空。
下面是C++代码实现:
```cpp
void postorderTraversal(TreeNode* root) {
if (!root) {
return;
}
stack<TreeNode*> s;
TreeNode* p = root;
TreeNode* lastVisited = nullptr;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
TreeNode* topNode = s.top();
if (topNode->right && topNode->right != lastVisited) {
p = topNode->right;
} else {
cout << topNode->val << " ";
s.pop();
lastVisited = topNode;
}
}
}
```
相关推荐
![](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)