基于队列的任意二叉树层次问题算法设计

吴 志 福

(石家庄职业技术学院 组织部，河北 石家庄 050081)

在数据结构中，树是一种用途广泛的结构.二叉树是每个节点最多有两个子树的树结构.在对任意二叉树进行存储的时候，普遍采用链式结构存储数据，在对链式结构存储的任意二叉树进行操作的时候，常采用递归的方法来实现.在求任意二叉树的层次问题上，也采用递归方法来实现.但递归方式算法复杂且不容易理解.对任意二叉树的研究发现，对于涉及到任意二叉树层次的计算，由于其结构的特殊性，完全可以使用比较容易理解的队列来解决.

1 二叉树的存储结构

二叉树的存储方式有顺序结构和链式结构两种[1].在任意二叉树的顺序存储结构中，采用数组存放任意二叉树的节点.二叉树层次和数组下标表示为：

M=log2(n+1).

其中，M表示二叉树层次，n表示数组的最大下标.

图1为任意二叉树结构示意图.采用顺序结构存储时，利用数组存储的结果见表1.

图1 任意二叉树结构示意图

数组下标存放节点数组下标存放节点数组下标存放节点1B14B47B52B25空8B63B36空︙︙

从表1可以看出，虽然采用顺序结构存储的任意二叉树可以利用公式很方便地计算出任意二叉树层次，但是利用数组存储数据时，会存在大量空节点，造成空间的浪费，因此任意二叉树存储一般不采用顺序结构而采用链式结构.

在采用链式结构存储任意二叉树时，由于二叉树的每个结点最多有左右两个孩子，因此，每个结点除了存储自身的数据外，还设置两个指针分别指向左孩子、右孩子的结点.链式结构任意二叉树存储结点示意图见图2.

左孩子地址节点数据右孩子地址

图2链式结构任意二叉树存储结点示意图

对于图1所示任意二叉树，其B1-B4节点的链式存储结构如图3所示.

(1)B1节点存储结构

(2)B2节点存储结构

(3)B3节点存储结构

(4)B4节点存储结构

图3任意二叉树节点的链式存储结构示意图

链式结构存储保留了任意二叉树的结构，且不存在空间浪费问题，但是无法通过公式来计算二叉树的层次，只能采用递归的方式遍历二叉树进而求得层次.由于递归涉及到调用时空间的开辟、现场的保存、参数的传递等问题，算法较难理解，因此需要寻找合适的算法求链式结构任意二叉树的层次.

2 算法设计

2.1 设计思路

在计算链式结构存储的任意二叉树层次的过程中，需要遍历整个任意二叉树，即需要处理多个相同结构的数据，为了便于数据的处理，减少空间的浪费，采用队列结构来实现层次算法.在使用队列求任意二叉树层次时，算法中仅增加了一个队列和一个顺序结构的数组[2]，没有增加太多的空间，但却减少了递归调用时空间的开辟.

队列是常用的一种数据结构，其特点是“先进先出”，即删除操作只允许在队列的前端进行，插入操作只在队列的后端进行，进行插入操作的端称为队尾，进行删除操作的端称为队头，所以先进入队列的元素总是先被删除的.利用队列这一特点，对采用链式结构存储的任意二叉树按照层次关系将其节点进行入队和出队操作，将其从逻辑关系上转变为线性结构，在转变的过程中，利用辅助数组记录任意二叉树的层次.当转变完成时，任意二叉树的层次也就得以保存.

在用队列实现二叉树的层次问题时，让根节点首先入队，继续进行操作的时候，节点出队的同时如果它的左孩子或右孩子不为空，循环操作将其入队.这样，每一层的节点将按照先左后右的顺序入队.由于节点的地址之间没有固定的线性关系，因此利用一个辅助数组来记住每一层的最左节点在队列中的位置，在队列不为空的时候将队头元素出队，同时重复前面的入队操作.由于节点在不断地入队和出队，所以记录节点位置的辅助数组的长度要不小于二叉树的最大宽度.

2.2 设计程序

在算法设计过程中，队列采用结构体来表示，结构为：

struct queue /* 队列*/

{

struct bitree *elem[MAXSIZE]; /* bitree为链式存储的任意二叉树的节点类型*/

int front,rear; /*头指针和尾指针*/

}

为了节省空间，减少系统的空间开销，队列中只保存了指向链式存储的任意二叉树的节点的指针，而没有保存其数据.

对图1所示任意二叉树进行遍历的过程如下：

根节点B1首先入队.此时队列中的数据如图4所示.

0节点B11

图4根节点B1入队后队列示意图

此时，辅助数组fuzhu[ ]中保存元素全部初始化为0，辅助数组下标j初始化为0，树的层次数k标记为0.为了标记是否是最左节点入队，初始化flag为0.

随后，在队列不为空的情况下进入队列的循环操作.

(1)队首元素B1出队，保存到变量P中.执行出队操作后，图4中数据变化见图5所示.

1节点B11

图5根节点B1出队后队列示意图

(2)判断p是否有左孩子或右孩子，且其左、右孩子是否为下一层的最左节点，如果是最左节点，则j增加1，k增加1，将下一层最左节点地址写入fuzhu[ ].

在图1中，节点B1有左孩子且其左孩子是下一层的最左节点，因此将j增加1，此时j的值为1，为fuzhu[j]写入下一层最左节点的值，此值即为图4中最右边的数据，即fuzhi[1].由于下一层的最左节点已经入队，因此更改flag值为1.

(3)判断已经出队节点是否为本层的最右节点，若是，则队列中首元素为下一层的最左节点，后续将开始下一层的出队和下下层的入队，因此更改flag值为0.

(4)判断p的左孩子是否不为空，如果不为空，则左孩子入队.

(5)判断p的右孩子是否不为空，如果不为空，则右孩子入队.

(6)继续返回开始步骤进行循环，直至队列为空.

对于图1的任意二叉树，其遍历至第三层的过程中，队列和对应辅助数组的变化过程如图6所示.

从图6中可以看出，随着任意二叉树节点的入队和出队，辅助数组中记录了每一层节点的最左节点，flag值记录了任意二叉树的层次.当循环结束时，flag的值就是任意二叉树的层次.

3 算法实现

算法中循环部分的C语言实现代码如下：

int cc(struct bitree *root)

/*求任意二叉树的最大层次数，二叉树采用链式存储结构*/

{

int fuzhi={0},j=0,k=1,flag=0;

struct queue *q;

struct bitree *p

inistilize(q);/*队列初始化*/

p=root;

enterque(q,p);/*根节点入队*/

while(! isempty(q)) /*队列非空*/

{

p=deleteque(q); /*队首元素出队*/

if (( p->lchild!=NULL ||p->rchild!=NULL) &&flag= =0)

/* flag 为0时，下一层还没有节点入队， 已经出队节点的孩子节点为下一层的最左节点*/

{

j++; /*辅助数组下标加1*/

flag=1;

/*将标志变为1，表示下一层已经有节点入队 */

fuzhi[j]=q->rear

/*下一层的最左节点的位置*/;

k++; /*层次数加1*/

}

if (q->front= =a[j])

/*已经出队节点为本层的最右节点*/

flag=0;

if (p->lchild!=NULL)

/*左孩子节点入队*/

enterqueue(q,p->lchild);

if(p->rchild!=NULL)

/*右孩子节点入队*/

enterqueue(q,p->rchild);

}

return(k); /*返回最大层次数*/

}

在此算法的具体设计中，对任意二叉树采用了链式存储结构，队列采用了顺序结构的循环队列，并且规定，当队列中只剩余一个空间时，队列满，即“尾指针+1”，对初始化的队列长度求余等于“头指针”时，队列满.队列的出队、入队、初始化等问题和循环队列的相同.文中不再给出树、队列的数据结构源代码和队列的出队、入队、初始化等的代码.

图6 算法过程队列及辅助数组变化示意图

4 结语

本算法的源程序已经在Visual C++6.0中通过调试，能解决求二叉树的最大层次问题.在解决实际问题的过程中，可以根据需要将程序加以改变，从而实现和层次相关问题的求解，如二叉树的树形输出、二叉树的最大宽度即层上节点的最大个数等问题，均可采用此算法.

参考文献：

[1] 严蔚敏，吴伟民．数据结构:C语言版[M]．北京：清华大学出版社，1997：126-127.

[2] 朱雅莉，李肯立.DNA计算机中基于顺序存储方式的二叉树数据结构[J].计算机应用，2008，28(6):1591-1594.