河池学院：《数据结构》课程电子教案（PPT教学课件）第7章 树和二叉树 7.4 二叉树的层次遍历 7.5 二叉树的构造

二叉树的层次遍历7.4层次遍历过程7.4.1若二叉树非空（假设其高度为h），则层次遍历的过程如下：访问根结点（第1层）。1从左到右访问第2层的所有结点。从左到右访问第3层的所有结点、…、第h层的所有结点。31/31

若二叉树非空（假设其高度为h），则层次遍历的过程如下： ① 访问根结点（第1层）。 ② 从左到右访问第2层的所有结点。 ③ 从左到右访问第3层的所有结点、.、第h层的所有结点。 1/31

层次遍历序列为ABCDEFG2/31

A B C D E F G 层次遍历序列为ABCDEFG 2/31

7.4.2月层次遍历算法设计在二叉树层次遍历中，对一层的结点访问完后，再按照它们的访问次序对各个结点的左、右孩子顺序访问，这样一层一层进行，先访问的结点其左，右孩子也要先访问，这样与队列的先进先出特点吻合。因此层次遍历算法采用一个队列qu来实现。思路：先将根结点b进队，在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有左孩子结点，将左孩子结点进队。如此操作直到队空为止。3/31

在二叉树层次遍历中，对一层的结点访问完后，再按照它们的访问次序对 各个结点的左、右孩子顺序访问，这样一层一层进行，先访问的结点其左、 右孩子也要先访问，这样与队列的先进先出特点吻合。因此层次遍历算法 采用一个队列qu来实现。 思路：先将根结点b进队，在队不空时循环：从队列中出队一个结点p，访 问它；若它有左孩子结点，将左孩子结点进队；若它有左孩子结点，将左 孩子结点进队。如此操作直到队空为止。 3/31

//层次遍历的算法public void Levelorder(BTreeclass bt)BTNodep;Queuequ=newLinkedList（）；//定义一个队列qu1/根结点进队qu.offer(bt.b);//队不空循环while(!qu.isEmpty())//出队一个结点(p=qu.poll();//访间p结点System.out.print(p.data+"");//有左孩子时将其进队if (p.lchild!=null)qu.offer(p.lchild);1/有右孩子时将其进队if (p.rchild!=null)qu.offer(p.rchild);与先序遍历非递归算法有哪些不同？4/31

public void LevelOrder(BTreeClass bt) //层次遍历的算法 { BTNode p; Queue qu=new LinkedList(); //定义一个队列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); } } 与先序遍历非递归算法有哪些不同？ 4/31

层次遍历算法的应用7.4.3【例7.15】采用层次遍历方法设计例7.13的算法，即求二叉树中第k（1≤≤二又树高度）层的结点个数。531

【例7.15】采用层次遍历方法设计例7.13的算法，即求二叉树中第k （1≤k≤二叉树高度）层的结点个数。 5/31

解法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;//结点引用BTNodenode;1/构造方法publicQNode(intl,BTNodeno)lno=l;node=no;Queuequ=newLinkedList()；|/定义一个队列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 node; //结点引用 public QNode(int l,BTNode no) //构造方法 { lno=l; node=no; } } Queue qu=new LinkedList(); //定义一个队列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 /定义队列quQueuequ=newLinkedList();BTNode p,q=null;int curl=l;1/当前层次，从1开始//当前层中最右结点BTNodelast;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 qu=new LinkedList(); //定义队列qu BTNode p,q=null; int curl=1; //当前层次,从1开始 BTNode 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