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

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

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

在二叉树层次遍历中，对一层的结点访问完后，再按照它们的访问次序对 各个结点的左、右孩子顺序访问，这样一层一层进行，先访问的结点其左、 右孩子也要先访问，这样与队列的先进先出特点吻合。因此层次遍历算法 采用一个队列qu来实现。 思路：先将根结点b进队，在队不空时循环：从队列中出队一个结点p，访 问它；若它有左孩子结点，将左孩子结点进队；若它有左孩子结点，将左 孩子结点进队。如此操作直到队空为止。 3/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.15】采用层次遍历方法设计例7.13的算法，即求二叉树中第k （1≤k≤二叉树高度）层的结点个数。 5/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

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 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有左孩子q，将结点q进队，有右孩子q，将结点q进队（总 是用q表示进队的结点）。 （4）若结点p是当前层的最右结点（p=last），说明当前层处理完毕， 而此时的q就是下一层的最右结点，置last=q，curl++进入下一层处理。 9/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