对任意给定的二叉树(顶点数自定)建立它的二叉链表存贮结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍历的结果。画出搜索顺序示意图。
时间: 2023-07-10 13:16:46 浏览: 88
抱歉,我是一个语言模型AI,并不能运行程序或画图。但我可以提供一些思路和代码片段供参考。
思路:
1. 定义二叉树节点的结构体,包含数据、左右子树指针。
2. 通过递归的方式建立二叉树的二叉链表存储结构。
3. 分别实现先序、中序、后序遍历。以先序遍历为例,其基本思路如下:
- 先访问根节点
- 递归遍历左子树
- 递归遍历右子树
4. 用栈来实现遍历过程中的节点存储和访问顺序。
- 先将根节点入栈。
- 每次取出栈顶元素,并访问它。
- 如果该节点有右子树,则将右子树入栈。
- 如果该节点有左子树,则将左子树入栈。
5. 对于中序遍历,入栈顺序需要稍作修改。
代码片段:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 递归建立二叉树
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) { // -1 代表该节点为空
return NULL;
}
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
// 先序遍历
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
cout << cur->val << " ";
if (cur->right) {
s.push(cur->right);
}
if (cur->left) {
s.push(cur->left);
}
}
}
// 中序遍历
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur || !s.empty()) {
if (cur) {
s.push(cur);
cur = cur->left;
} else {
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
}
// 后序遍历
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
TreeNode* pre = NULL;
while (!s.empty()) {
TreeNode* cur = s.top();
if ((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right))) {
cout << cur->val << " ";
s.pop();
pre = cur;
} else {
if (cur->right) {
s.push(cur->right);
}
if (cur->left) {
s.push(cur->left);
}
}
}
}
int main() {
TreeNode* root = buildTree();
preOrder(root);
cout << endl;
inOrder(root);
cout << endl;
postOrder(root);
return 0;
}
```
阅读全文
相关推荐
![-](https://img-home.csdnimg.cn/images/20241231045053.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![-](https://img-home.csdnimg.cn/images/20241231044833.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![pdf](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231044930.png)
![-](https://img-home.csdnimg.cn/images/20241231044947.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![-](https://img-home.csdnimg.cn/images/20241231044937.png)
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)