c++实现二叉树的遍历
时间: 2024-01-02 07:03:43 浏览: 30
以下是C++中二叉树前序、中序、后序遍历的递归和非递归实现,以及层序遍历和深度优先遍历的代码和讲解:
1.1 前序遍历(Preorder Traversal)- 递归实现
```c++
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " "; // 输出节点值
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
```
1.2 前序遍历(Preorder Traversal)- 非递归实现
```c++
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
while (!.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " "; // 输出节点值
if (node->right != NULL) {
s.push(node->right); // 先将右子树入栈
}
if (node->left != NULL) {
s.push(node->left); // 再将左子树入栈
}
}
}
```
2.1 中序遍历(Inorder Traversal)- 递归实现
```c++
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left); // 遍历左子树
cout << root->val << " "; // 输出节点值
inorderTraversal(root->right); // 遍历右子树
}
```
2.2 中序遍历(Inorder Traversal)- 非递归实现
```c++
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
TreeNode* node = root;
while (node != NULL || !s.empty()) {
while (node != NULL) {
s.push(node);
node = node->left; // 将左子树入栈
}
node = s.top();
s.pop();
cout << node->val << " "; // 输出节点值
node = node->right; // 遍历右子树
}
}
```
3.1 后序遍历(Postorder Traversal)- 递归实现
```c++
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
cout << root->val << " "; // 输出节点值
}
```
3.2 后序遍历(Postorder Traversal)- 非递归实现
```c++
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node);
if (node->left != NULL) {
s1.push(node->left); // 先将左子树入栈
}
if (node->right != NULL) {
s1.push(node->right); // 再将右子树入栈
}
}
while (!s2.empty()) {
TreeNode* node = s2.top();
s2.pop();
cout << node->val << " "; // 输出节点值
}
}
```
4.1 层序遍历(Level Order Traversal)
```c++
void levelOrderTraversal(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* node = q.front();
q.pop();
cout << node->val << " "; // 输出节点值
if (node->left != NULL) {
q.push(node->left); // 将左子树入队
}
if (node->right != NULL) {
q.push(node->right); // 将右子树入队
}
}
}
}
```
5.1 深度优先遍历(Depth First Traversal)
```c++
void dfs(TreeNode* root) {
if (root == NULL) {
return;
}
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " "; // 输出节点值
if (node->right != NULL) {
s.push(node->right); // 先将右子树入栈
}
if (node->left != NULL) {
s.push(node->left); // 再将左子树入栈
}
}
}
```