二叉树的中序、前序、后序的递归、非递归遍历算法
时间: 2023-05-31 22:18:39 浏览: 80
### 回答1:
二叉树的中序、前序、后序遍历算法分为递归和非递归两种方法。
递归遍历算法:
1. 中序遍历:先遍历左子树,再访问根节点,最后遍历右子树。
2. 前序遍历:先访问根节点,再遍历左子树,最后遍历右子树。
3. 后序遍历:先遍历左子树,再遍历右子树,最后访问根节点。
非递归遍历算法:
1. 中序遍历:使用栈来模拟递归过程,先将根节点入栈,然后将左子树的所有节点入栈,直到遇到叶子节点,然后出栈并访问该节点,再将右子树的所有节点入栈,重复上述过程。
2. 前序遍历:使用栈来模拟递归过程,先将根节点入栈,然后出栈并访问该节点,再将右子树入栈,最后将左子树入栈,重复上述过程。
3. 后序遍历:使用栈来模拟递归过程,先将根节点入栈,然后将左子树的所有节点入栈,直到遇到叶子节点,然后将右子树的所有节点入栈,最后出栈并访问该节点,重复上述过程。需要使用一个辅助栈来记录已经访问过的节点。
### 回答2:
二叉树的中序、前序、后序遍历是树的三种基本遍历方法,他们都有递归和非递归两种算法。
1. 中序遍历
中序遍历是先访问左子树,再访问根节点,最后访问右子树。递归遍历可以先递归访问左子树,然后输出根节点,继续递归访问右子树。非递归遍历可以用栈进行模拟,从根节点开始,先访问左子树,遇到左子树都入栈,然后输出根节点,最后遍历右子树。
2. 前序遍历
前序遍历是先访问根节点,再访问左子树,最后访问右子树。递归遍历可以先输出根节点,然后递归访问左子树和右子树。非递归遍历可以用栈进行模拟,从根节点开始,先输出根节点,然后将右子树入栈,最后遍历左子树。
3. 后序遍历
后序遍历是先访问左子树,再访问右子树,最后访问根节点。递归遍历可以先递归访问左子树和右子树,最后输出根节点。非递归遍历可以用栈进行模拟,在遍历每个节点的时候都要记录下该节点是否已经被访问过了,当左右子树都被访问过的时候,再输出根节点。
总之,递归遍历的代码比较简单,但是会使用到函数调用栈,容易导致栈溢出,所以针对比较大的二叉树,我们通常使用非递归遍历。非递归遍历可以使用栈来模拟递归过程,但是需要注意栈空的时候需要退出循环。
### 回答3:
二叉树遍历是指以某种顺序依次访问二叉树中所有结点,是二叉树最常用的操作之一。常见的遍历方式有中序遍历、前序遍历和后序遍历。这三种遍历方式都可以采用递归和非递归算法实现。
1. 中序遍历
中序遍历的顺序是左孩子-根节点-右孩子。递归实现中序遍历:
```
void inorder(TreeNode* root) {
if (root == nullptr) return;
inorder(root->left);
visit(root);
inorder(root->right);
}
```
非递归实现中序遍历:
```
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur || !s.empty()) {
while (cur) {
s.push(cur);
cur = cur->left;
}
cur = s.top(); s.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}
```
2. 前序遍历
前序遍历的顺序是根节点-左孩子-右孩子。递归实现前序遍历:
```
void preorder(TreeNode* root) {
if (root == nullptr) return;
visit(root);
preorder(root->left);
preorder(root->right);
}
```
非递归实现前序遍历:
```
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* tmp = s.top(); s.pop();
res.push_back(tmp->val);
if (tmp->right) s.push(tmp->right);
if (tmp->left) s.push(tmp->left);
}
return res;
}
```
3. 后序遍历
后序遍历的顺序是左孩子-右孩子-根节点。递归实现后序遍历:
```
void postorder(TreeNode* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
visit(root);
}
```
非递归实现后序遍历:
```
// 双栈法
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* tmp = s1.top(); s1.pop();
s2.push(tmp);
if (tmp->left) s1.push(tmp->left);
if (tmp->right) s1.push(tmp->right);
}
while (!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}
```
```
// 单栈法
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) return res;
stack<TreeNode*> s;
TreeNode* cur = root;
TreeNode* last = nullptr;
while (cur || !s.empty()) {
while (cur) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
if (cur->right == nullptr || cur->right == last) {
res.push_back(cur->val);
s.pop();
last = cur;
cur = nullptr;
}
else {
cur = cur->right;
}
}
return res;
}
```
非递归的实现需要用到栈,代码实现可能有些繁琐,但是值得熟练掌握。在实际编码中,也可使用Morris遍历来实现二叉树遍历并节省空间。