树--＞算法总结

1. 二叉树的先序遍历（非递归算法）

算法思想 若 p 所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将 p 指向其左孩子结点；若 p 所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将 p 指向其右孩子结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。

#define MAX_STACK	50
void PreOrderTraverse(BTree T)
{
	BTree STACK[MAX_STACK], p = T;
	int	top = -1;
	while (p != NULL || top != -1){
		while (p != NULL){
			VISIT(p);
			STACK[++top] = p;
			p = p->lchild;
		}
		p = STACK[top--];
		p = p->rchild;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 二叉树的中序遍历（非递归算法）

算法思想 若 p 所指结点不为空，则将该结点的地址 p 入栈，然后再将 p 指向其左孩子结点；若 p 所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送 p，并访问该结点，然后再将 p 指向该结点的右孩子结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。

#define MAX_STACK	50
void InOrderTraverse(BTree T)
{
	BTree STACK[MAX_STACK], p = T;
	int	top = -1;
	while (p != NULL || top != -1);{
		while (p != NULL){
			STACK[++top] = p;
			p = p->lchild;
		}
		p = STACK[top--];
		VISIT(p);
		p = p->rchild;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 二叉树的后序遍历（非递归算法）

算法思想 当 p 指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量flag，当 flag = 0 时表示该结点暂不访问，flag = 1 时表示该结点可以访问。flag 的值随同该结点的地址一起入栈和出栈。因此，算法中设置了两个堆栈，其中 STACK1 存放结点的地址，STACK2 存放标志变量 flag，两个堆栈使用同一栈顶指针 top，且 top 的初始值为 −1。

#define MAX_STACK	50
void PostOrderTraverse(BTree T)
{
	BTree STACK1[MAX_STACK], p = T;
	int	STACK2[MAX_STACK], flag, top = -1;
	while (p != NULL || top != -1){
		while (p != NULL) {
			STACK1[++top] = p;
			STACK2[top] = 0;
			p = p->lchild;
		}
		p = STACK1[top];
		flag = STACK2[top--];
		if (flag == 0) {
			STACK1[++top] = p;
			STACK2[top] = 1;
			p = p->rchild;
		} else {
			VISIT(p);
			p = NULL;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 二叉树的按层次遍历

算法思想 设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点（若存在的话）和右孩子结点（若存在的话）入队列。如此重复下去，直到队列为空。

#define MAX_QUEUE	50
void LayeredOrderTraverse(BTree T)
{
	BTree QUEUE[MAX_QUEUE], p;
	int	front, rear;
	if (T != NULL){
		QUEUE[0] = T;
		front = -1;
		rear = 0;
		while (front < rear){
			p = QUEUE[++front];
			VISIT(P);
			if (p->lchild != NULL)
				QUEUE[++rear] = p->lchild;
			if (p->rchild != NULL)
				QUEUE[++rear] = p->rchild;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5. 建立二叉树（从键盘输入数据，先序遍历递归算法）

BTree CreateBT()
{
	char ch;
	BTree T;
	sacnf("%c", &ch);
	if (ch == ' ')
		return NULL;
	else {
		T = (BTree)malloc(sizeof(BTNode));
		T->data	= ch;
		T->lchild = CreateBT();
		T->rchild = CreateBT();
		return T;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6. 建立二叉树（从数组获取数据）

BTree CreateBT(int A[], int i, int n)
{
	BTree p;
	if (i > n)
		return NULL;
	else {
		p = (BTree)malloc(sizeof(BTNode));
		p->data = A[i];
		p->lchild = CreateBT(A, 2*i, n);
		p->rchild = CreateBT(A, 2*i+1, n);
		return p;
	}
}
T = CreateBT(A, 1, n);
--------------------------------------------------------
BTree CreateBT(int A[], int n)
{
	int	i;
	BTree *pT;
	//	对应 n 个结点申请可容纳 n 个指针变量的内存空间 
	pT = (BTree *)malloc(sizeof(BTree)*n);
	//	若数组中的某个元素不等于零，则申请相应的结点空间并进行赋值 
	for (i=1; i <= n; i++){
		if (A[i] != 0) {
			pT[i] = (BTree)malloc(sizeof(BTNode));
			pT[i]->data = A[i];
		} else {
			pT[i] = NULL;
		}
	}
	//	修改结点的指针域的内容，使父结点指向左、右孩子结点 
	for (i=1; i <= n; i++){
		if (pT[i] != NULL){
			pT[i]->lchild = pT[2*i]; pT[i]->rchild = pT[2*i+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

7. 求二叉树的深度（递归算法）

int Depth(BTree T)
{
	int ldepth, rdepth;
	if (T == NULL)
		return 0;
	else {
	ldepth = Depth(T->lchild);
	rdepth = Depth(T->rchild);
	if (ldepth > rdepth)
		return ldepth+1;
	else
		return rdepth+1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

8. 求二叉树的深度（非递归算法）

算法思想 对二叉树进行遍历，遍历过程中依次记录各个结点所处的层次数以及当前已经访问过的结点所处的最大层次数。每当访问到某个叶子结点时，将该叶子结点所处的层次数与最大层次数进行比较，若前者大于后者，则修改最大层次数为该叶子结点的层次数，否则不作修改。遍历结束时，所记录的最大层次数即为该二叉树的深度。本算法使用的是非递归的中序遍历算法（其它遍历顺序也可以）。

#define MAX_STACK	50
int Depth(BTree T)
{
	BTree STACK1[MAX_STACK], p = T;
	int	STACK2[MAX_STACK];
	int	curdepth, maxdepth = 0, top = -1;
	if (T != NULL){
		curdepth = 1;
		while (p != NULL || top != -){
			while (p != NULL){
				STACK1[++top] = p;
				STACK2[top] = curdepth;
				p = p->lchild;
				curdepth++;
			}
			p = STACK1[top];
			curdepth = STACK2[top--];
			if (p->lchild == NULL && p->rchild == NULL)
				if (curdepth > maxdepth)
					maxdepth = curdepth;
			p = p->rchild;
			curdepth++;
		}
	}
	return maxdepth;
}
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

9. 求结点所在层次

算法思想：采用后序遍历的非递归算法对二叉树进行遍历，遍历过程中对每一个结点判断其是否为满足条件的结点，若是满足条件的结点，则此时堆栈中保存的元素个数再加 1 即为该结点所在的层次。

#define MAX_STACK	50
int LayerNode(BTree T, int item)
{
	BTree STACK1[MAX_STACK], p = T;
	int	STACK2[MAX_STACK], flag, top = -1;
	while (p != NULL || top != -1){
		while (p != NULL){
			STACK1[++top] = p;
			STACK2[top] = 0;
			p = p->lchild;
		}
		p = STACK1[top];
		flag = STACK2[top--];
		if (flag == 0) {
			STACK1[++top] = p;
			STACK2[top] = 1;
			p = p->rchild;
		} else {
			if (p->data == item)
			return top+2;
			p = NULL;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

10. 交换二叉树中所有结点的左右子树的位置

算法思想：按层次遍历二叉树，遍历过程中每当访问一个结点时，就将该结点的左右子树的位置对调。

#define MAX_QUEUE	50
void ExchangeBT(BTree T)
{
	BTree QUEUE[MAX_QUEUE], temp, p = T;
	int	front, rear;
	if (T != NULL){
		QUEUE[0] = T;
		front = -1;
		rear = 0;
		while (front < rear){
			p = QUEUE[++front];
			temp = p->lchild;
			p->lchild = p->rchild;
			p->rchild = temp;
			if (p->lchild != NULL)
				QUEUE[++rear] = p->lchild;
			if (p->rchild != NULL)
				QUEUE[++rear] = p->rchild;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

11. 删除二叉树中以某个结点为根结点的子树

算法思想：先序遍历找到符合条件的结点（其它遍历方法亦可），然后删除以该结点为根结点的子树。最后把该结点的父结点的相应的指针域置为 NULL。为此，需在算法中设置一个指针变量用以指示当前结点的父结点。

#define MAX_STACK	50
BTree DeleteSubtree(BTree &T, int item)
{
	BTree STACK[MAX_STACK], q, p = T;
	int	top = -1;
	if (T->data == item){
		DestroyBT(T);
		T = NULL;
		return NULL;
	}else{
		while (p != NULL || top != -1){
			while (p != NULL){
				if (p->data == item){
					if (q->lchild == p)
						q->lchild = NULL;
					else
						q->rchild = NULL;
					DestroyBT(p);
					return T;
				}
				STACK[++top]= p;
				q = p;
				p = p->lchild;
			}
			q = STACK[top--];
			p = q->rchild;
		}
	}
}
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