数据基础教程3

7.4.1层次遍历过程7.4二叉树的层次遍历若二叉树非空（假设其高度为h），则层次遍历的过程如下：①访问根结点（第1层）。②从左到右访问第2层的所有结点。③从左到右访问第3层的所有结点、…、第h层的所有结点。1/32ABCEFDG层次遍历序列为ABCDEFG2/327.4.2层次遍历算法设计在二叉树层次遍历中，对一层的结点访问完后，再按照它们的访问次序对各个结点的左、右孩子顺序访问，这样一层一层进行，先访问的结点其左、右孩子也要先访问，这样与队列的先进先出特点吻合。因此层次遍历算法采用一个队列qu来实现。算法思路：先将根结点b进队，在队不空时循环：从队列中出队一个结点p，访问它；若它有左孩子结点，将左孩子结点进队；若它有左孩子结点，将左孩子结点进队。如此操作直到队空为止。3/32publicvoidLevelOrder(BTreeClassbt){ //层次遍历的算法BTNode<Character>p;

Queue<BTNode>qu=newLinkedList<BTNode>();//定义一个队列ququ.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/327.4.3层次遍历算法的应用

【例7.15】采用层次遍历方法设计例7.13的算法，即求二叉树中第k（1≤k≤二叉树高度）层的结点个数。5/32解法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/32publicstaticintKCount2(BTreeClassbt,intk){//解法1intcnt=0; //累计第k层结点个数classQNode { //队列元素类（内部类）intlno; //结点的层次BTNode<Character>node; //结点引用publicQNode(intl,BTNode<Character>no){lno=l;node=no;}}7/32Queue<QNode>qu=newLinkedList<QNode>();//定义一个队列quQNodep;qu.offer(newQNode(1,bt.b)); //根结点(层次为1)进队while(!qu.isEmpty()){

//队不空循环p=qu.poll(); //出队一个结点if(p.lno>k) //当前结点的层次大于k，返回returncnt;if(p.lno==k)cnt++; //当前结点是第k层的结点,cnt增1else{ //当前结点的层次小于kif(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;}8/32解法2ABCEFDG层次遍历中某层的最右结点lastlastABCEFDGlast的作用确定一层是否遍历完成！9/32

用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++进入下一层处理。10/32publicstaticintKCount3(BTreeClassbt,intk){ //解法2intcnt=0; //累计第k层结点个数

Queue<BTNode>qu=newLinkedList<BTNode>();

//定义队列quBTNode<Character>p,q=null;intcurl=1; //当前层次,从1开始BTNode<Character>last; //当前层中最右结点last=bt.b; //第1层最右结点qu.offer(bt.b); //根结点进队while(!qu.isEmpty()){ //队不空循环if(curl>k)returncnt; //当层号大于k时返回cntp=qu.poll(); //出队一个结点if(curl==k)cnt++; //是第k层的结点,cnt增1if(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++;}}returncnt;}11/32解法3

层次遍历是从第一层开始，访问一层的全部结点后（此时该层的全部结点已出队）再访问下一层的结点。上一层遍历完毕，队中恰好是下一层的全部结点。若k<1，返回0；否则将根结点进队，当前层次curl=1。队不空循环：

（1）若curl=k，队中恰好包含该层的全部结点，直接返回队中元素个数（即第k层结点个数）。

（2）否则，求出队中元素个数n（当前层curl的全部结点个数），循环出队n次，每次出队一个结点时将其孩子结点进队。

（3）置curl++，进入下一层处理。

最后返回0（k>二叉树高度的情况）。12/32publicstaticintKCount4(BTreeClassbt,intk){ //解法3if(k<1)return0; //k<1返回0Queue<BTNode>qu=newLinkedList<BTNode>(); //定义队列quBTNode<Character>p,q=null;intcurl=1; //当前层次,从1开始qu.offer(bt.b); //根结点进队while(!qu.isEmpty()){ //队不空循环if(curl==k) //当前层为第k层返回cntreturnqu.size();intn=qu.size(); //求出当前层结点个数for(inti=1;i<=n;i++){ //出队当前层的n个结点p=qu.poll(); //出队一个结点if(p.lchild!=null) //有左孩子时将其进队qu.offer(p.lchild);if(p.rchild!=null) //有右孩子时将其进队qu.offer(p.rchild);}curl++; //转向下一层}return0;}13/327.5二叉树的构造7.5.1由先序/中序序列或后序/中序序列构造二叉树一棵所有结点值不同的二叉树，其先序、中序、后序和层次遍历都是唯一的，也就是说一棵这样的二叉树，不可以有两种不同的先序遍历序列，也不可能有两种不同的中序序列。二叉树的构造就是给定某些遍历序列，反过来唯一地确定该二叉树。14/32ABCABCABCABCABC(a)(b)(c)(d)(e)二叉树遍历序列图(a)的二叉树图(b)的二叉树图(c)的二叉树图(d)的二叉树图(e)的二叉树先序遍历序列ABCABCABCABCABC中序遍历序列BACBCAACBCBAABC后序遍历序列BCACBACBACBACBA15/32从中看到，对于不同形态的二叉树：先序遍历序列可能相同（图中5棵二叉树的先序遍历序列均相同）。中序遍历序列可能相同。后序遍历序列可能相同（图(b)～(e)的后序遍历序列均相同）先序遍历序列和后序遍历序列可能都相同（图(d)和(e)的先序遍历序列和后序遍历序列均相同）。ABCABCABCABCABC(a)(b)(c)(d)(e)16/32实际上，对于含2个或者以上结点的二叉树，在先序、中序和后序遍历序列中：由先序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由后序遍历序列和中序遍历序列能够唯一确定一棵二叉树。由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。17/32

定理7.1任何n（n≥0）个不同结点的二又树，都可由它的中序序列b和先序序列a唯一地确定。由a0（根结点）找到bk。若bk前面有k个结点，则左子树有k个结点，右子树有n-k-1个结点。可以求出左右子树的中序序列和先序序列。这样根结点是确定的，左右子树也是确定的，则该二叉树是确定的。左子树先序序列，有k个结点右子树先序序列，有n-k-1个结点先序序列：a0

a1…ak

ak+1…an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1…bk-1bk

bk+1…bn-1通过根结点a0在中序序列中找到bk18/32已知先序序列为ABDGCEF，中序序列为DGBAECF，则构造二叉树的过程：根结点：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根结点：B左先序:DG左中序:DG右先序:空右中序:空根结点：D左先序:空左中序:空右先序:G右中序:G根结点：G左先序:空左中序:空右先序:空右中序:空根结点：C左先序:E左中序:E右先序:F右中序:F根结点：E左先序:空左中序:空右先序:空右中序:空根结点：F左先序:空左中序:空右先序:空右中序:空19/32publicstaticBTreeClassCreateBT1(Stringpre,Stringin){

//由先序序列pre和中序序列in构造二叉链BTreeClassbt=newBTreeClass();bt.b=CreateBT11(pre,0,in,0,pre.length());returnbt;}20/32privatestaticBTNode<Character>CreateBT11(Stringpre,inti, Stringin,intj,intn){BTNode<Character>t;charch;intp,k;if(n<=0)returnnull;ch=pre.charAt(i);t=newBTNode<Character>(ch); //创建根结点(结点值为ch)p=j; //p指中序序列的开始元素while(p<j+n){ //在in中找等于ch的位置pif(in.charAt(p)==ch) break;p++;}由先序序列pre[i..i+n-1]和中序序列in[j..j+n-1]创建二叉链t21/32k=p-j; //确定左子树中结点个数kt.lchild=CreateBT11(pre,i+1,in,j,k); //递归构造左子树t.rchild=CreateBT11(pre,i+k+1,in,p+1,n-k-1);//递归构造右子树returnt;}先序pre：a0

a1

…

ak-1ak

ak+1…

an-2an-1中序in：b0

b1

…

bk-1bk

bk+1…

bn-2

bn-1pi+1i+k+1p+1ji22/32

定理7.2

任何n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列唯一地确定。左子树后序序列，有k个结点右子树后序序列，有n-k-1个结点后序序列：a0

a1

…

ak-1

ak

…an-2

an-1左子树中序序列，有k个结点右子树中序序列，有n-k-1个结点中序序列：b0

b1

…bk-1

bk

bk+1

…

bn-1通过根结点an-1在中序序列中找到bk由an-1（根结点）找到bk。若bk前面有k个结点，则左子树有k个结点，右子树有n-k-1个结点。可以求出左右子树的中序序列和后序序列。这样根结点是确定的，左右子树也是确定的，则该二叉树是确定的。23/32已知中序序列为DGBAECF，后序序列为GDBEFCA，则构造二叉树的过程根结点：A左中序:DGB左后序:GDB右中序:ECF右后序:EFC根结点：B左中序:DG左后序:GD右中序:空右后序:空根结点：D左中序:空左后序:空右中序:G右后序:G根结点：G左中序:空左后序:空右中序:空右后序:空根结点：C左中序:E左后序:E右中序:F右后序:F根结点：E左中序:空左后序:空右中序:空右后序:空根结点：F左中序:空左后序:空右中序:空右后序:空24/32publicstaticBTreeClassCreateBT2(Stringpost,Stringin){//由后序序列post和中序序列in构造二叉链BTreeClassbt=newBTreeClass();bt.b=CreateBT22(post,0,in,0,post.length());returnbt;}25/32privatestaticBTNode<Character>CreateBT22(Stringpost,inti, Stringin,intj,intn){BTNode<Character>t;charch;intp,k;if(n<=0)returnnull;ch=post.charAt(i+n-1); //取后序序列尾元素t=newBTNode<Character>(ch); //创建根结点(结点值为ch)p=j; //p指中序序列的开始元素while(p<j+n){ //在中序序列中找根位置pif(in.charAt(p)==ch)break; //在in中找到根后退出p++;}k=p-j; //确定左子树中结点个数kt.lchild=CreateBT22(post,i,in,j,k); //递归构造左子树t.rchild=CreateBT22(post,i+k,in,p+1,n-k-1);//递归构造右子树returnt;}由后序序列post[i..i+n-1]和中序序列in[j..j+n-1]创建二叉链t26/32

【例7.17】若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？二叉树的先序序列是NLR，后序序列是LRN。NLR=LRN则L和R均为空。所以满足条件的二叉树只有一个根结点。27/327.5.2*序列化和反序列化ABCEFDG仅仅讨论先序遍历序列化和反序列化。ABCEFDG########加上外部结点"ABD#G###CE##F##"先序遍历序列化序列28/32publicstaticStringPreOrderSeq(BTreeClassbt){ //二叉树bt的序列化returnPreOrderSeq1(bt.b);}privatestaticStringPreOrderSeq1(BTNode<Character>t){Strings="",s1,s2;if(t==null)return