（2）按层次输出所有结点
为了达到按层次扫描结点的目的， 需要设置一个容量足够大的循环队列 （可以用
一个首尾相接的一维数组模拟） 。初始时，将根结点序号入队。然后每次从队列
中退出一个结点序号， 将此结点的值及左右链指针输出， 且依次将此结点的左右
链指针入队。这个过程一直进行到队列空为止。设循环队列数组为 cq（1：m），
其头尾指针分别为 front 与 rear，则按层次输出所有结点的算法如下：
IF HBT = 0 THEN RETURN “ THIS TREE IS EMPTY”
Front m, rear m
ADD ( cq, HBT, front, rear )
WHILE front rear DO
{
DEL ( cq , i, front ,rear )
OUTPUT ( L( i ) , V( i ) ,R ( i ))
IF L( i ) 0 THEN ADD (cq , L( i ), front, rear)
IF R( i ) 0 THEN ADD (cq , R( i ), front, rear)
}
RETURN
在这个算法中的 ADD 和 DEL 分别为入队和退队运算的两个过程 ,其算法 (不
考虑溢出情况 )如下：
ADD （ cq，i，front ，rear）
rear rear + 1
IF rear = m + 1 THEN rear 1
cq （rear） i
RETURN
DEL (cq, i, front, rear )
front front + 1
IF front = m+ 1 THEN font 1
i cq (front )
RETURN
（3）输出所有叶子结点
叶子结点的左右指针域均为零。 因此，为了输出所有叶子结点， 需要设置一个容
量足够大的栈 S（可以用一个一维数组模拟它，栈底在数组的第一个元素处） 。
具体过程是： 从根结点开始扫描二叉树， 如果扫描的当前结点的左右均为零， 则
输出次叶子结点； 否则将非零的右指针和左指针值推入堆栈。 然后从栈中退出一
个结点序号重新进行这个过程，直至栈空为止。其算法如下：
IF HBT = 0 THEN RETURN “THIS TREE IS EMTPY ”
top 0
PUSH （ S，HBT ，top）
WHILE top 0 DO
{
VIP享7折，此内容立减4.47元 
评论0
最新资源