树与二叉树（三）

Share 
本篇文章是树系列的第三篇文章，主要介绍二叉树的遍历和建树

二叉树的遍历

遍历的定义：顺着某一条搜索路径巡防二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

“遍历”是任何类型都有的操作，对线性结构来说，只有一条搜索路径（因为每个结点只有一个后继），故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径来进行遍历的问题。

对“二叉树”而言，可以有三条搜索路径：

1
2
3
先上后下的按层次遍历
先左（子树）后右（子树）的遍历
先右（子树）后左（子树）的遍历

先左后右的遍历算法

先（根）序的遍历算法：

若二叉树为空树，则空操作，否则：
1）访问根节点；
2）先序遍历左子树；
3）先序遍历右子树

中（根）序的遍历算法：

若二叉树为空树，则空操作，否则：
1）中序遍历左子树；
2）访问根节点；
3）中序遍历右子树

后（根）序的遍历算法：

若二叉树为空树，则空操作，否则：
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根节点

算法的递归描述

1
2
3
4
5
6
7
8
9
void preorder(BiTree T, void(*visit)(elemtype &e)) {
	//先序遍历二叉树
	//中序与后序遍历算法只是将if里的三条语句的顺序换一下就可以了
	if(T) {
		visit(T -> data);	//访问结点
		preorder(T -> lChild, visit);		//访问左子树
		preorder(T -> rChild, visit);		//访问右子树
	}
}

算法的非递归描述

1
中序遍历非递归算法

由中序遍历算法过程可知，采用一个栈用以保存需要返回的结点指针，先扫描（并非访问）根节点的所有左结点并将他们一一进栈。

然后出栈一个结点，显然该结点没有左孩子结点或者左孩子结点已经访问过，则访问它。

然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所在左结点并一一进栈。循环，直到栈空为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void inOrder(BiTree root) {
	//调用栈操作实现
	initStack(&S);
	p = root;
	while(p != NULL || !stackEmpty) {
		if(p != NULL) {
			//根指针进栈，遍历左子树
			push(&S, p);
			p = p -> lChild;
		}else {
			//根指针出栈，访问根节点，遍历右子树
			pop(&S, p);
			visit(p -> data);
			//改变visit的位置就可以改变算法的实现，比如放到前面的if中就是先序遍历
			p = p -> rChild;
		}
	}
}

void NRinOrder(BiTree bt) {
	BiTree stack[MAX_TREE_SIZE], p;
	int top = 0;
	p = bt;
	if (bt == NULL) return;
	while (!(p == NULL && top == 0)) {
		while (p != NULL) {
			if (top < MAX_TREE_SIZE - 1)
				stack[top++] = p;
			else {
				printf(“栈溢出”);
				return;
			}
			p = p -> lChild;	//指针指向p的左孩子结点
		if (top < 0) return;	//栈空时结束
		else {
			p = stack[- -top];	//从栈中推出栈顶元素
			visit(p -> data);	//访问结点的数据域
			p = p -> rChild;	//指针指向p的右孩子结点
		}
	}
}
1
先序遍历的非递归算法

由先序遍历的过程可知，先访问根节点，再访问左子树，最后访问右子树。

因此，先将根节点进栈，在栈不空时循环：出栈p，访问*p结点，将其右孩子结点进栈，再将左孩子进栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrder(BiTree b) {
	BiTree st[MAX_TREE_SIZE], p;
	int top = -1;
	if (b != NULL) {
		st[++top] = b;		//根结点进栈
		while (top > -1) {
			//栈不空时循环
			p = st[top—];
			visit(p -> data);
			if(p -> rChild != NULL) //右孩子进栈
				st[top++] = p -> rChild;
			if(p -> lChild != NULL) //左孩子进栈
				st[top++] = p -> lChild;
		}
	}
}
1
后序遍历的非递归算法

由后序遍历过程可知，采用一个栈保存需要返回的指针结点，先扫描根节点的所有左结点并将他们一一入栈，同时出栈当前结点*b，然后扫描该结点的右孩子结点并进栈，然后扫描该右孩子的所有左结点并入栈。

当一个结点的左、右孩子结点均被访问后再访问该结点，循环，直到栈空为止.

其中的难点是如何判断一个结点*b的右孩子结点已经被访问过，因此用p保存刚刚访问过的结点（初值为NULL），若(b -> rChild) == p成立（在后序遍历中，*b的右孩子结点一定刚好在*b之前访问），说明*b的左右子树均已被访问，现在应访问*b。

从上述过程可知，栈中保存的是当前结点*b的所有祖先结点（均未被访问）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void postOrder1(BiTree b) {
	BiTree st[MAX_TREE_SIZE], p;
	int flag;
	int top = -1;
	if (b != NULL) {
		do {
			while (b != NULL) {
				//扫描b的左结点并进栈
				st[++top] = b;
				b = b -> lChild;
			}
			p = NULL;	//p指向栈顶结点的前一个已被访问过的结点
			flag = 1;	//设置b的访问标记为访问过
			while (top != -1 && flag) {
				b = st[top];	//取出当前的栈顶元素
				if (b -> rChild == p) {
					//右孩子不存在或者已经访问过，则访问\*b
					visit(b -> data);	//访问\*b结点
					top—;
					p = b;		//p指向被访问的结点
				} else {
					b = b -> rChild;	//b指向右孩子结点
					flag = 0;		//设置为未被访问
				}
			}
		}while (top != -1);	
	}
}

由二叉树的先序序列和中序序列建树

仅知二叉树的先序序列“abcdefg”不能确定唯一的一棵二叉树；但同时已知二叉树的中序序列”cbdaegf”，则会如何？

二叉树的先序遍历：根　|　左子树　|　右子树

二叉树的中序遍历：左子树　|　根　|　右子树

已知先序序列和中序序列是可以确定唯一一棵二叉树的。因为先序首先得到根，将根代入中序中便会得到左右划分，以此递推，便可求得二叉树。

同理，若已知后序序列和中序序列也是可以确定唯一一棵二叉树的。

但是，已知先序序列和后序序列则不能确定唯一一棵二叉树，因为两者的作用都是一样的，都是确定根而不能确定左右划分。