二叉树的遍历程序
时间: 2023-09-21 08:07:44 浏览: 26
二叉树的遍历有三种:前序遍历、中序遍历和后序遍历。下面分别介绍三种遍历方式的程序实现。
1. 前序遍历
前序遍历的顺序是先遍历根节点,然后是左子树,最后是右子树。
递归实现:
```
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* node = s.top();
s.pop();
cout << node->val << " ";
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
}
```
2. 中序遍历
中序遍历的顺序是先遍历左子树,然后是根节点,最后是右子树。
递归实现:
```
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* node = root;
while (!s.empty() || node) {
if (node) {
s.push(node);
node = node->left;
} else {
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right;
}
}
}
```
3. 后序遍历
后序遍历的顺序是先遍历左子树,然后是右子树,最后是根节点。
递归实现:
```
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;
TreeNode* node = root;
TreeNode* lastVisited = nullptr;
while (!s.empty() || node) {
if (node) {
s.push(node);
node = node->left;
} else {
TreeNode* peekNode = s.top();
if (peekNode->right && peekNode->right != lastVisited) {
node = peekNode->right;
} else {
cout << peekNode->val << " ";
lastVisited = peekNode;
s.pop();
}
}
}
}
```
相关推荐
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)