数据结构 | 二叉树的遍历（递归&非递归）

目录

前

中

后

前

#include<iostream>
#include<stack>
using namespace std;
struct BTNode
{
	int data;
	BTNode* left, * right;
	BTNode(int val) :data(val), left(NULL), right(NULL) {}

};
//先序 遍历递归算法
/*void preorder(BTNode* t)
{
	if (t == NULL)
		return;
	cout << t->data;
	preorder(t->left);
	preorder(t->right);
}*/
//先序非递归
void preorder(BTNode* t)
{
	if (t == NULL)
		return;
	stack<BTNode*> s;  //栈的实质：寄放右子树的根指针
	
	while (!s.empty() || t)
	{
		if (t)
		{
			cout << t->data;
			s.push(t);
			t = t->left;
			
		}
		else
		{
			t = s.top();//遍历左子树将结点取出
			s.pop();
			t = t->right;  //通过这些结点来访问右子树
		}
	}

}
int main()
{
	BTNode* root = new BTNode(1);
	root->left = new BTNode(2);
	root->right = new BTNode(3);
	root->left->left = new BTNode(4);
	root->left->right = new BTNode(5);
	root->right->left = new BTNode(6);
	root->right->right = new BTNode(7);
	preorder(root);
	return 0;
}

中

#include<iostream>
#include<stack>
using namespace std;
struct BTNode
{
	int data;
	BTNode* left, * right;
	BTNode(int val) :data(val), left(NULL), right(NULL) {}

};
//中序 遍历递归算法
/*void inorder(BTNode* t)
{
	if (t == NULL)
		return;
	
	inorder(t->left);
	cout << t->data<<'\t';
	inorder(t->right);
}*/
//中序非递归
void inorder(BTNode* t)
{
	if (t == NULL)
		return;
	stack<BTNode*> s;

	while (!s.empty() || t)
	{
		if (t)
		{
			s.push(t);  //将根节点放入栈中
			t = t->left; //将左孩子全部放入栈中，直到栈为空

		}
		else
		{
			t = s.top(); //取出右子树的根指针
			s.pop();
			cout << t->data<<"\t";  //左根右
			t = t->right;
		}
	}

}
int main()
{
	BTNode* root = new BTNode(1);
	root->left = new BTNode(2);
	root->right = new BTNode(3);
	root->left->left = new BTNode(4);
	root->left->right = new BTNode(5);
	root->right->left = new BTNode(6);
	root->right->right = new BTNode(7);
	cout << "中序遍历："  << endl;
	inorder(root);
	return 0;
}

后

#include<iostream>
#include<stack>
using namespace std;
struct BTNode
{
	int data;
	BTNode* left, * right;
	BTNode(int val) :data(val), left(NULL), right(NULL) {}

};
//后序 遍历递归算法
/*void postorder(BTNode* t)
{
	if (t == NULL)
		return;

	postorder(t->left);
	
	postorder(t->right);
	cout << t->data<<'\t';
}*/
//后序遍历非递归算法
void postorder(BTNode* t)
{
	if (t == NULL)
		return;
	stack<BTNode*> s;
	BTNode* r;
	r = NULL;
	while (t || !s.empty())
	{
	
		if (t) //步骤一：沿着根的左孩子，依次入栈，直到左孩子为空
		{
			s.push(t);
			t = t->left;
			
		}
		else
		{
			t = s.top();  //步骤二：读栈顶元素进行判定
			if (t->right && t->right != r) //如果栈顶元素的右孩子存在且右孩子没有被访问过 执行步骤一
			{
				t = t->right; //更新指向指针为它的右孩子
				s.push(t);//右孩子入栈
				t = t->left;//沿着根(右孩子）的左孩子，依次入栈，直到左孩子为空
			}
			else
			{
				
				s.pop(); //步骤三：栈顶元素出栈
				cout << t->data<<'\t';
				r = t;  //将标记指针更新为指向指针
				t = NULL; //出栈之后把指向指示指针置空
				//因为应经访问了，出栈了  所以不用管了
				//t也应该更新为栈顶元素
			}
		}

	}
}
int main()
{
	BTNode* root = new BTNode(1);
	root->left = new BTNode(2);
	root->right = new BTNode(3);
	root->left->left = new BTNode(4);
	root->left->right = new BTNode(5);
	root->right->left = new BTNode(6);
	root->right->right = new BTNode(7);
	cout << "后序遍历：" << endl;
	postorder(root);
	return 0;
}