欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的先序、中序、后序遍历的非递归方式

程序员文章站 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;
}
相关标签: 后端