二叉树的层次遍历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)BTNode<Character>p;Queue<BTNode>qu=newLinkedList<BTNode>（）；//定义一个队列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<Character> p; Queue<BTNode> qu=new LinkedList<BTNode>(); //定义一个队列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