c++层次次序输入二叉树,输出先序,中序,后序遍历结果
时间: 2023-07-21 20:02:55 浏览: 47
假设二叉树的节点结构体为:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
我们可以使用递归的方式实现先序、中序、后序遍历。具体实现如下:
```c++
void preOrder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode* root) {
if (!root) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
```
其中,先序遍历先访问根节点,然后访问左子树、右子树;中序遍历先访问左子树,然后访问根节点、右子树;后序遍历先访问左子树,然后访问右子树、根节点。
对于按照层次序列输入的二叉树,我们可以使用队列来实现。具体实现如下:
```c++
TreeNode* buildTree(vector<int>& nums) {
if (nums.empty()) return nullptr;
TreeNode* root = new TreeNode(nums[0]);
queue<TreeNode*> q{{root}};
int i = 1;
while (!q.empty() && i < nums.size()) {
TreeNode* curr = q.front(); q.pop();
if (i < nums.size() && nums[i] != -1) {
curr->left = new TreeNode(nums[i]);
q.push(curr->left);
}
i++;
if (i < nums.size() && nums[i] != -1) {
curr->right = new TreeNode(nums[i]);
q.push(curr->right);
}
i++;
}
return root;
}
```
其中,-1 表示节点为空。使用一个队列来存储每层的节点,对于每个节点,如果其左(右)子节点存在,则在队列中插入该节点的左(右)子节点。最后返回根节点即可。
完整代码如下:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& nums) {
if (nums.empty()) return nullptr;
TreeNode* root = new TreeNode(nums[0]);
queue<TreeNode*> q{{root}};
int i = 1;
while (!q.empty() && i < nums.size()) {
TreeNode* curr = q.front(); q.pop();
if (i < nums.size() && nums[i] != -1) {
curr->left = new TreeNode(nums[i]);
q.push(curr->left);
}
i++;
if (i < nums.size() && nums[i] != -1) {
curr->right = new TreeNode(nums[i]);
q.push(curr->right);
}
i++;
}
return root;
}
void preOrder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode* root) {
if (!root) return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
void postOrder(TreeNode* root) {
if (!root) return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
vector<int> nums{1, 2, 3, -1, 4, 5, 6};
TreeNode* root = buildTree(nums);
cout << "preOrder: ";
preOrder(root);
cout << endl;
cout << "inOrder: ";
inOrder(root);
cout << endl;
cout << "postOrder: ";
postOrder(root);
cout << endl;
return 0;
}
```