分别用递归和非递归方式实现二叉树的先序、中序和后序遍历
时间: 2023-07-23 15:44:02 浏览: 61
好的,我来回答你的问题。
先序遍历:
- 递归实现:
```
void preOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
cout << root->val << " ";
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
```
- 非递归实现:
```
void preOrderTraversal(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);
}
}
```
中序遍历:
- 递归实现:
```
void inOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
inOrderTraversal(root->left);
cout << root->val << " ";
inOrderTraversal(root->right);
}
```
- 非递归实现:
```
void inOrderTraversal(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;
}
}
```
后序遍历:
- 递归实现:
```
void postOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
postOrderTraversal(root->left);
postOrderTraversal(root->right);
cout << root->val << " ";
}
```
- 非递归实现:
```
void postOrderTraversal(TreeNode* root) {
if(root == nullptr) return;
stack<TreeNode*> s;
s.push(root);
TreeNode* pre = nullptr;
while(!s.empty()) {
TreeNode* cur = s.top();
if((cur->left == nullptr && cur->right == nullptr) ||
(pre != nullptr && (pre == cur->left || pre == cur->right))) {
cout << cur->val << " ";
s.pop();
pre = cur;
} else {
if(cur->right != nullptr) s.push(cur->right);
if(cur->left != nullptr) s.push(cur->left);
}
}
}
```
以上就是递归和非递归方式实现二叉树的先序、中序和后序遍历的代码。
相关推荐
![](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)
![](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)