树3—树的遍历

 

树3—树的遍历

 

1. 按照根结点，左子树，右子树的顺序输出结点编号，称为树的前序遍历（preorder tree walk）。

2. 按照左子树，根结点，右子树的顺序输出结点编号，称为树的中序遍历（inorder tree walk）。

3. 按照左子树，右子树，根结点的顺序输出结点编号，成为树的后序遍历（postorder tree walk）。

 

preorde，inorder，postorder遍历均为递归算法。

具体如下：

void preorder(int u) {
	if (u == nil)return ;
	printf("%d ", u);
	preorder(t[u].l);
	preorder(t[u].r);
}

 

void inorder(int u) {
	if (u == nil)return;
	inorder(t[u].l);
	printf("%d ", u);
	inorder(t[u].r);
}

 

void postorder(int u) {
	if (u == nil)return;
	postorder(t[u].l);
	postorder(t[u].r);
	printf("%d ", u);
}

只要改变printf（u）的位置，就可以实现不同的遍历算法。

完整代码如下：

#include<stdio.h>
#define nil -1
#define max 10000

struct node { int p, l, r; };
node t[max];

int n;

void preorder(int u) {
	if (u == nil)return ;
	printf("%d ", u);
	preorder(t[u].l);
	preorder(t[u].r);
}

void inorder(int u) {
	if (u == nil)return;
	inorder(t[u].l);
	printf("%d ", u);
	inorder(t[u].r);
}

void postorder(int u) {
	if (u == nil)return;
	postorder(t[u].l);
	postorder(t[u].r);
	printf("%d ", u);
}

int main() {
	int i, v, r, l,root=0;

	scanf_s("%d", &n);

	for (i = 0; i < n; i++) {
		t[i].p = nil;
	}

	for (i = 0; i < n; i++) {
		scanf_s("%d%d%d", &v, &l, &r);
		t[v].l = l;
		t[v].r = r;
		if (l != nil)t[l].p = v;
		if (r != nil)t[r].p = v;
	}

	for (i = 0; i < n; i++) {
		if (t[i].p == nil)root = i;
	}

	preorder(root);
	printf("\n");
	inorder(root);
	printf("\n");
	postorder(root);

	return 0;

}

二叉树遍历会对树的每个结点进行一次访问，因此算法复杂度为O（n）。

用递归法遍历算法时，树的结点数量庞大且分布不均时，会导致递归深度过深。

---

读《挑战程序设计竞赛》第二十一天（侵删）2021.3.17