C++前序遍历二叉树并打印
时间: 2024-06-19 15:04:07 浏览: 11
C++前序遍历二叉树并打印的代码如下所示:
```c++
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){} //构造函数
};
void preorderTraversal(TreeNode* root){
if(root == nullptr){
return;
}
cout << root->val << " "; //先打印根节点的值
preorderTraversal(root->left); //递归遍历左子树
preorderTraversal(root->right); //递归遍历右子树
}
```
这里假设二叉树的节点定义为`TreeNode`,有一个整型成员变量`val`表示节点的值,一个指向左子节点的指针`left`和一个指向右子节点的指针`right`。`preorderTraversal`函数是前序遍历二叉树并打印的函数,它接收一个指向二叉树根节点的指针`root`作为参数。
相关问题
C++非递归前序遍历二叉树并打印
C++非递归前序遍历二叉树的代码如下:
```cpp
#include <iostream>
#include <stack>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void preorderTraversal(TreeNode* root) {
if (!root) {
return;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ";
if (node->right) {
s.push(node->right);
}
if (node->left) {
s.push(node->left);
}
}
}
int main() {
// Create a binary tree
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);
// Non-recursive preorder traversal
cout << "Non-recursive preorder traversal: ";
preorderTraversal(root);
cout << endl;
return 0;
}
```
非递归前序遍历二叉树的思路是使用栈来模拟递归过程。我们首先把根节点入栈,然后在循环中不断取出栈顶元素,输出它的值,并依次把其右子节点和左子节点入栈。由于栈是后进先出的数据结构,所以先入栈右子节点再入栈左子节点可以保证左子节点先被访问。
C++用前序遍历创建二叉树
以下是C++用前序遍历创建二叉树的代码示例:
```cpp
#include <iostream>
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;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (root == NULL) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main() {
TreeNode* root = buildTree();
cout << "前序遍历结果为:";
preorder(root);
cout << endl;
cout << "中序遍历结果为:";
inorder(root);
cout << endl;
return 0;
}
```
输入格式为一串数字,其中-1表示空节点。例如,输入序列为1 2 -1 -1 3 4 -1 -1 5 -1 -1,则表示如下二叉树:
```
1
/ \
2 3
/ \
4 5
```
输出结果为:
```
前序遍历结果为:1 2 3 4 5
中序遍历结果为:2 1 4 3 5
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)