二叉树的先序、中序、后序遍历的非递归方式
程序员文章站
2022-05-16 10:08:49
...
先序遍历:
引入栈。
拿到一棵树的根结点后,首先打印该结点的值,然后将其非空右孩子、非空左孩子依次压栈。栈非空循环:从栈顶弹出结点(一棵子树的根节点)并打印其值,再将其非空右孩子、非空左孩子依次压栈。
void pre2(node *root) {
stack<node*> sb;
sb.push(root);
node* cur;
while (!sb.empty()) {
cur = sb.top();
sb.pop();
cout << cur->data;
if (cur->right != NULL) {
sb.push(cur->right);
}
if (cur->left != NULL) {
sb.push(cur->left);
}
}
}
中序遍历
对于一棵树,将该树的左边界全部压栈,cur的走向是只要左孩子不为空就走向左孩子。当左孩子为空时弹出栈顶结点(此时该结点是一棵左子树为空的树的根结点)打印,如果该结点的右孩子非空(说明有右子树),那么将其右孩子压栈,这个右孩子又可能是一棵子树的根节点,因此将这棵子树的左边界压栈,这时回到了开头,以此类推。
void med2(node* root) {
stack<node*> sb;
node* cur;
cur = root;
while (!sb.empty()|| cur!=NULL) {
if (cur!= NULL) {
sb.push(cur);
cur = cur->left;
}
else {
cur = sb.top();
sb.pop();
cout << cur->data;
cur = cur->right;
}
}
}
后序遍历
后序遍历的顺序是左右中。准备两个栈,第一个栈的 元素出栈顺序是 中右左;将出栈的元素压入第二个栈,则第二个栈出栈顺序就是 左右中。第一个栈类似前序遍历的栈,只是左右相反。
当然也有一个栈的方法,比较复杂。
void post2(node* root) {
stack<node*> sb;
stack<node*> res;
node* cur;
sb.push(root);
while (!sb.empty()) {
cur = sb.top();
sb.pop();
res.push(cur);
if (cur->left != NULL) {
sb.push(cur->left);
}
if (cur->right != NULL) {
sb.push(cur->right);
}
}
while (!res.empty())
{
cout << res.top()->data;
res.pop();
}
}
整体的代码:
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
struct node {
int data;
node* left;
node* right;
node() :left(NULL), right(NULL) {}
node(int i) :data(i), left(NULL), right(NULL) {}
};
void pre(node *a) {
if (a!=NULL) {
cout << a->data;
pre(a->left);
pre(a->right);
}
}
void pre2(node *root) {
stack<node*> sb;
sb.push(root);
node* cur;
while (!sb.empty()) {
cur = sb.top();
sb.pop();
cout << cur->data;
if (cur->right != NULL) {
sb.push(cur->right);
}
if (cur->left != NULL) {
sb.push(cur->left);
}
}
}
void med2(node* root) {
stack<node*> sb;
node* cur;
cur = root;
while (!sb.empty()|| cur!=NULL) {
if (cur!= NULL) {
sb.push(cur);
cur = cur->left;
}
else {
cur = sb.top();
sb.pop();
cout << cur->data;
cur = cur->right;
}
}
}
void post2(node* root) {
stack<node*> sb;
stack<node*> res;
node* cur;
sb.push(root);
while (!sb.empty()) {
cur = sb.top();
sb.pop();
res.push(cur);
if (cur->left != NULL) {
sb.push(cur->left);
}
if (cur->right != NULL) {
sb.push(cur->right);
}
}
while (!res.empty())
{
cout << res.top()->data;
res.pop();
}
}
int main() {
node *root = new node(1);
root->left = new node(2);
root->right = new node(3);
root->left->left = new node(4);
root->left->right = new node(5);
root->right->left = new node(6);
root->right->right = new node(7);
//cout << 1 << endl;
pre(root);
cout << endl;
pre2(root);
cout << endl;
med2(root);
cout << endl;
post2(root);
return 1;
}
上一篇: 实现二叉树的先序、中序、后序遍历,包括递归方式和非递归方式
下一篇: 怎样将前端页面的文本边框去掉