1、二叉树的深度遍历
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树的所有结点，使得每个结点被访问一次且仅被访问一次。
对于二叉树的深度遍历，有前序遍历二叉树、中序遍历二叉树、后序遍历二叉树三种形式，下面分别进行学习和介绍。
1.1 二叉树的前序遍历
1）前序递归遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图所示，遍历的顺序为ABDGHCEIF。
前序递归遍历的代码实现，如下所示。
|
1
2
3
4
5
6
7
8
9
10
|
//前序递归遍历void PreOrderTraverse(BiTree t)
{ if(t != NULL)
{
printf("%c ", t->data);
PreOrderTraverse(t->lchild);
PreOrderTraverse(t->rchild);
}
} |
2）前序非递归遍历
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同的规则访问它的左子树；当访问其左子树时，再访问它的右子树，因此其处理过程如下：
对于任一结点p：
a. 访问结点p，并将结点p入栈；
b. 判断结点p的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点p，循环置a；若不为空，则将p的左孩子置为当前结点p；
c. 直到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
|
//前序非递归遍历int NoPreOrderTraverse(BiTree t)
{ SqStack s;
InitStack(&s);
BiTree tmp = t;
if(tmp == NULL)
{
fprintf(stdout, "the tree is null.\n");
return ERROR;
}
while((tmp != NULL) || (IsEmpty(&s) != 1))
{
while(tmp != NULL)
{
Push(&s, tmp);
printf("%c ", tmp->data);
tmp = tmp->lchild;
}
if(IsEmpty(&s) != 1)
{
Pop(&s, &tmp);
tmp = tmp->rchild;
}
}
return OK;
} |
1.2 中序遍历二叉树
1）中序递归遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意这里并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图所示，遍历的顺序为：GDHBAEICF。
中序递归遍历代码实现如下所示。
|
1
2
3
4
5
6
7
8
9
10
|
//中序递归遍历void InOrderTraverse(BiTree t)
{ if(t != NULL)
{
InOrderTraverse(t->lchild);
printf("%c ", t->data);
InOrderTraverse(t->rchild);
}
} |
2）中序非递归遍历
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一个根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才停止访问，然后按相同的规则访问其右子树。其处理过程如下：
对于任一结点：
a. 若其左孩子不为空，则将p入栈，并将p的左孩子设置为当前的p，然后对当前结点再进行相同的操作；
b. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；
c. 直到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
|
//中序非递归遍历二叉树int NoInOrderTraverse(BiTree t)
{ SqStack s;
InitStack(&s);
BiTree tmp = t;
if(tmp == NULL)
{
fprintf(stderr, "the tree is null.\n");
return ERROR;
}
while(tmp != NULL || (IsEmpty(&s) != 1))
{
while(tmp != NULL)
{
Push(&s, tmp);
tmp = tmp->lchild;
}
if(IsEmpty(&s) != 1)
{
Pop(&s, &tmp);
printf("%c ", tmp->data);
tmp = tmp->rchild;
}
}
return OK;
} |
1.3 后序遍历二叉树
1）后序递归遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。遍历的顺序为：GHDBIEFCA。
后序递归遍历代码实现，如下所示。
|
1
2
3
4
5
6
7
8
9
10
|
//后序递归遍历void PostOrderTraverse(BiTree t)
{ if(t != NULL)
{
PostOrderTraverse(t->lchild);
PostOrderTraverse(t->rchild);
printf("%c ", t->data);
}
} |
2）后序非递归遍历
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难题。下面介绍一种思路。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它，或者p存在左孩子或右孩子，但是其左孩子和右孩子都已经被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将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
35
36
37
38
39
40
|
//后序非递归遍历二叉树int NoPostOrderTraverse(BiTree t)
{ SqStack s;
InitStack(&s);
BiTree cur; //当前结点
BiTree pre = NULL; //前一次访问的结点
BiTree tmp;
if(t == NULL)
{
fprintf(stderr, "the tree is null.\n");
return ERROR;
}
Push(&s, t);
while(IsEmpty(&s) != 1)
{
GetTop(&s, &cur);//
if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
{
printf("%c ", cur->data); //如果当前结点没有孩子结点或者孩子结点都已被访问过
Pop(&s, &tmp);
pre = cur;
}
else
{
if(cur->rchild != NULL)
{
Push(&s, cur->rchild);
}
if(cur->lchild != NULL)
{
Push(&s, cur->lchild);
}
}
}
return OK;
} |
2、二叉树的广度遍历
广度遍历二叉树（即层次遍历）是用队列来实现的，从二叉树的第一层（根结点）开始，自上而下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。如下图所示，遍历的顺序为：ABCDEFGHI。
按照从根结点到叶结点、从左子树到右子树的次序访问二叉树的结点，具体思路如下：
A. 初始化一个队列，并把根结点入队列；
B. 当队列为非空时，循环执行步骤3到步骤5，否则执行步骤6；
C. 出队列取得一个结点，访问该结点；
D. 若该结点的左子树为非空，则将该结点的左子树入队列；
E. 若该结点的右子树为非空，则将该结点的右子树入队列；
F. 结束。
广度遍历二叉树代码实现，如下所示。
|
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
|
//层次遍历二叉树 - 广度遍历二叉树 - 队列int TraverseBiTree(BiTree t)
{ LinkQueue q;
InitQueue(&q);
BiTree tmp = t;
if(tmp == NULL)
{
fprintf(stderr, "the tree is null.\n");
return ERROR;
}
InsertQueue(&q, tmp);
while(QueueIsEmpty(&q) != OK)
{
DeQueue(&q, &tmp);
printf("%c ", tmp->data);
if(tmp->lchild != NULL)
{
InsertQueue(&q, tmp->lchild);
}
if(tmp->rchild != NULL)
{
InsertQueue(&q, tmp->rchild);
}
}
return OK;
} |
3、二叉树的建立
如果要在内存中建立一个如下左图这样的树，wield能让每个结点确认是否有左右孩子，我们对它进行扩展，变成如下右图的样子，也就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值，比如”#”，称之为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。如前序遍历序列为AB#D##C##。
有了这样的准备，就可以看看如何生成一棵二叉树了。假设二叉树的结点均为一个字符，把刚才前序遍历序列AB#D##C##用键盘挨个输入，实现的算法如下所示。
二叉树建立实现代码一，如下所示。
|
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
|
//创建树//按先后次序输入二叉树中结点的值(一个字符),#表示空树//构造二叉链表表示的二叉树BiTree CreateTree(BiTree t){ char ch;
scanf("%c", &ch);
if(ch == '#')
{
t = NULL;
}
else
{
t = (BitNode *)malloc(sizeof(BitNode));
if(t == NULL)
{
fprintf(stderr, "malloc() error in CreateTree.\n");
return;
}
t->data = ch; //生成根结点
t->lchild = CreateTree(t->lchild); //构造左子树
t->rchild = CreateTree(t->rchild); //构造右子树
}
return t;
} |
二叉树建立实现代码二，如下所示。
|
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
|
//创建树方法二int CreateTree2(BiTree *t)
{ char ch;
scanf("%c", &ch);
if(ch == '#')
{
(*t) = NULL;
}
else
{
(*t) = (BiTree)malloc(sizeof(BitNode));
if((*t) == NULL)
{
fprintf(stderr, "malloc() error in CreateTree2.\n");
return ERROR;
}
(*t)->data = ch;
CreateTree2(&((*t)->lchild));
CreateTree2(&((*t)->rchild));
}
return OK;
} |
其实建立二叉树，也是利用了递归的原理。只不过在原来应该打印结点的地方，改成生成结点、给结点赋值的操作而已。因此，完全可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。
4、二叉树的深度
树中结点的最大层次称为树的深度。对于二叉树，求解树的深度用以下两种方法实现。即非递归和递归的方法实现。
递归求解二叉树的深度实现代码，如下所示。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//二叉树的深度 - 递归//返回值: 二叉树的深度int BiTreeDeep(BiTree t)
{ int dept = 0;
if(t)
{
int lchilddept = BiTreeDeep(t->lchild);
int rchilddept = BiTreeDeep(t->rchild);
dept = lchilddept >= rchilddept ? (lchilddept + 1) : (rchilddept + 1);
}
return dept;
} |
对于非递归求解二叉树的深度，这里采用了层次遍历的原理，通过层次遍历，找到二叉树的最后一个结点。然后，根据该结点，寻找其双亲结点，即找到其上一层，此时深度dept加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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
//返回二叉树的深度 - 非递归 - 受层次遍历二叉树的影响//返回值: 二叉树的深度int NoBiTreeDeep(BiTree t)
{ LinkQueue q;
InitQueue(&q);
BiTree tmp = t;
if(tmp == NULL)
{
return ERROR;
}
InsertQueue(&q, tmp);
while(QueueIsEmpty(&q) != OK)
{
DeQueue(&q, &tmp);
//printf("%c ", tmp->data);
if(tmp->lchild != NULL)
{
InsertQueue(&q, tmp->lchild);
}
if(tmp->rchild != NULL)
{
InsertQueue(&q, tmp->rchild);
}
}
int deep = 0;
BiTree m = tmp;
BiTree n = t;
while(m != n)
{
InsertQueue(&q, n);
while(QueueIsEmpty(&q) != OK)
{
DeQueue(&q, &tmp);
if(m == tmp->lchild || m == tmp->rchild)
{
deep++;
m = tmp;
break;
}
if(tmp->lchild != NULL)
{
InsertQueue(&q, tmp->lchild);
}
if(tmp->rchild != NULL)
{
InsertQueue(&q, tmp->rchild);
}
}
}
return deep + 1; //深度从1开始
|
相关推荐
二叉树作为一种重要的数据结构，广泛应用于计算机科学的各个领域，如编译器设计、操作系统、数据库、图形学等。它的遍历是理解和操作二叉树的基础，这其中包括前序遍历、中序遍历、后序遍历以及层次遍历（也称为广度...
在二叉树遍历中，我们利用函数调用自身来处理树的不同部分。 1. **前序遍历**（根-左-右）： - 递归版本：首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。 - 非递归版本：使用栈来模拟递归过程。首先...
二叉树作为一种基础且重要的数据结构，被广泛应用于各种场景，如文件系统、编译器、数据库索引等。本篇文章将深入探讨二叉树及其遍历方法的源代码实现。 二叉树是由节点构成的层次结构，每个节点最多有两个子节点，...
数据结构二叉树及遍历 PPT 二叉树是一种数据结构，用于表示不同数据元素之间的层级关系。它由节点组成，每个节点都有一个值，并且可以有零个或多个子节点。二叉树的每个节点都有一个父节点和零个或多个子节点。根...
通过对上述代码的分析，我们可以看到二叉树遍历的基本思路是通过递归的方式来实现的。在实际应用中，二叉树及其遍历方法是非常重要的基础，掌握这些基本概念和技术对于深入理解高级数据结构和算法设计具有重要意义。
数据结构二叉树的遍历 二叉树的深度 二叉树的某结点层次 二叉树结点数
数据结构课程设计报告-二叉树的遍历 本报告基于二叉树的遍历方法，旨在通过递归和非递归两种方法创建一棵二叉树，并对其进行先序遍历、中序遍历、后序遍历及层次遍历，并求出该二叉树的深度和叶子结点数。同时，...
在IT领域，数据结构和算法是基础且至关重要的部分，它们直接影响到程序的效率和性能。本主题聚焦于“二叉树遍历”、“图的遍历”以及“排序算法”，这些都是计算机科学中的核心概念。 首先，我们来讨论二叉树遍历。...
总结来说，二叉树遍历算法在实际问题中具有广泛的实用性，不仅可以用于数据结构的分析，还能解决如统计信息和计算深度等实际问题。通过理解和掌握这些算法，开发者可以更有效地处理涉及二叉树的各种挑战。
在本实验中，我们主要探讨的是二叉树的遍历方法，这是数据结构中的一个重要概念。二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树遍历是访问二叉树中所有节点的过程...
### 二叉树遍历实验报告知识点概览 #### 一、实验背景及目标 **实验背景：** 本次实验属于《数据结构》课程的一部分，旨在通过实际编程加深学生对二叉树这一数据结构的理解和应用能力。二叉树作为一种基本且重要的...
二叉树是一种常见的数据结构，遍历二叉树是指从根节点开始访问树中的所有节点，并对其进行处理。二叉树遍历算法有多种，包括前序遍历、中序遍历、后序遍历、层次遍历等。每种遍历算法都有其特点和应用场景，本文将...
二叉树遍历是计算机科学中的一个重要概念，主要应用于数据结构和算法领域。二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树遍历是指按照特定顺序访问二叉树的所有...
（选做）【基本要求】从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）【测试数据】如输入：ABC##DE#G##F###（其中#表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：...
数据结构二叉树遍历有关算法 数据结构中的二叉树是一种常用的数据结构形式，二叉树遍历是一种基本的算法操作，旨在访问二叉树中的每个节点，并对其进行相应的处理。以下是相关的知识点： 一、 二叉树的定义 在...
在IT领域，数据结构是计算机科学的基础，而二叉树作为一种重要的数据结构，广泛应用于算法设计、数据库系统、编译器等。本话题主要聚焦于二叉树的遍历，这是理解和操作二叉树的关键技能之一。二叉树遍历是指按照特定...
二叉树遍历是针对这种数据结构的一种基本操作，用于按照特定顺序访问树中的所有节点。本程序实现了三种主要的二叉树遍历方法：先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释： 1. 先序遍历...
本实验主题为“数据结构上机实验2”，主要涵盖了二叉树的一些核心操作，包括深度遍历、层次遍历以及计算二叉树的深度。这里我们将深入探讨这些概念及其在C++中的实现。 首先，我们来理解二叉树。二叉树是一种特殊的...
包含了二叉树的建立与遍历，遍历包含前序，中序（两种），后序遍历，以及二叉树的深度计算。程序健壮性较强。