如何实现二叉树的前序遍历、中序遍历和后序遍历?
时间: 2024-06-17 17:07:42 浏览: 14
二叉树的前序遍历、中序遍历和后序遍历是三种基本的遍历方式,具体实现方法如下:
1. 前序遍历:先访问根节点,再访问左子树,最后访问右子树。具体实现可以使用递归或者栈来实现。
递归实现:
```
void preorder(TreeNode* root) {
if (root == nullptr) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
```
栈实现:
```
void preorder(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
cout << cur->val << " ";
if (cur->right) s.push(cur->right);
if (cur->left) s.push(cur->left);
}
}
```
2. 中序遍历:先访问左子树,再访问根节点,最后访问右子树。具体实现可以使用递归或者栈来实现。
递归实现:
```
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
```
栈实现:
```
void inorder(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != nullptr || !s.empty()) {
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
```
3. 后序遍历:先访问左子树,再访问右子树,最后访问根节点。具体实现可以使用递归或者栈来实现。
递归实现:
```
void postorder(TreeNode* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
```
栈实现:
```
void postorder(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* cur = s1.top();
s1.pop();
s2.push(cur);
if (cur->left) s1.push(cur->left);
if (cur->right) s1.push(cur->right);
}
while (!s2.empty()) {
TreeNode* cur = s2.top();
s2.pop();
cout << cur->val << " ";
}
}
```