第7章树和二叉树（4）.pptx

7.4.1层次遍历过程;;7.4.2层次遍历算法设计;publicvoidLevelOrder(BTreeClassbt) //层次遍历的算法

{BTNodeCharacterp;

QueueBTNodequ=newLinkedListBTNode();//定义一个队列qu

qu.offer(bt.b); //根结点进队

while(!qu.isEmpty()) //队不空循环

{p=qu.poll(); //出队一个结点

System.out.print(p.data+); //访问p结点

if(p.lchild!=null) //有左孩子时将其进队

qu.offer(p.lchild);

if(p.rchild!=null) //有右孩子时将其进队

qu.offer(p.rchild);

}

};7.4.3层次遍历算法的应用;解法1;publicstaticintKCount2(BTreeClassbt,intk) //解法1

{intcnt=0; //累计第k层结点个数

classQNode //队列元素类（内部类）

{intlno; //结点的层次

BTNodeCharacternode; //结点引用

publicQNode(intl,BTNodeCharacterno) //构造方法

{lno=l; node=no;}

}

QueueQNodequ=newLinkedListQNode();//定义一个队列qu

QNodep;

qu.offer(newQNode(1,bt.b)); //根结点(层次为1)进队

while(!qu.isEmpty()) //队不空循环

{p=qu.poll(); //出队一个结点

if(p.lnok) //当前结点的层次大于k，返回

returncnt;

if(p.lno==k)cnt++; //当前结点是第k层的结点,cnt增1

else //当前结点的层次小于k

{if(p.node.lchild!=null) //有左孩子时将其进队

qu.offer(newQNode(p.lno+1,p.node.lchild));

if(p.node.rchild!=null) //有右孩子时将其进队

qu.offer(newQNode(p.lno+1,p.node.rchild));

}

}

returncnt;

};解法2;用cnt变量计第k层结点个数（初始为0）。设计队列仅保存结点引用，置当前层次curl=1，用last变量指示当前层次的最右结点（根结点）进队。将根结点进队，队不空循环：

（1）若curlk，返回cnt（继续层次遍历不可能再找到第k层的结点）。

（2）否则出队结点p，若curl=k，表示结点p是第k层的结点，cnt增1。

（3）若结点p有左孩子q，将结点q进队，有右孩子q，将结点q进队（总是用q表示进队的结点）。

（4）若结点p是当前层的最右结点（p=last），说明当前层处理完毕，而此时的q就是下一层的最右结点，置last=q，curl++进入下一层处??。;publicstaticintKCount3(BTreeClassbt,intk) //解法2

{intcnt=0; //累计第k层结点个数

QueueBTNodequ=newLinkedListBTNode(); //定义队列qu

BTNodeCharacterp,q=null;

intcurl=1; //当前层次,从1开始

BTNodeCharacterlast; //当前层中最右结点

last=bt.b; //第1层最右结点

qu.offer(bt.b); //根结点进队

while(!qu.isEmpty()) //队不空循环

{if(curlk)returncnt; //当层号大于k时返回cnt

p=qu.poll(); //出队一个结点

if(curl==k)cnt++; //是第k层的结点,cnt增1

if(