数据结构教程（Java语言描述）（第2版 微课视频版） 课件 第7章 树和二叉树

第7章树和二叉树7.1树7.2二叉树CONTENTS提纲7.3二叉树先序、中序和后序遍历7.4二叉树的层次遍历7.5二叉树的构造7.6线索二叉树7.8二叉树与树、森林之间的转换7.7哈夫曼树7.9树算法设计和并查集1/36树是由n（n≥0）个结点组成的有限集合（记为T）。如果n=0，它是一棵空树，这是树的特例。如果n>0，这n个结点中存在（有仅存在）一个结点作为树的根结点（root），其余结点可分为m（m≥0）个互不相交的有限集T1、T2、…、Tm，其中每个子集本身又是一棵符合本定义的树，称为根结点的子树。7.1.1树的定义7.1树2/36树是一种非线性数据结构，具有以下特点：每一结点可以有零个或多个后继结点，但有且只有一个前驱结点（根结点除外）。数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。3/36ADTTree{

数据对象：

D={ai

|0≤i≤n-1，n≥0，ai为E类型}

数据关系：

R={r} r={<ai，aj>|ai，aj∈D，0≤i，j≤n-1，其中每个结点最多只有一个

前驱结点、可以有零个或多个后继结点，有且仅有一个结点即根

结点没有前驱结点}

基本运算： boolCreateTree()：由树的逻辑结构表示建立其存储结构。 StringtoString()：返回由树转换的括号表示串。 EGetParent(inti)：求编号为i的结点的双亲结点值。

…}抽象数据类型树的描述4/367.1.2树的逻辑结构表示方法树形表示法。这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。ABCDEFHG5/36文氏图表示法。使用集合以及集合的包含关系描述树结构。ABCDEFHG6/36凹入表示法。使用线段的伸缩关系描述树结构。ABCDEFHG7/36括号表示法。将树的根结点写在括号的左边，除根结点之外的其余结点写在括号中并用逗号分隔。A(B,C(E(H),F),D(G))ABCDEFHG根(子树1，子树2，…，子树m）8/367.1.3树的基本术语度为3度为1结点的度。树中每个结点具有的子树数或者后继结点数称为该结点的度。ABCDEFHG9/36树的度。树中所有结点的度的最大值称之为树的度。树的度为3ABCDEFHG10/36分支结点。度大于0的结点称为分支结点或非终端结点。度为1的结点称为单分支结点，度为2的结点称为双分支结点，依次类推。ABCDEFHGA、C、D、E为分支结点11/36叶子结点（或叶结点）。度为零的结点称为叶子结点或终端结点。ABCDEFHGB、H、F、G为叶子结点12/36孩子结点。一个结点的后继称之为该结点的孩子结点。结点A的孩子结点为B、C和DABCDEFHG13/36双亲结点（或父亲结点）。一个结点称为其后继结点的双亲结点。结点E和F的双亲结点均为CABCDEFHG14/36子孙结点。一个结点的子树中除该结点外的所有结点称之为该结点的子孙结点。ABCDEFHG结点C结点的子孙结点为E、F和H15/36祖先结点。从树根结点到达某个结点的路径上通过的所有结点称为该结点的祖先结点（不含该结点自身）。ABCDEFHG结点F的祖先结点为A、C16/36兄弟结点。具有同一双亲的结点互相称之为兄弟结点。结点E和F是兄弟结点ABCDEFHG17/36结点层次。树具有一种层次结构，根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层次。1234ABCDEFHG18/36树的高度。树中结点的最大层次称为树的高度或深度。1234ABCDEFHG高度是419/36森林。零棵或多棵互不相交的树的集合称为森林。ABCDEFHG4棵树构成的森林20/367.1.4树的性质性质1：

树中的结点数等于所有结点的度数加1。度之和=分支数分支数=n-1所以，n=度之和+1ABCDEFHGABCDEFHG21/36性质2：度为m的树中第i层上至多有mi-1个结点，这里应有i≥1。数学归纳法证明

当一棵m次树的第i层有mi-1个结点（i≥1）时，称该层是满的，若一棵m次树的所有叶子结点在同一层，所有层都是满的，称为满m次树。显然，满m次树是所有相同高度的m次树中结点总数最多的树。也可以说，对于n个结点，构造的m次树为满m次树或者接近满m次树，此时树的高度最小。推广22/36性质3：

高度为h的m次树至多有个结点。由性质2推出23/36性质4：具有n个结点的m次树的最小高度为

logm(n(m-1)+1)

。

证明：设具有n个结点的m次树的最小高度为h，若在该树中前h-1层都是满的，即每一层的结点数都等于mi-1个（1≤i≤h-1），第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的高度。其高度h可计算如下：h层全满高度为h，结点个数最多的情况h-1层满高度为h，结点个数最少的情况+124/36根据树的性质3可得：<

n≤乘(m-1)后得：

mh-1<n(m-1)+1≤

mh以m为底取对数后得：

h-1<logm(n(m-1)+1)≤

h即 logm(n(m-1)+1)≤

h<logm(n(m-1)+1)+1因h只能取整数，所以h=

logm(n(m-1)+1)

，结论得证。25/36

【例7.1】若一棵三次树中度为3的结点为2个，度为2的结点为1个，度为1的结点为2个，则该三次树中总的结点个数和度为0的结点个数分别是多少？

设该三次树中总结点个数、度为0的结点个数、度为1的结点个数、度为2的结点个数和度为3的结点个数分别为n、n0、n1、n2和n3。

显然，每个度为i的结点在所有结点的度数之和中贡献i个度。依题意有：n1=2，n2=1，n3=2。由树的性质1可知

n=所有结点的度数之和+1

=0×n0+1×n1+2×n2+3×n3+1=1×2+2×1+3×2+1=11又因为n=n0+n1+n2+n3即：n0=n-n1-n2-n3=11-2-1-2=6所以该三次树中总的结点个数和度为0的结点个数分别是11和6。26/367.1.5树的基本运算树的运算主要分为三大类：查找满足某种特定关系的结点，如寻找当前结点的双亲结点等；插入或删除某个结点，如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；遍历树中每个结点。27/36

树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。

有以下3种遍历方法：

先根遍历后根遍历层次遍历1.树的遍历28/36先根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。层次遍历:若树不空，则自上而下自左至右访问树中每个结点。先根和后根遍历算法都是递归的。注意29/36ABCDEFGHJIK先根遍历的顶点访问次序：ABEFCDGHIJK后根遍历的顶点访问次序：EFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK30/367.1.6树的存储结构1.双亲存储结构

这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有结点，同时在每个结点中附设一个伪指针指示其双亲结点的位置。ABCDEFHG位置dataparent0A-11B02C03D04E25F26G37H431/36classPTree<E> { //双亲存储结构结点类Edata; //存放结点的值intparent; //存放双亲的位置}PTree<E>[]t; //双亲存储结构t双亲存储结构中结点类PTree利用了每个结点（根结点除外）只有唯一双亲的性质。这种存储结构中，求某个结点的双亲结点十分容易，但求某个结点的孩子结点时需要遍历整个结构。优缺点32/362.孩子链存储结构孩子链存储结构可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域个数。ABCFDEGA∧BC∧∧∧D∧∧∧E∧∧G∧∧∧F∧∧∧33/36孩子链存储结构的结点类TSonNodeclassTSonNode<E>{

//孩子链存储结构结点类Edata; //结点的值TSonNode<E>[]sons; //指向孩子结点}孩子链存储结构的优点是查找某结点的孩子结点十分方便。缺点是查找某结点的双亲结点比较费时。当树的度较大时，存在较多的空指针域，可以证明含有n个结点的m次树采用孩子链存储结构时有mn-n+1个空指针域。优缺点34/363.孩子兄弟链存储结构

孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域，一个指向该结点的第一个孩子结点的指针域，一个指向该结点的下一个兄弟结点指针域。ABCFDEGA∧BD∧G∧∧C∧∧EF∧∧35/36兄弟链存储结构中结点类TSBNode定义如下：classtTSBNode<E>{

//孩子兄弟链存储结构中结点类Edata; //结点的值TSBNode<E>hp; //指向兄弟TSBNode<E>vp; //指向孩子结点}孩子兄弟链存储结构的最大优点是可以方便地实现树和二叉树的相互转换。缺点和孩子链存储结构的缺点一样：就是从当前结点查找双亲结点比较麻烦，需要从树的根结点开始逐个结点比较查找。优缺点36/36二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。7.2.1二叉树的概念7.2二叉树1.二叉树的定义37/35度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。提示二叉树与度为2的树是不同的。38/35归纳起来，二叉树的5种形态：Ø(a)空二叉树(b)只有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树非空的二叉树39/35ADTBTree{

数据对象： D={ai|1≤i≤n，n≥0，ai为E类型}//为了简单，假设E为char

数据关系： R={r} r={<ai，aj>|ai，aj∈D，1≤i，j≤n，当n=0时，称为空二叉树；

否则其中有一个根结点，其他结点构成根结点的互不相交的左、右子

树，该左、右两棵子树也是二叉树}

基本运算： voidCreateBTree(stringstr)：由二叉树括号表示串建立其存储结构。 StringtoString()：返回由二叉树树转换的括号表示串。 BTNodeFindNode(x)：在二叉树中查找值为x的结点。 intHeight()：求二叉树的高度。

…}2.二叉树抽象数据类型的描述40/353.满二叉树和完全二叉树在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行。满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2h-1个结点的二叉树称为满二叉树。ABDHIEJKCFLMGNO12489510113612137141541/35满二叉树的特点如下：叶子结点都在最下一层。只有度为0和度为2的结点。含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为

n/2

+1，度为2的结点个数为

n/2

。ABDHIEJKCFLMGNO124895101136121371415n=15h=log2(n+1)=442/35若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。ABDHIEJKCFG124895101136743/35完全二叉树的特点如下：叶子结点只可能出现在最下面两层中。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子；按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。ABDHIEJKCFG124895101136744/357.2.2二叉树性质性质1

非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。总结点数n=n0+n1+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则n1+2n2=n0+n1+n2-1，求出n0=n2+1。证明：在二叉树中计算结点时常用的关系式有：①所有结点的度之和=n-1②所有结点的度之和＝n1＋2n2

③n=n0+n1+n2。归纳45/35性质2

非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

由树的性质2可推出。性质3

高度为h的二叉树至多有2h-1个结点（h≥1）。

由树的性质3可推出。46/35性质4对完全二叉树中层序编号为i的结点（1≤i≤n，n≥1）有：

（1）若i≤

n/2

，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。

（2）若n为奇数，则n1=0，这样每个分支结点都是双分支结点；若n为偶数，则n1=1，只有一个单分支结点，该单分支结点是编号最大的分支结点（编号为

n/2

）。

（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i+1。

（4）若编号为i的结点有双亲结点，其双亲结点的编号为

i/2

。i/2i2i2i+147/35

性质5

具有n个（n＞0）结点的完全二叉树的高度为

log2(n+1)

或

log2n

+1。

由完全二叉树的定义和树的性质3可推出。一棵完全二叉树中，由结点总数n可以确定其树形。n1只能是0或1，当n为偶数时，n1=1，当n为奇数时，n1=0。层序编号为i的结点层次恰好为

log2(i+1)

或者

log2i

+1。归纳48/35

【例7.2】一棵含有882个结点的二叉树中有365个叶子结点，求度为1的结点个数和度为2的结点个数。这里n=882，n0=365。由二叉树的性质1可知n2=n0-1=364。n=n0+n1+n2，即n1=n-n0-n2=882-365-364=153。所以该二叉树中度为1的结点和度为2的结点个数分别是153和364。49/35【例7.5】一棵完全二叉树中有501个叶子结点，则至少有多少个结点。该二叉树中有，n0=501。由二叉树性质1可知n0=n2+1，所以n2=n0-1=500。n=n0+n1+n2=1001+n1，由于完全二叉树中n1=0或n1=1，则n1=0时结点个数最少，此时n=1001，即至少有1001个结点。50/357.2.3二叉树存储结构1.二叉树的顺序存储结构顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。由二叉树的性质4可知，对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。51/35一棵完全二叉树的顺序存储结构1234567891011121314…ABCDEFGHIJK####位置sbABDHIEJKCFG124895101136752/35ABDEGHCFKABDEGHCFK1248951011361271413增添空结点补齐为一棵完全二叉树并对所有结点进行编号一般的二叉树的顺序存储结构设计：53/351234567891011121314…ABCDE#F##GH##K#位置sb仅保留实际存在的结点值，其他为空ABDEGHCFK124895101136127141354/35

二叉树顺序存储结构采用这样的数组存放（假设每个结点值为单个字符）：

Stringsb; //二叉树的顺序存储结构用sb字符串存储

当二叉树中某结点为空结点或无效结点（不存在该编号的结点）时，对应位置的值用特殊值（如'#'）表示。55/35完全二叉树或满二叉树采用顺序存储结构比较合适如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。h=4MazSize=24-1=15空间利用率=4/15=27%优缺点56/352.二叉树的链式存储结构ABCEFDG二叉链存储结构AB∧C∧D∧E∧∧G∧∧F∧b57/35对应Java语言的二叉链结点类BTNode<E>classBTNode<E>{

//二叉链中结点类Edata; //存放数据元素BTNodelchild; //指向左孩子结点BTNoderchild; //指向右孩子结点publicBTNode(){

//默认构造方法lchild=rchild=null;}publicBTNode(Ed){

//重载构造方法data=d;lchild=rchild=null;}}58/357.2.4二叉树的递归算法设计对于二叉树b，设f(b)是求解的“大问题”。f(b->lchild)和f(b->rchild)为“小问题”。假设f(b->lchild)和f(b->rchild)是可求的，在此基础上得出f(b)和f(b->lchild)、f(b->rchild)之间的关系，从而得到递归体。再考虑b=NULL或只有一个结点的特殊情况，从而得到递归出口。一般地，二叉树的递归结构如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)59/357.2.5二叉树的基本运算及其实现1.二叉树类设计publicclassBTreeClass{

//二叉树类BTNode<Character>b; //根结点Stringbstr; //二叉树的括号表示串publicBTreeClass(){ //构造方法b=null;}//二叉树基本运算算法}

为了简单，本节讨论的二叉树中所有结点值为单个字符。逻辑结构采用括号表示串，存储结构采用二叉链。60/352.二叉树的基本运算算法实现（1）创建二叉树CreateBTree(str)str逻辑结构b存储结构正确的括号表示串（每个结点值为单个字符）61/35用ch扫描str，其中只有4类字符，各类字符的处理方式如下：若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈。然后开始处理该结点的左孩子，因此置flag=true，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点。若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈。若ch=','：表示开始处理栈顶结点的右孩子结点，置flag=false。其他情况：只能是单个字符，表示要创建一个新结点p，根据flag值建立p结点与栈顶结点之间的联系，当flag=true时，表示p结点作为栈顶结点的左孩子结点，当flag=false时，表示p结点作为栈顶结点的右孩子结点。62/35publicvoidCreateBTree(Stringstr){

Stack<BTNode>st=newStack<BTNode>();

//建立一个栈stBTNode<Character>p=null;booleanflag=true;charch;inti=0;由括号表示层str创建以b为根结点的二叉链存储结构63/35while(i<str.length()){ //循环扫描str中每个字符ch=str.charAt(i);switch(ch){ case'(': st.push(p); //刚刚新建的结点有孩子,将其进栈flag=true;break; case')':st.pop(); //栈顶结点的子树处理完，出栈break; case',':flag=false; //开始处理栈顶结点的右孩子break;64/35default:p=newBTNode<Character>(ch); //用ch值新建一个结点if(b==null)b=p; //若尚未建立根结点,p作为根结点else{ //已建立二叉树根结点if(flag){ //新结点p作为栈顶结点的左孩子if(!st.empty())st.peek().lchild=p;}else{ //新结点p作为栈顶结点的右孩子if(!st.empty())st.peek().rchild=p;}}break;}i++; //继续遍历}}65/35str="A(B(D(，G))，C(E，F))"AB∧C∧D∧E∧∧G∧∧F∧b66/35（2）返回二叉链的括号表示串toString()publicStringtoString(){ //返回二叉链的括号表示串bstr="";

toString1(b);returnbstr;}privatevoidtoString1(BTNode<Character>t){//被toString方法调用if(t!=null){bstr+=t.data; //输出根结点值if(t.lchild!=null||t.rchild!=null){bstr+="("; //有孩子结点时输出"("

toString1(t.lchild); //递归输出左子树if(t.rchild!=null)bstr+=","; //有右孩子结点时输出","

toString1(t.rchild); //递归输出右子树bstr+=")"; //输出")"}}}67/35（3）查找值为x的结点FindNode(x)设f(t，x)在以t为根结点的二叉树中查找值为x的结点，找到后返回其地址，否则返回null。f(t，x)=null 若t=nullf(t，x)=t 若t.data=xf(t，x)=p

若在左子树中找到了，即

p=f(t.lchild，x)且p!=nullf(t，x)=f(t.rchild，x)

其他情况68/35publicBTNode<Character>FindNode(charx){

//查找值为x的结点算法returnFindNode1(b,x);}privateBTNode<Character>FindNode1(BTNode<Character>t,charx){//被FindNode方法调用BTNode<Character>p;if(t==null)returnnull; //t为空时返回nullelseif(t.data==x)returnt; //t所指结点值为x时返回telse{p=FindNode1(t.lchild,x); //在左子树中查找if(p!=null)returnp; //在左子树中找到p结点elsereturnFindNode1(t.rchild,x); //返回在右子树中查找结果}}69/35（4）求高度Height()

设以t为根结点二叉树的高度为f(t)，空树高度为0，非空树高度为左、右子树中较大的高度加1。f(t)=0

若t=nullf(t)=MAX{f(t.lchild)，f(t.rchild)}+1 其他情况70/35publicintHeight(){ //求二叉树高度的算法returnHeight1(b);}privateintHeight1(BTNode<Character>t){ //被Height方法调用intlchildh,rchildh;if(t==null)return0; //空树的高度为0else{lchildh=Height1(t.lchild); //求左子树高度lchildhrchildh=Height1(t.rchild); //求右子树高度rchildhreturnMath.max(lchildh,rchildh)+1;}}71/357.3二叉树先序、中序和后序遍历7.3.1二叉树遍历的概念二叉树遍历是指按照一定次序访问二叉树中所有结点，并且每个结点仅被访问一次的过程。设N为根结点，L、R分别为左、右子树，这6种遍历方法是NLR、LNR、LRN、NRL、RNL、RLN），若再规定先遍历左子树，后遍历右子树，则对于非空二叉树，可得到如下3种递归的遍历方法（即NLR、LNR和LRN）。NLR72/491）先序遍历①访问根结点。②先序遍历左子树。③先序遍历右子树。ABCEFDG先序序列为：ABDGCEF说明在一棵二叉树的先序序列中，第一个元素即为根结点对应的结点值。73/492）中序遍历①

中序遍历左子树。②

访问根结点。③中序遍历右子树。ABCEFDG中序序列为：DGBAECF。说明在一棵二叉树的中序序列中，根结点值将其序列分为前后两部分，前部分为左子树的中序序列，后部分为右子树的中序序列。74/493）后序遍历①后序遍历左子树。②后序遍历右子树。③访问根结点。ABCEFDG后序序列为：GDBEFCA。说明在一棵二叉树的后序序列中，最后一个元素即为根结点对应的结点值。75/497.3.2先序、中序和后序遍历递归算法1）先序遍历的递归算法publicvoidPreOrder1(BTreeClassbt){ //先序遍历的递归算法PreOrder11(bt.b);}privatevoidPreOrder11(BTNode<Character>t){//被PreOrder1方法调用if(t!=null){System.out.print(t.data+""); //访问根结点

PreOrder11(t.lchild); //先序遍历左子树

PreOrder11(t.rchild); //先序遍历右子树}}76/49ABCEFDGABCEFDGPreOrder1177/492）中序遍历的递归算法publicvoidInOrder1(BTreeClassbt){ //中序遍历的递归算法InOrder11(bt.b);}privatevoidInOrder11(BTNode<Character>t){//被InOrder1方法调用if(t!=null){

InOrder11(t.lchild); //中序遍历左子树System.out.print(t.data+""); //访问根结点

InOrder11(t.rchild); //中序遍历右子树}}78/49ABCEFDGInOrder11ABCEFDG79/493）后序遍历的递归算法publicvoidPostOrder1(BTreeClassbt){ //后序遍历的递归算法PostOrder11(bt.b);}privatevoidPostOrder11(BTNode<Character>t){//被PostOrder1方法调用if(t!=null){

PostOrder11(t.lchild); //后序遍历左子树

PostOrder11(t.rchild); //后序遍历右子树System.out.print(t.data+""); //访问根结点}}80/49ABCEFDGPostOrder11ABCEFDG81/497.3.3递归遍历算法的应用

【例7.6】假设二叉树采用二叉链存储结构存储，设计一个算法求一棵给定二叉树中的结点个数。

求一棵二叉树中的结点个数是以遍历算法为基础的，任何一种遍历算法都可以出一棵二叉树中的结点个数。82/49publicstaticintNodeCount1(BTreeClassbt){//基于先序遍历求结点个数returnNodeCount11(bt.b);}privatestaticintNodeCount11(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;k=1; //根结点计数1，相当于访问根结点m=NodeCount11(t.lchild); //遍历求左子树的结点个数n=NodeCount11(t.rchild); //遍历求右子树的结点个数returnk+m+n;}83/49publicstaticintNodeCount2(BTreeClassbt){//基于中序遍历求结点个数returnNodeCount21(bt.b);}privatestaticintNodeCount21(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;m=NodeCount21(t.lchild); //遍历求左子树的结点个数k=1; //根结点计数1，相当于访问根结点n=NodeCount21(t.rchild); //遍历求右子树的结点个数returnk+m+n;}84/49publicstaticintNodeCount3(BTreeClassbt){//基于后序遍历求结点个数returnNodeCount31(bt.b);}privatestaticintNodeCount31(BTNode<Character>t){intm,n,k;if(t==null) //空树结点个数为0return0;m=NodeCount31(t.lchild); //遍历求左子树的结点个数n=NodeCount31(t.rchild); //遍历求右子树的结点个数k=1; //根结点计数1，相当于访问根结点returnk+m+n;}85/49

也可以从递归算法设计的角度来求解。设f(b)求二叉树b中所有结点个数，它是“大问题”，f(b.lchild)和f(b.rchild)分别求左、右子树的结点个数。NLRf(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况86/49publicstaticintNodeCount4(BTreeClassbt){//递归求解returnNodeCount41(bt.b);}privatestaticintNodeCount41(BTNode<Character>t){if(t==null)return0; //空树结点个数为0elsereturn(NodeCount41(t.lchild)+NodeCount41(t.rchild)+1);}f(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况87/49f(b)=0 当b=nullf(b)=f(b.lchild)+f(b.rchild)+1 其他情况

其中“+1”相当于访问结点，放在不同位置体现不同的递归遍历思路，NodeCount41()方法是将“+1”放在最后，体现出后序遍历的算法思路。

基于递归遍历思路和直接采用递归算法设计方法完全相同。实际上，当求解问题较复杂时，直接采用递归算法设计方法更加简单方便。88/49一般地，二叉树由根、左右子树3部分构成，但可以看成两类，即根和子树。如果需要先处理根再处理子树，可以采用先序遍历思路。如果需要先处理子树，再处理根，可以采用后序遍历思路。NLR89/49

【例7.8】假设二叉树采用二叉链存储结构存储，设计一个算法将二叉树bt1复制到二叉树bt2。

采用直接递归算法设计方法。设f(t1，t2)是由二叉链t1复制产生t2，这是“大问题”。t1t2f(t1.rchild，t2.rchild)f(t1.lchild，t2.lchild)f(t1，t2)90/49t1t2f(t1.rchild，t2.rchild)f(t1.lchild，t2.lchild)f(t1，t2)f(t1，t2)

t2=null 当t1=nullf(t1，t2)

由t1根结点复制产生t2根结点; 当t1≠null

f(t1.lchild，t2.lchild);

f(t1.rchild，t2.rchild);91/49publicstaticBTreeClassCopyBTree1(BTreeClassbt1){//基于先序遍历复制二叉树BTreeClassbt2=newBTreeClass();bt2.b=CopyBTree11(bt1.b);returnbt2;}privatestaticBTNode<Character>CopyBTree11(BTNode<Character>t1){//由t1复制产生t2if(t1!=null){BTNode<Character>t2=newBTNode<Character>(t1.data);//复制根t2.lchild=CopyBTree11(t1.lchild); //递归复制左子树t2.rchild=CopyBTree11(t1.rchild); //递归复制右子树returnt2;}returnnull; //t1为空时返回null}92/49上述算法是基于先序遍历的：先复制根结点（访问根结点），然后分别复制二叉树左子树和右子树（遍历左子树和右子树）。也可以采用基于后序遍历思路。那么是否可以基于中序遍历呢？尽管理论上可行，建议不采用中序遍历思路求解，因为在复制中处理一个结点时，最好先创建该结点后再一次性建立其左右子树，这样思路更加清晰，所以基于先序遍历复制二叉树是最佳方法。例如，交换一棵二叉树中的所有结点的左右子树，采用先序遍历和后序遍历思路均可，但不能采用中序遍历思路，而后序遍历思路最佳。掌握3种递归遍历算法，灵活利用它们求解问题十分重要！提示93/49

【例7.9】假设一棵二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法求二叉树中指定结点值的结点所在的层次（根结点的层次计为1）。解法1二叉树中每个结点都有一个相对于根结点的层次，根结点的层次为1，那么如何指定这种情况呢？可以采用递归算法参数赋初值的方法，即设f(b，x，h)为“大问题”，增加第3个参数h表示第一个参数b指向结点的层次，在初始调用时b指向根结点，h对应的实参为1，从而指定了根结点的层次为1的情况。94/49f(b，x，h)=0 b=nullf(b，x，h)=h

当b.data=xf(b，x，h)=l

当l=f(b.child，x，h+1)，

且l≠0（在左子树中找到了）f(b，x，h)=f(b.rchild，x，h+1) 其他情况95/49publicstaticintLevel1(BTreeClassbt,charx){returnLevel11(bt.b,x,1);}privatestaticintLevel11(BTNode<Character>t,charx,inth){if(t==null)return0; //空树不能找到该结点elseif(t.data==x)returnh; //根结点即为所找,返回其层次else{intl=Level11(t.lchild,x,h+1); //在左子树中查找if(l!=0)returnl; //左子树中找到了,返回其层次elsereturnLevel11(t.rchild,x,h+1);

//左子树中未找到,再在右子树中查找}}递归算法参数赋初值问题96/49解法2前面的解法是直接求x结点在整个二叉树b中的层次（绝对层次）。实际上对于任何一棵包含x结点的子树，相对于该子树x结点有一个层次（相对层次），不同的子树中x结点的相对层次是不同的。ABCEFDGG在B的子树中的相对层次=3G在C的子树中的相对层次=0G在A的中的相对层次=MAX(3,0)+1=497/49对于二叉树b中子树t，若t=null，则不可能在子树t中找到x结点，返回0。若t.data=x，表示x结点的相当层次为1，返回1。否则递归在t的左右子树中求出相对于左右孩子的相对层次leftl和rightl，那么x结点相当于子树t的相对层次应该为max(lefti，righti)+1。当子树t为二叉树b时，求出的结果就是x结点在整个二叉树中的层次。98/49publicstaticintLevel2(BTreeClassbt,charx){returnLevel21(bt.b,x);}privatestaticintLevel21(BTNode<Character>t,charx){if(t==null) //空树不能找到该结点return0;if(t.data==x) //根结点值为xreturn1;intleftl=(t.lchild==null?0:Level21(t.lchild,x));intrightl=(t.rchild==null?0:Level21(t.rchild,x));if(leftl<1&&rightl<1) //左右子树都没有找到，返回0return0;returnMath.max(leftl,rightl)+1; //返回左右子树中最大层次+1}99/49

【例7.11】假设二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法输出值为x的结点的所有祖先。解法1根据二叉树中祖先的定义可知，若一个结点的左孩子或右孩子值为x时，则该结点是x结点的祖先结点；若一个结点的左孩子或右孩子为x结点的祖先结点时，则该结点也为x结点的祖先结点。设f(t，x)表示t结点是否为x结点的祖先结点。f(b，x)=false 若b==nullf(b，x)=true，并输出b结点

若b结点有值为x的左孩子结点f(b，x)=true，并输出b结点

若b结点有值为x的右孩子结点f(b，x)=true，并输出b结点

若f(b.lchild，x)为true或 f(b.rchild，x)为truef(b，x)=false 其他情况100/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor1(BTreeClassbt,charx){//返回x的祖先ans="";Ancestor11(bt.b,x);returnans;}privatestaticbooleanAncestor11(BTNode<Character>t,Characterx){if(t==null)returnfalse;if(t.lchild!=null&&t.lchild.data==x){ans+=t.data+""; //t结点是x结点的祖先returntrue;}if(t.rchild!=null&&t.rchild.data==x){ans+=t.data+""; //t结点是x结点的祖先returntrue;}if(Ancestor11(t.lchild,x)||Ancestor11(t.rchild,x)){ans+=t.data+""; //祖先的祖先是祖先returntrue;}returnfalse; //其他情况返回false}}101/49解法2二叉树中x结点的祖先恰好是根结点到x结点的路径上除了x结点外的所有结点。采用先序遍历的思路，采用一个ArrayList容器path存放路径，当找到x结点时，将path中x结点（最后添加的结点）删除，再将path复制的ans中。ABCEFDGG的祖先：ABD102/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor2(BTreeClassbt,charx){//返回x的祖先ArrayList<Character>path=newArrayList<Character>();//存放路径ans="";Ancestor21(bt.b,x,path);returnans;}privatestaticvoidAncestor21(BTNode<Character>t, Characterx,ArrayList<Character>path){if(t==null)return;path.add(t.data);if(t.data==x){path.remove(path.size()-1); //删除x结点ans=path.toString();return;}

Ancestor21(t.lchild,x,path); //遍历左子树

Ancestor21(t.rchild,x,path); //遍历右子树path.remove(path.size()-1); //从path中删除t结点,回退}}?103/49在方法Ancestor21(t，x，path)中path为ArrayList对象，当执行该方法的path.add(t.data)语句后将当前访问的t结点值添加到path中，这样在找到x结点时path是一个查找轨迹（包含所有遍历中访问的结点）。ABCEFDG先序遍历访问F时的轨迹从根结点到F结点的路径104/49publicclassExam7_11{staticStringans; //存放x结点的所有祖先结点publicstaticStringAncestor3(BTreeClassbt,charx){//返回祖先char[]path=newchar[100];intd=-1; //path[0..d]存放根到x结点的路径ans="";Ancestor31(bt.b,x,path,d);returnans;}privatestaticvoidAncestor31(BTNode<Character>t, Characterx,char[]path,intd){if(t==null)return;

d++;path[d]=t.data;if(t.data==x){for(inti=0;i<d;i++) //将path[0..d-1]存放的ans中ans+=String.valueOf(path[i])+"";return;}

Ancestor31(t.lchild,x,path,d); //遍历左子树

Ancestor31(t.rchild,x,path,d); //遍历右子树}}105/49

【例7.12】假设二叉树采用二叉链存储结构，且所有结点值均不相同，设计一个算法求二叉树的宽度（即二叉树中结点个数最多的那一层的结点个数）。设置一个数组w，w[i]表示第i（1≤i≤最大层次）层的结点个数（初始所有元素为0）。采用先序遍历求w（通过递归算法参数赋初值方式指定根结点的层次为1），w中的最大元素就是该二叉树的宽度。106/49publicclassExam7_12{finalstaticintMaxLevel=100; //最大层次staticint[]w=newint[MaxLevel]; //存放每一层结点个数publicstaticintWidth(BTreeClassbt){//求二叉树的宽度

Width1(bt.b,1);intans=0;for(inti=1;i<MaxLevel;i++) //求w中最大元素if(ans<w[i])ans=w[i];returnans;}privatestaticvoidWidth1(BTNode<Character>t,inth){if(t==null)return;w[h]++; //第h层的结点个数增1

Width1(t.lchild,h+1); //遍历左子树

Width1(t.rchild,h+1); //遍历右子树}}107/497.3.4*先序、中序和后序遍历非递归算法1）先序遍历的非递归算法方法1将根结点t进栈;while(栈不空){出栈结点p并访问之;

若p结点有右孩子，将其右孩子进栈；

若p结点有左孩子，将其左孩子进栈；}108/49publicvoidPreOrder2(BTreeClassbt) //先序遍历的非递归算法1PreOrder21(bt.b);}privatevoidPreOrder21(BTNode<Character>t){//被PreOrder2调用

Stack<BTNode>st=newStack<BTNode>();

//定义一个栈BTNode<Character>p;st.push(t); //根结点t进栈while(!st.empty()){ //栈不为空时循环p=st.pop(); //出栈结点pSystem.out.print(p.data+""); //访问p结点if(p.rchild!=null) //p结点有右孩子时进栈st.push(p.rchild);if(p.lchild!=null) //p结点有左孩子时进栈st.push(p.lchild);}}109/49方法2ABCDFHEG①②③④⑤⑥⑦⑧p=t;while(栈不空或者p!=null){while(p!=null){//访问p及左下结点并进栈

访问p结点;将p进栈;p=p.lchild} //Ⅰ部分if(栈不空){

出栈p；p=p.rchild;} //Ⅱ部分}110/49publicvoidPreOrder3(BTreeClassbt) { //先序遍历的非递归算法2PreOrder31(bt.b);}privatevoidPreOrder31(BTNode<Character>t){//被PreOder3调用Stack<BTNode>st=newStack<BTNode>(); //定义一个栈BTNode<Character>p=t;while(!st.empty()||p!=null){ //栈不空或者p不空时循环while(p!=null){ //访问根结点及所有左下结点并进栈System.out.print(p.data+""); //访问p结点st.push(p);p=p.lchild;}if(!st.empty()){ //若栈不空p=st.pop(); //出栈p结点p=p.rchild; //转向处理其右子树}}}111/492）中序遍历的非递归算法⑧ABCDFHEG①②③④⑤⑥⑦p=t;while(栈不空或者p!=null){while(p!=null){//p及所有左下结点进栈

将p进栈;p=p.lchild;} //Ⅰ部分if(栈不空){

出栈p并访问之;p=p.rchild;} //Ⅱ部分}112/49publicvoidInOrder2(BTreeClassbt){ //中序遍历的非递归算法InOrder21(bt.b);}privatevoidInOrder21(BTNode<Character>t){//被InOrder2调用Stack<BTNode>st=newStack<BTNode>(); //定义一个栈BTNode<Character>p=t;while(!st.empty()||p!=null){ //栈不空或者p不空时循环while(p!=null){ //p及其所有左下结点并进栈st.push(p);p=p.lchild;}if(!st.empty()){ //若栈不空p=st.pop(); //出栈p结点System.out.print(p.data+""); //访问p结点p=p.rchild; //转向处理右子树}}}113/493）后序遍历的非递归算法⑧⑥⑦①②ABCDFH④⑤EG③p=t;do{while(p!=null){

将p进栈;p=p.lchild;} //Ⅰ部分while(栈不空且p结点的左子树已遍历或为空){

取栈顶结点p;if(p的右子树已遍历){

访问p结点;

退栈;}elsep=p.rchild;} //Ⅱ部分}while(栈不空);114/49问题1：如何确定p结点的右子树已遍历？LRp

设置一个变量q（初始为空），考虑栈顶结点p（与中序非递归过程相同，结点p的