二叉树的前、中、后序排列

二叉树的前、中、后序排列 前序排列

前序排列就是按照根、左子树、右子树的顺序输出。

搜索顺序如下：

void pro_dfs(int rt)//rt为当前节点
{
	if(rt == -1) return; //当该点不存在时返回上一个点
	cout << ' ' << tree[rt].u;//输出当前节点
	pro_dfs(tree[rt].lc);//扩展到左子树
	pro_dfs(tree[rt].rc);//扩展到右子树
}

---

中序排列

中序排列即为按照左子树、根、右子树的顺序输出。

搜索顺序如下：

void mid_dfs(int rt)
{
	if(rt == -1) return;
	mid_dfs(tree[rt].lc);
	cout << ' ' << tree[rt].u;
	mid_dfs(tree[rt].rc);
}

---

后序排列

按照左子树、右子树、根的顺序输出。

搜索顺序如下：

void post_dfs(int rt)
{
	if(rt == -1) return;
	post_dfs(tree[rt].lc);
	post_dfs(tree[rt].rc);
	cout << ' ' << tree[rt].u;
}

---

代码

#include 

using namespace std;

const int maxn = 100010;
int n;

struct hzw
{
	int lc,rc,u,fa;//左子树，右子树，当前节点，父亲节点
}tree[maxn];

void pro_dfs(int rt)//前序排列
{
	if(rt == -1) return;
	cout << ' ' << tree[rt].u;
	pro_dfs(tree[rt].lc);
	pro_dfs(tree[rt].rc);
}

void mid_dfs(int rt)//中序排列
{
	if(rt == -1) return;
	mid_dfs(tree[rt].lc);
	cout << ' ' << tree[rt].u;
	mid_dfs(tree[rt].rc);
}

void post_dfs(int rt)//后序排列
{
	if(rt == -1) return;
	post_dfs(tree[rt].lc);
	post_dfs(tree[rt].rc);
	cout << ' ' << tree[rt].u;
}

int main()
{
	cin >> n;
	for(int i=0; i> rt >> lc >> rc;
		tree[rt].u = rt;
		tree[rt].lc = lc;
		tree[rt].rc = rc;
		if(lc != -1) tree[lc].fa = rt;
		if(rc != -1) tree[rc].fa = rt;
	}
	int root;
	for(int i=0; i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5592937.html