c++输出二叉树先序遍历序列
时间: 2023-06-23 07:54:21 浏览: 45
假设二叉树的节点结构体为:
```cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
则输出二叉树的先序遍历序列的代码如下:
```cpp
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
```
其中,先输出当前节点的值,然后递归输出左子树和右子树。
相关问题
用c++输出利用先序遍历创建的二叉树的层次遍历序列
要输出利用先序遍历创建的二叉树的层次遍历序列,可以使用队列实现。具体的实现步骤如下:
1. 创建一个队列,将根节点入队。
2. 循环执行以下操作,直到队列为空:
a. 取出队头元素,输出该元素的值。
b. 如果该元素有左子树,则将左子树入队。
c. 如果该元素有右子树,则将右子树入队。
下面是使用 C++ 实现的代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct Node {
char data;
Node* left;
Node* right;
};
// 根据先序遍历序列建立二叉树
Node* createTree() {
char c;
cin >> c;
if (c == '#') {
return NULL;
}
Node* root = new Node;
root->data = c;
root->left = createTree();
root->right = createTree();
return root;
}
// 层次遍历二叉树
void levelOrder(Node* root) {
if (root == NULL) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* p = q.front();
q.pop();
cout << p->data << " ";
if (p->left != NULL) {
q.push(p->left);
}
if (p->right != NULL) {
q.push(p->right);
}
}
}
int main() {
Node* root = createTree();
levelOrder(root);
return 0;
}
```
这个程序可以读入一个先序遍历序列表示的二叉树,并输出该二叉树的层次遍历序列。例如,如果输入序列是 `AB##C##`,则输出序列为 `A B C`。
C++根据二叉树的先序遍历序列和中序遍历序列,求其后序遍历序列
我们可以利用递归的思想来解决这个问题。一个二叉树的先序遍历序列的第一个元素一定是根节点,而在中序遍历序列中,根节点的左侧都是左子树的节点,右侧都是右子树的节点。因此,我们可以根据这个性质来构建二叉树,并且递归地处理左右子树。
具体的实现步骤如下:
1. 根据先序遍历序列的第一个元素创建根节点。
2. 在中序遍历序列中找到根节点的位置,将序列分成左右两部分。
3. 递归地处理左子树,将左子树的先序遍历序列和中序遍历序列作为参数传入。
4. 递归地处理右子树,将右子树的先序遍历序列和中序遍历序列作为参数传入。
5. 将根节点的值加入到后序遍历序列中。
6. 返回后序遍历序列。
下面是 C++ 的代码实现:
```cpp
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<int> buildTree(vector<int>& preorder, vector<int>& inorder) {
// 将中序遍历序列的每个元素及其下标存储到哈希表中
for (int i = 0; i < inorder.size(); i++) {
index[inorder[i]] = i;
}
return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
private:
unordered_map<int, int> index;
// 根据先序遍历序列和中序遍历序列构建二叉树,并返回后序遍历序列
vector<int> buildTree(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd) {
if (preStart > preEnd) {
return {};
}
// 先序遍历序列的第一个元素是根节点
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历序列中找到根节点的位置
int rootIndex = index[rootVal];
// 计算左子树的长度
int leftSize = rootIndex - inStart;
// 递归处理左子树
vector<int> left = buildTree(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1);
// 递归处理右子树
vector<int> right = buildTree(preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd);
// 将根节点的值加入到后序遍历序列中
vector<int> res = left;
res.insert(res.end(), right.begin(), right.end());
res.push_back(rootVal);
return res;
}
};
```
时间复杂度为 O(n),其中 n 是二叉树中的节点个数。这是因为我们需要遍历每个节点恰好一次。空间复杂度为 O(n),其中 n 是二叉树中的节点个数。除了存储答案所需的空间,我们还需要 O(n) 的空间存储哈希表。