0%

【算法导论】二叉树的广度优先遍历

广度优先遍历:又称按层次遍历,也就是先遍历二叉树的第一层节点,然后遍历第二层节点……最后遍历最下层节点。而对每一层的遍历是按照从左至右的方式进行的。

基本思想:按照广度优先遍历的方式,上一层中先被访问的节点,它的下层孩子也必然先被访问,因此在算法实现时,需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队,然后依次从队列中出队结点的存储地址,每出队一个结点的存储地址则对该结点进行访问,然后依次将该结点的左孩子和右孩子的存储地址入队,如此反复,直到队空为止。

具体算法如下:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define maxsize 20

typedef int datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;

void Layer(bitree *p);
bitree* CreatBitree(int* arrayA,int n);
int countleaf(bitree *p);
int treedepth(bitree*p,int l);

void main()
{
int arrayA[10]={0,1,2,3,4,5,6,7,8,9};//第一个节点没有用于存储数据
int n=sizeof(arrayA)/sizeof(int);
int l=0;//二叉树的深度
bitree *head=NULL;

head=CreatBitree(arrayA,n);


printf("按广度优先搜索遍历的结果为:");
Layer(head);
printf("\n");

}

/**************************************************\
函数功能:二叉树的广度优先遍历
输入:二叉树的根节点
输出:无
\**************************************************/
void Layer(bitree *p)
{
bitree* queue[maxsize];//queue数组用于存储节点地址
bitree* s;
int rear=0; //队列尾指针
int front=0; //队列头指针

if(p!=NULL)//输入的树不为空
{
rear=1; //初始化
front=0;
queue[rear]=p;
while(front<rear)//判断队列是否为空
{
front++;
s=queue[front];
printf("%d ",s->data);
if(s->lchild!=NULL) //存储左右子节点
{
rear++;
queue[rear]=s->lchild;
}
if(s->rchild!=NULL)
{
rear++;
queue[rear]=s->rchild;
}
}
}
}

/*************************************************\
函数功能:建立二叉树(按照顺序方式)
输入: 原始数组
输出: 二叉树的头结点
\*************************************************/
bitree* CreatBitree(int* arrayA,int n)//顺序存储 建立二叉树
{
bitree *root;
bitree *queue[maxsize];
bitree *p;
int front,rear;
front=1;rear=0;
root=NULL;

for(int i=1;i<n;i++)
{
p=(bitree*)malloc(sizeof(bitree));
p->data=arrayA[i];
p->lchild=NULL;
p->rchild=NULL;

rear++;
queue[rear]=p;

if(rear==1)
root=p;
else
{
if(i%2==0)
queue[front]->lchild=p;
else
{
queue[front]->rchild=p;
front=front+1;
}
}

}

return root;
}
坚持原创技术分享,您的支持将鼓励我继续创作!