二叉树实现前序、中序、后序、层次遍历的算法思想
时间: 2023-08-05 08:07:50 浏览: 49
二叉树的遍历方式有四种:前序遍历、中序遍历、后序遍历和层次遍历。下面分别介绍这四种遍历方式的算法思想和实现方法:
1. 前序遍历
前序遍历的算法思想是先访问根节点,然后按照左子树、右子树的顺序递归遍历每个子树。具体实现过程可以采用递归方式或者利用栈来实现迭代遍历。
递归方式实现前序遍历:
```
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
cout << root->val << " "; //访问根节点
preOrderTraversal(root->left); //递归遍历左子树
preOrderTraversal(root->right); //递归遍历右子树
}
}
```
利用栈实现前序遍历:
```
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 != NULL) st.push(node->right); //右子树入栈
if (node->left != NULL) st.push(node->left); //左子树入栈
}
}
```
2. 中序遍历
中序遍历的算法思想是先递归遍历左子树,然后访问根节点,最后递归遍历右子树。具体实现过程可以采用递归方式或者利用栈来实现迭代遍历。
递归方式实现中序遍历:
```
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left); //递归遍历左子树
cout << root->val << " "; //访问根节点
inOrderTraversal(root->right); //递归遍历右子树
}
}
```
利用栈实现中序遍历:
```
void inOrderTraversal(TreeNode* root) {
if (root == NULL) return;
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;
}
}
```
3. 后序遍历
后序遍历的算法思想是先递归遍历左子树,然后递归遍历右子树,最后访问根节点。具体实现过程可以采用递归方式或者利用栈来实现迭代遍历。
递归方式实现后序遍历:
```
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left); //递归遍历左子树
postOrderTraversal(root->right); //递归遍历右子树
cout << root->val << " "; //访问根节点
}
}
```
利用栈实现后序遍历:
```
void postOrderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> st;
TreeNode* node = root;
TreeNode* lastVisit = NULL;
while (node != NULL || !st.empty()) {
while (node != NULL) {
st.push(node);
node = node->left;
}
node = st.top();
if (node->right == NULL || node->right == lastVisit) {
st.pop();
cout << node->val << " "; //访问当前节点
lastVisit = node;
node = NULL;
} else {
node = node->right;
}
}
}
```
4. 层次遍历
层次遍历的算法思想是按照从上到下、从左到右的顺序依次访问每个节点。具体实现过程可以采用队列来实现。
```
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); //右子树入队
}
}
}
```
以上是二叉树实现前序、中序、后序、层次遍历的算法思想和实现方法。其中,递归方式实现简单易懂,但可能会导致递归调用栈溢出的问题;利用栈或队列实现的迭代遍历方式更加稳定,但需要额外的空间来存储栈或队列。