c++输出二叉树先序遍历序列
时间: 2023-06-23 16:54:21 浏览: 100
假设二叉树的节点结构体为:
```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++输出其层次序遍历序列
可以使用递归的方式构建二叉树,并利用队列实现层次遍历。以下是示例代码:
```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) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
int rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
int leftSize = rootIndex - inStart;
TreeNode* root = new TreeNode(rootVal);
root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
return root;
}
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* curr = q.front();
q.pop();
cout << curr->val << " ";
if (curr->left != NULL) {
q.push(curr->left);
}
if (curr->right != NULL) {
q.push(curr->right);
}
}
}
}
int main() {
vector<int> preorder = { 3, 9, 20, 15, 7 };
vector<int> inorder = { 9, 3, 15, 20, 7 };
TreeNode* root = buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
levelOrder(root); // 输出 3 9 20 15 7
return 0;
}
```
用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`。
阅读全文