二叉树递归遍历cpp
时间: 2024-05-21 22:09:26 浏览: 14
二叉树递归遍历主要有三种方式:前序遍历、中序遍历和后序遍历。
具体实现方式如下:
1.前序遍历(根节点->左子树->右子树):
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
2.中序遍历(左子树->根节点->右子树):
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
3.后序遍历(左子树->右子树->根节点):
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
相关问题
二叉树的遍历c++递归
以下是C++递归实现二叉树的先序、中序和后序遍历的代码:
先序遍历:
```cpp
void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 先访问根节点
visit(root);
// 再递归遍历左子树
preorderTraversal(root->left);
// 最后递归遍历右子树
preorderTraversal(root->right);
}
```
中序遍历:
```cpp
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 先递归遍历左子树
inorderTraversal(root->left);
// 再访问根节点
visit(root);
// 最后递归遍历右子树
inorderTraversal(root->right);
}
```
后序遍历:
```cpp
void postorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
// 先递归遍历左子树
postorderTraversal(root->left);
// 再递归遍历右子树
postorderTraversal(root->right);
// 最后访问根节点
visit(root);
}
```
其中,`visit`函数表示访问节点的操作,可以根据具体情况进行定义。
二叉树非递归遍历实现完整代码
二叉树的非递归遍历可以使用栈来实现。以下是二叉树的非递归前序、中序和后序遍历的完整代码实现:
```cpp
#include <iostream>
#include <stack>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
cout << node->val << " ";
if (node->right) st.push(node->right);
if (node->left) st.push(node->left);
}
}
// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
while (node != NULL || !st.empty()) {
while (node != NULL) {
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
cout << node->val << " ";
node = node->right;
}
}
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* node = root;
TreeNode* lastVisited = NULL;
while (node != NULL || !st.empty()) {
while (node != NULL) {
st.push(node);
node = node->left;
}
TreeNode* topNode = st.top();
if (topNode->right == NULL || topNode->right == lastVisited) {
cout << topNode->val << " ";
st.pop();
lastVisited = topNode;
} else {
node = topNode->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);
// 非递归前序遍历
cout << "Preorder traversal: ";
preorderTraversal(root);
cout << endl;
// 非递归中序遍历
cout << "Inorder traversal: ";
inorderTraversal(root);
cout << endl;
// 非递归后序遍历
cout << "Postorder traversal: ";
postorderTraversal(root);
cout << endl;
return 0;
}
```