二叉树

使用链式存储。

因为书上的大题使用的都是链式存储。所以我也采取这样的方式，作为我的算法模板。

二叉树的类型描述

1
2
3
4
typedef struct BiTNode{
	int data; // 数据域
	struct BiTNode * lchild, * rchild; // 左、右孩子指针
}BiTNode, * BiTree;

先序递归建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 先序递归建树
BiTree CreateBiTree(){
	BiTNode * root = (BiTNode *)malloc(sizeof(BiTNode));
	int ch;
	cin >> ch;
	
	if(ch == -1){
		root = NULL;
	}else{
		root -> data = ch;
		root -> lchild = CreateBiTree();
		root -> rchild = CreateBiTree();
	}
	return root;
}

先序遍历

1
2
3
4
5
6
7
8
// 先序遍历
void PreOrder(BiTree root){
	if(root){
		cout << root -> data << endl;
		PreOrder(root -> lchild);
		PreOrder(root -> rchild);
	}
}

中序遍历

1
2
3
4
5
6
7
8
// 中序遍历
void InOrder(BiTree root){
	if(root){
		InOrder(root -> lchild);
		cout << root -> data << endl;
		InOrder(root -> rchild);
	}
}

后序遍历

1
2
3
4
5
6
7
8
// 后序遍历
void PostOrder(BiTree root){
	if(root){
		PostOrder(root -> lchild);
		PostOrder(root -> rchild);
		cout << root -> data << endl;
	}
}

先序遍历的非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 先序遍历的非递归算法
void PreOrder2(BiTree root){
	// 需要使用辅助栈，模拟递归
	SqStack s; InitStack(s);
	// 遍历指针p
	BiTNode * p = root;
	
	// p不空 或者 栈不空 循环
	while(p || !EmptyStack(s)){
		if(p){// 一路向左
			cout << p -> data << endl;
			Push(s, p);
			p = p -> lchild;
		}else{// 出栈，并转向出栈结点的右子树
			Pop(s, p);
			p = p -> rchild;
		}
	}
}

关于先序遍历的非递归算法：

  1. 根左右，先根的性质，决定了在一路向左的过程，是可以边输出边入栈的。
  2. 模拟递归回溯，也就是else部分，此时已经完成了根左。现就只要出栈，并转向出栈结点的右子树。

中序遍历的非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 中序遍历的非递归算法
void InOrder2(BiTree root){
	// 需要使用辅助栈，模拟递归
	SqStack s; InitStack(s);
	// 遍历指针p
	BiTNode * p = root;
	
	// p不空 或者 栈不空 循环
	while(p || !EmptyStack(s)){
		if(p){// 一路向左
			Push(s, p);
			p = p -> lchild;
		}else{// 出栈，并转向出栈结点的右子树
			Pop(s, p);
			cout << p -> data << endl;
			p = p -> rchild;
		}
	}
}

关于中序遍历的非递归算法：

  1. 与先序遍历的非递归算法类似，不同的是什么时候访问结点。
  2. 左根右，决定了必须要找到最左边的结点再回溯。
  3. else部分，也就是模拟递归回溯过程，必须要先出栈再拿着那个结点的值访问。

后序遍历非递归算法

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
// 后序遍历的非递归算法
void PostOrder2(BiTree root){
	// 需要使用辅助栈，模拟递归
	SqStack s; InitStack(s);
	// 遍历指针p
	BiTNode * p = root;
	// 还需要借助一个指针r，记录最近访问过的结点
	// 因为回溯的过程中，可能是从左边回溯，也可能是从右边回溯
	// 从左边回溯，那么根结点就没被访问过。
	// 从右边回溯，那么根结点被访问过。
	BiTNode * r = NULL;
	
	// p不空 或者 栈不空 循环
	while(p || !EmptyStack(s)){
		if(p){ // 一路向左
			Push(s, p);
			p = p -> lchild;
		}else{ // 转右
			GetTop(s, p);
			// 右子树存在，且右子树还没被访问过
			if(p -> rchild && p -> rchild != r){
				p = p -> rchild;
			}else{ // 否则出栈
				Pop(s, p);
				cout << p -> data << endl;
				r = p; // 标记为最近访问过的结点
				p = NULL; // 重置p，这样下次循环会直接弹出栈顶元素。
			}
		}
	}
}

关于后序遍历的非递归算法：

  1. 指针r：回溯的过程中，可能是从左边回溯，也可能是从右边回溯。∴ 从左边回溯，那么根结点就没被访问过。从右边回溯，那么根结点被访问过。根结点被访问过，说明该直接从栈顶弹出一个元素。

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 层序遍历
void LevelOrder(BiTree root){
	// 辅助队列
	SqQueue q; InitQueue(q);
	
	EnQueue(q, root);
	
	while(!EmptyQueue(q)){
		BiTNode * t; DeQueue(q, t);
		cout << t -> data << endl;
		
		if(t -> lchild) EnQueue(q, t -> lchild);
		if(t -> rchild) EnQueue(q, t -> rchild);
		
	}
}