解法1用cnt变量计第层结点个数（初始为）。设计队列中元素类型为QNode类，包含表示当前结点层次lno和结点引用node两个成员变量。先将根结点进队（根结点的层次为1）。在层次遍历中出队一个结点p：（1）若结点p层次大于k，返回cnt（继续层次遍历不可能再找到第k层的结点）。（2）若结点p是第k层的结点（p.lno=k），cnt增1（3）若结点p的层次小于R，将其孩子结点进队，孩子结点的层次为双亲结点的层次加1。最后返回cnt。6/31
解法1 用cnt变量计第k层结点个数（初始为0）。设计队列中元素类型为 QNode类，包含表示当前结点层次lno和结点引用node两个成员变量。先将 根结点进队（根结点的层次为1）。在层次遍历中出队一个结点p： （1）若结点p层次大于k，返回cnt（继续层次遍历不可能再找到第k层 的结点）。 （2）若结点p是第k层的结点（p.lno=k），cnt增1。 （3）若结点p的层次小于k，将其孩子结点进队，孩子结点的层次为双亲 结点的层次加1。 最后返回cnt。 6/31
1/解法1public static int KCount2(BTreeclass bt,int k)( int cnt=o;/1累计第k层结点个数1/队列元素类（内部类）class QNode//结点的层次广int Ino;//结点引用BTNode<Character>node;1/构造方法publicQNode(intl,BTNode<character>no)lno=l;node=no;Queue<QNode>qu=newLinkedList<QNode>()；|/定义一个队列quQNode p;//根结点（层次为1）进队qu.offer(new QNode(1,bt.b));//队不空循环while(!qu.isEmpty())1/出队一个结点p=qu.poll();//当前结点的层次大于k，返回if (p.lno>k)return cnt;if (p.lno==k) cnt++;//当前结点是第k层的结点，cnt增1else//当前结点的层次小于k1/有左孩子时将其进队(if(p.node.lchild!=null)qu.offer(new QNode(p.lno+1,p.node.lchild));if (p.node.rchild!=null)1/有右孩子时将其进队qu.offer(newQNode(p.lno+1,p.node.rchild));return cnt;731
public static int KCount2(BTreeClass bt,int k) //解法1 { int cnt=0; //累计第k层结点个数 class QNode //队列元素类（内部类） { int lno; //结点的层次 BTNode<Character> node; //结点引用 public QNode(int l,BTNode<Character> no) //构造方法 { lno=l; node=no; } } Queue<QNode> qu=new LinkedList<QNode>(); //定义一个队列qu QNode p; qu.offer(new QNode(1,bt.b)); //根结点(层次为1)进队 while (!qu.isEmpty()) //队不空循环 { p=qu.poll(); //出队一个结点 if (p.lno>k) //当前结点的层次大于k，返回 return cnt; if (p.lno==k) cnt++; //当前结点是第k层的结点,cnt增1 else //当前结点的层次小于k { if (p.node.lchild!=null) //有左孩子时将其进队 qu.offer(new QNode(p.lno+1,p.node.lchild)); if (p.node.rchild!=null) //有右孩子时将其进队 qu.offer(new QNode(p.lno+1,p.node.rchild)); } } return cnt; } 7/31
解法2层次遍历中某层的最右结点lastlastlast的作用确定一层是否遍历完成！8/31
解法2 A B C D E F G 层次遍历中某层的最右结点last last A B C D E F G last的作用确定一层是否遍历完成！ 8/31
用cnt变量计第k层结点个数（初始为0）。设计队列仅保存结点引用，置当前层次curl=1，用last变量指示当前层次的最右结点（根结点）进队将根结点进队，队不空循环：（1）若curl>k，返回cnt（继续层次遍历不可能再找到第k层的结点）（2）否则出队结点p，若curl=k，表示结点p是第k层的结点，cnt增1。（3）若结点p有左孩子9，将结点g进队，有右孩子9，将结点q进队（总是用q表示进队的结点）。（4）若结点p是当前层的最右结点（p=last），说明当前层处理完毕，而此时的g就是下一层的最右结点，置1ast=q，curl++进入下一层处理。931
用cnt变量计第k层结点个数（初始为0）。设计队列仅保存结点引用， 置当前层次curl=1，用last变量指示当前层次的最右结点（根结点）进队。 将根结点进队，队不空循环： （1）若curl>k，返回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++进入下一层处理。 9/31
1/解法2public static int Kcount3(BTreeclass bt,int k)//累计第k层结点个数int cnt=o;广1 /定义队列quQueue<BTNode>qu=newLinkedList<BTNode>();BTNode<Character> p,q=null;int curl=l;1/当前层次，从1开始//当前层中最右结点BTNode<Character>last;last=bt.b;1/第1层最右结点//根结点进队qu.offer(bt.b);//队不空循环while（!qu.isEmpty()){ if (curl>k) return cnt;1/当层号大于k时返回cnt1/出队一个结点p=qu.poll();//是第k层的结点，cnt增1if (curl==k) cnt++;if(p.lchild!=null)1/有左孩子时将其进队q=p.lchild;qu.offer(q);)1/有右孩子时将其进队if(p.rchild!=null)q=p.rchild; qu.offer(q);)if//当前层的所有结点处理完毕(p==last)last=q;1/让last指向下一层的最右结点+curl++;return cnt;10/31
public static int KCount3(BTreeClass bt,int k) //解法2 { int cnt=0; //累计第k层结点个数 Queue<BTNode> qu=new LinkedList<BTNode>(); //定义队列qu BTNode<Character> p,q=null; int curl=1; //当前层次,从1开始 BTNode<Character> last; //当前层中最右结点 last=bt.b; //第1层最右结点 qu.offer(bt.b); //根结点进队 while (!qu.isEmpty()) //队不空循环 { if (curl>k) return cnt; //当层号大于k时返回cnt p=qu.poll(); //出队一个结点 if (curl==k) cnt++; //是第k层的结点,cnt增1 if (p.lchild!=null) //有左孩子时将其进队 { q=p.lchild; qu.offer(q); } if (p.rchild!=null) //有右孩子时将其进队 { q=p.rchild; qu.offer(q); } if (p==last) //当前层的所有结点处理完毕 { last=q; //让last指向下一层的最右结点 curl++; } } return cnt; } 10/31