第7章树和二叉树-6（小结）

第7章-小结1树树中结点计算方法度为m的树中所有结点的度≤m至少有一个度为m的结点度为2的树至少有3个结点！1/42任何非空树中：分支数=所有结点度之和，分支数=n-1度为m的树中：n=n0+n1+…+nm度为m的树中：所有结点度之和=n1+2n2+…+mnm树中结点计算的基本公式2/42已知一棵度为4的树中，度为i（i>1）的结点个数有i个，问该树中有多少个叶子结点？n=n0+n1+n2+n3+n4=n0+1+2+3+4=n0+10，即：n0=n-10度之和=n-1度之和=n1+2n2+3n3+4n4=30所以n=30+1=31，n0=n-10=31-10=21。示例1解3/42树和二叉树的转换与还原二叉树还原为树树转换为二叉树过程4/42将森林T转换为二叉树B，若T中有n个非叶子结点，则二叉树B中无右孩子的结点个数是多少？ABCDEFGABCDEFGBT非叶子结点：3无右孩子的结点：4T中一个放在结点至少有一个孩子结点，有一个最右边的孩子结点s在B中s没有右孩子

T中n个非叶子结点，B中对应n个没有右孩子结点T的根结点对应B的根结点，它一定是没有右孩子结点

n+1示例5/42树的遍历先根遍历后根遍历层次遍历具有递归性6/42给定一棵树T，将其转换成二叉树B后，T的先根遍历对应B的什么遍历序列？先根遍历：A

BT11T12T2

…先序遍历：A

Bt11t12t2

…AAT11T12t11t12t2BT2…B…TB先序序列示例7/42给定一棵树T，将其转换成二叉树B后，T的后根遍历对应B的什么遍历序列？后根序列：

BT11T12T2

…

A中序序列：Bt11t12t2

…

AAAT11T12t11t12t2BT2…B…中序序列示例8/42树的存储结构双亲存储结构：表示1：1的关系孩子链存储结构：表示1：n的关系孩子兄弟链存储结构：树转化为二叉树，对应二叉链9/42在一棵树T中最常用的操作是查找某个结点的祖先结点，采用哪种存储结构最合适？

双亲存储结构

孩子链存储结构或者孩子兄弟链存储结构

如最常用的操作是查找某个结点的所有兄弟，采用哪种存储结构最合适？示例10/422二叉树

n个不同的结点构造的二叉树个数？当n=3，结果为5。第n个Catalan数11/42有n个结点并且高度为n的不同形态的二叉树个数是多少？该二叉树：有n层，每层一个结点，该结点可以作为双亲结点的左孩子，也可以作为右孩子

这样的二叉树的个数=1×2×…×2=2n-1。例如，当n=3时有22=4个这样的二叉树。示例12/42

二叉树中结点计算方法二叉树中所有结点的度≤2分支数=所有结点度之和，分支数=n-1n=n0+n1+n2所有结点度之和=n1+2n2n0=n2+113/42完全二叉树中结点计算方法结点个数为n，树形可以唯一确定叶子结点个数为n0，树形不能唯一确定n为奇数时，n1=0；n为偶数时，n1=1。n0=n2+1高度h=log2(n+1)，是n个结点高度最小的二叉树14/42含有60个叶子结点的二叉树的最小高度是多少？在该二叉树中，n0=60，n2=n0-1=59，n=n0+n1+n2=119+n1。当n1=0且为完全二叉树时高度最小。此时高度h=

log2(n+1)

=

log2120

=7。示例15/42满二叉树中结点计算方法高度h=log2(n+1)高度为h的满二叉树，n=2h-1，n一定为奇数n0=n2+1n1=016/42已知一棵非空满二叉树中有31个分支结点，则总结点个数是多少？n2+n1=31，而n1=0，所以n2=31（双分支结点个数）。n0=n2+1=32（二叉树性质），n=n0+n1+n2=63。示例17/423二叉树的存储结构顺序存储结构BACD1236A1B2C3#4#5D6i2i2i+1i/218/42一棵高度为h的并且只有h个结点的二叉树，采用顺序存储结构存放在R[1..n]中，则n应该至少是（）。A.2h B.2h-1C.2h-1D.2h可能是一棵有斜树，最后一个结点的层序编号为2h-1。C…层序编号为2h-1h示例19/42二叉链存储结构BACDAbB∧∧C∧D∧∧任何结点的左、右指针分别指向一棵二叉树！

递归数据结构20/42含有n个结点的二叉树采用二叉链存储结构，其中空指针域个数是多少？每个结点2个指针域，共2n个指针域除了根结点外，每个结点被一个非空指针所指向共有n-1个非空指针域空指针域的个数=2n-(n-1)=n+1。示例21/42二叉树遍历遍历过程某种次序访问所有结点不重复访问422/42先序遍历中序遍历后序遍历层次遍历

常用遍历方法具有递归性二叉树算法二叉树查找二叉树遍历23/42递归遍历算法应用基于递归遍历

采用递归数据结构的递归算法设计方法NLRbf(b)：大问题f(L)：小问题f(R)：小问题3部分组成，两种类型：结点，子树先结点，再子树

先序先子树，再结点

后序24/42假设二叉树采用二叉链存储结构，设计一个算法求二叉树b中第k层的结点个数。设计算法为knumber(b，h，k，&n)，h表示b所指的结点层次，n是引用型参数，用于保存第k层的结点个数。初始调用时，b为根结点指针，h为1，n赋值为0，即调用方式是：n=0；knumber(b，1，k，n)。递归算法赋初值方式示例解25/42算法如下：voidknumber(BTNode*b，inth，intk，int&n){if(b==NULL) //空树直接返回return;else //处理非空树{if(h==k)n++; //当前访问的结点在第k层时，n增1

elseif(h<k) //若当前结点层次小于k，递归处理左、右子树{knumber(b->lchild，h+1，k，n); knumber(b->rchild，h+1，k，n);}}}基于先序遍历的思路26/42假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度（采用递归方法）。levelnumber(BTNode*b，inth，inta[])：求二叉树b中所有层的结点个数，存放在a数组中，a[h]表示第h层结点个数f(b，h，a)

不做任何事情

当b=NULLf(b，h，a)

a[h]++; 其他情况

f(b->lchild，h+1，a)

f(b->rchild，h+1，a)示例解27/42voidlevelnumber(BTNode*b，inth，inta[]){if(b==NULL)return;else{a[h]++;

levelnumber(b->lchild，h+1，a);

levelnumber(b->lchild，h+1，a);}}28/42intBTWidth1(BTNode*b){intwidth=0，i;inta[MaxSize];for(i=1;i<MaxSize;i++)a[i]=0; //a设置所有元素初始化为0

levelnumber(b，1，a);i=1;while(a[i]!=0) //求a中最大元素即宽度

{if(a[i]>width) width=a[i];i++;}returnwidth;}29/42层次遍历算法应用BACD每个结点有唯一的双亲结点结点的层次=双亲结点的层次+130/42假设二叉树采用二叉链存储结构，设计一个算法求二叉树b的宽度（采用层次遍历方法）。intBTWidth2(BTNode*b){struct{intlno; //结点的层次

BTNode*p; //结点指针

}Qu[MaxSize]; //定义非环形队列

intfront，rear; //定义队头和队尾指针intlnum，width，i，n;front=rear=0; //置队列为空队示例解31/42rear++; Qu[rear].p=b; //根结点进队Qu[rear].lno=1; //根结点的层次为1while(rear!=front) //队不空时循环{front++;b=Qu[front].p; //出队结点plnum=Qu[front].lno;if(b->lchild!=NULL) //有左孩子，将其进队{rear++;Qu[rear].p=b->lchild;Qu[rear].lno=lnum+1;}if(b->rchild!=NULL) //有右孩子，将其进队{rear++;Qu[rear].p=b->rchild;Qu[rear].lno=lnum+1;}}32/42width=0;lnum=1;i=1; //width存放宽度while(i<=rear){n=0;while(i<=rear&&Qu[i].lno==lnum){n++; //n累计一层中的结点个数

i++; //i扫描队列中所有结点}lnum=Qu[i].lno;if(n>width)width=n;}returnwidth;}33/42二叉树的构造由中序序列和先序序列可以唯一构造一棵二叉树由中序序列和后序序列可以唯一构造一棵二叉树由中序序列和层次序列可以唯一构造一棵二叉树534/42由一个固定的先序序列（含n个不同的结点），构造的二叉树个数？当n=3，结果为5。ABCABCABCABCABC第n个Catalan数35/42若某非空二叉树的先序序列和中序序列正好相反，则该二叉树的形态是什么？先序序列NLR中序序列的反序RNLR为空所有结