假设二叉树采用二叉链存储结构,设计二叉树的先序遍历、中序遍历、后序通历和层次遍历算法;并用相关数据进行测试。
时间: 2023-12-18 12:05:49 浏览: 47
以下是四种遍历算法的实现(C++代码):
```c++
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历
void preorder(TreeNode* root) {
if (root != NULL) {
cout << root->val << " "; // 访问根节点
preorder(root->left); // 遍历左子树
preorder(root->right); // 遍历右子树
}
}
// 中序遍历
void inorder(TreeNode* root) {
if (root != NULL) {
inorder(root->left); // 遍历左子树
cout << root->val << " "; // 访问根节点
inorder(root->right); // 遍历右子树
}
}
// 后序遍历
void postorder(TreeNode* root) {
if (root != NULL) {
postorder(root->left); // 遍历左子树
postorder(root->right); // 遍历右子树
cout << root->val << " "; // 访问根节点
}
}
// 层次遍历
void levelorder(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front();
q.pop();
if (cur != NULL) {
cout << cur->val << " ";
q.push(cur->left);
q.push(cur->right);
}
}
}
int main() {
// 构建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 测试四种遍历算法
cout << "先序遍历:";
preorder(root);
cout << endl;
cout << "中序遍历:";
inorder(root);
cout << endl;
cout << "后序遍历:";
postorder(root);
cout << endl;
cout << "层次遍历:";
levelorder(root);
cout << endl;
return 0;
}
```
测试结果如下:
```
先序遍历:1 2 4 5 3 6 7
中序遍历:4 2 5 1 6 3 7
后序遍历:4 5 2 6 7 3 1
层次遍历:1 2 3 4 5 6 7
```
相关推荐
![](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)