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

二叉树递归与非递归的先序,中序,后序遍历以及层序遍历

程序员文章站 2022-06-17 17:36:02
...

前几天把二叉树的遍历复习了一下,代码可以直接复制运行(包含了二叉树的创建,这里直接创建了一个二叉搜索树),可以留作复习用,不明白的可以用vs调试慢慢看。
其中非递归遍历用栈实现。

样例的二叉树为:
二叉树递归与非递归的先序,中序,后序遍历以及层序遍历

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

struct bTree
{
	int val;
	bTree* lchild;
	bTree* rchild;
};
//新建结点
bTree* newNode(int v)
{
	bTree* node = new bTree;
	node->val = v;
	node->lchild = NULL;
	node->rchild = NULL;
	return node;
}
//插入操作
void insertNode(bTree*& node, int v)
{
	if (!node)
		node = newNode(v);
	else if (v < node->val)       //插入左子树
		insertNode(node->lchild, v);
	else                         //插入右子树
		insertNode(node->rchild, v);
}
//创建二叉树
bTree* creatNode(int data[], int n)
{
	bTree* root = NULL;
	for (int i = 0; i < n; i++)
		insertNode(root, data[i]);

	return root;
}
//递归先序遍历
void preOrder(bTree* root)
{
	if (!root)
		return;
	cout << root->val;
	preOrder(root->lchild);
	preOrder(root->rchild);
}
//非递归先序遍历
void preOrder_nores(bTree* root)
{
	bTree* temp;
	stack<bTree*> s;
	if (!root)
		return;
	s.push(root);
	while (!s.empty())
	{
		temp = s.top();
		s.pop();
		cout << temp->val;
		if (temp->rchild)
			s.push(temp->rchild);
		if (temp->lchild)
			s.push(temp->lchild);
	}
}

//递归中序遍历
void inOrder(bTree* root)
{
	if (!root)
		return;
	inOrder(root->lchild);
	cout << root->val;
	inOrder(root->rchild);
}
//非递归中序遍历
void inOrder_nores(bTree* root)
{
	stack<bTree*> s;
	while (!s.empty() || root)
	{
		if (root)
		{
			s.push(root);
			root = root->lchild;
		}
		else
		{
			root = s.top();
			cout << root->val;
			s.pop();
			root = root->rchild;
		}
	}
}
//后序遍历
void postOrder(bTree* root)
{
	if (!root)
		return;
	postOrder(root->lchild);
	postOrder(root->rchild);
	cout << root->val;
}
//非递归后序遍历
void postOrder_nores(bTree* root)
{
	stack<bTree*> s;
	if (!root)
		return;
	//s.push(root);
	bTree* p = root, * q;

	do 
	{
		while (p != nullptr) /* 往左下走 */ 
		{ 
			
			s.push(p); 
			p = p->lchild; 
		} 
		q = nullptr;
		while (!s.empty()) 
		{ 
			p = s.top(); 
			s.pop();
			/* 右孩子不存在或已被访问,访问之 */
			if (p->rchild == q) 
			{ 
				cout<<p->val;
				q = p; /* 保存刚访问过的结点 */ 
			} 
			else 
			{ 
				/* 当前结点不能访问,需第二次进栈 */ 
				s.push(p); /* 先处理右子树 */
				p = p->rchild; 
				break; 
			} 
		}
	} while (!s.empty()); 

}

//层序遍历
void layerOrder(bTree* root)
{
	queue<bTree*> q;
	bTree* tmp = NULL;
	if (!root)
		return;
	q.push(root);
	while (!q.empty())
	{
		tmp = q.front();
		q.pop();
		cout << tmp->val;
		if (tmp->lchild)
			q.push(tmp->lchild);
		if (tmp->rchild)
			q.push(tmp->rchild);
	}
}

int main()
{
	bTree* root = NULL;
	int a[7] = { 4,2,6,1,3,5,7 };
	root = creatNode(a, 7);
	cout << "递归先序遍历 ";
	preOrder(root);
	cout << endl << "非递归先序遍历 ";
	preOrder_nores(root);
	cout << endl << "递归中序遍历 ";
	inOrder(root);
	cout << endl << "非递归中序遍历 ";
	inOrder_nores(root);
	cout << endl << "递归后序遍历 ";
	postOrder(root);
	cout << endl << "非递归后序遍历 ";
	postOrder_nores(root);
	cout << endl << "层序遍历 ";
	layerOrder(root);
	return 0;
}

运行截图
二叉树递归与非递归的先序,中序,后序遍历以及层序遍历