学习笔记-数据结构-树与二叉树（2024-4-22）

递归遍历二叉树

先序遍历：

typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrder(BiTree T)
{
	if(T!=NULL)
	{
		vist(T);//访问根节点
		PreOrder(T->lchild);//递归遍历左子树
		PreOrder(T->rchild);//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

中序遍历

typedef struct BiTNode
{
	Elemtype datal
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void InOrder(BiTree T)
{
	if(T!=NULL)
	{
	I	InOrder(T->lchild);//递归遍历左子树
		vist(T);//访问根节点
		InOrder(T->rchild);//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后序遍历

typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,BiTree;
void PostOrder(BiTree T)
{
	if(T!=NULL)
	{
		PostOrder(T->lchild);//递归遍历左子树
		PostOrder(T->rchild);//递归遍历右子树
		visit(T);//访问根节点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

非递归遍历二叉树（需要使用栈）

中序遍历的访问流程：1⃣️沿着根的左孩子，依次将元素入栈，直到左孩子为空；2⃣️栈顶元素出栈并访问，并且判断它是否有右孩子，如果右孩子为空，继续执行2；如果有右孩子，转去执行1。
中序遍历的非递归算法如下：

typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void InOrder2(BiTree T)
{
	InitStack(S);//初始化栈S
	BiTree p=T;//p为遍历指针
	while( p || !IsEmpty(S) )//p不空时或者栈不为空时循环
	{
		if(p)//一路向左
		{
			Push(S,p);//当前节点入栈
			p=p->lchild;//左孩子不空，一直向左走
		}
		else//出栈，并转向出栈节点的右子树
		{
			Pop(S,p);//栈顶元素出栈，并将值存于p
			vist(p);//访问出栈节点
			p=p->rchild;//向右子树走，p赋值为当前节点的右孩子
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

先序遍历的访问流程：1⃣️先访问当前节点的元素，然后沿着当前节点的左孩子，将元素入栈，一直循环先访问再入栈，直到左孩子为空；2⃣️栈顶元素出栈，并且判断有没有右孩子，如果没有右孩子，继续栈顶元素出栈；如果有右孩子，继续执行1。
先序遍历的非递归算法如下：

typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void PreOrder2(BiTree T)
{
	InitStack(S);//初始化栈S
	BiTree p=T;//p是遍历指针
	while( p || !IsEmpty(S) )//p不空时或者栈不空时循环
	{
		if(p)//一路向左
		{
			visit(p);//访问当前节点
			Push(S,p);//当前节点入栈
			p=p->lchild;//左孩子不为空，一直向左走
		}
		else//出栈，并转向出栈节点的右子树
		{
			Pop(S,p);//栈顶元素出栈
			p=p->rchild;//向右子树走，p赋值为当前节点的右孩子
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

后序遍历的思路分析：1⃣️沿着根的左孩子，依次入栈，直到左孩子为空。2⃣️读栈顶元素：若其右孩子不空且未被访问过，将右子树转向执行1；否则，栈顶元素出栈并访问。
在2⃣️中必须分清返回时是从左子树还是返回的还是从右子树返回的，因此设定一个辅助指针r，用于指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问。

typedef struct BiTNode
{
	Elemtype data;
	struct BiTNode *lchild,rchild;
}BiTNode,*BiTree;
void PostOrder2(BiTree T)
{
	InitStack(S);
	BiTree *p=T;
	BiTree *r=NULL;
	while( p || !IsEmpty(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);//将节点弹出
				visit(p->data);//访问该节点
				r=p;//记录最近访问过的节点
				p=NULL;//节点访问完后，重置p指针
			}
		}
	}
}
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

二叉树的层次遍历：进行层次遍历需要借助一个队列。
层次遍历的思想如下：1⃣️首先将二叉树的根节点入队。2⃣️若队列非空，则队头节点出队，访问该节点，若它有左孩子，则将其左孩子入对；若它有右孩子，则将其右孩子入队。3⃣️重复2⃣️步，直至队列为空。

typedef struct BiTNode
{
	ELemtype data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void LevelOrder(BiTree T)
{
	InitQueue(Q);//初始化辅助队列
	BiTree p;
	EnQueue(Q,T);//将根节点入队
	while(!IsEmpty(Q))//队列不空则循环
	{
		Dequeue(Q,p);//队头节点出队
		visit(p);//访问出队节点
		if(p->lchild!=NULL)
		{
			EnQueue(Q,p->lchild);//若左孩子不空，则左孩子入队
		}
		if(p->rchild!=NULL)
		{
			EnQueue(Q,p->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