数据结构ppt
列车运行图调整-音箱系统
2023年2月17日发(作者：猪靥)第13页
数据结构第6章树和二叉树.ppt
1、第六章树和二叉树6.1树的类型定义6.2二叉树的类型定义和实现6.3
遍历二叉树和线索二叉树6.4树和森林6.5Huffman树与Huffman编码1对比树
型结构和线性结构的结构特点第一个数据元素(无前驱)最终一个数据元素(无后
继)其它数据元素(一个前驱、一个后继)根结点(无前驱)多个叶子结点(无后继)
其它数据元素(一个前驱、多个后继)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~26.1树的
类型定义树是n(n≥0)个结点的有限集D，当n≥1时：1〕有一个特定的结点root
被称为根(结点);2〕除根以外的结点被分成m(m≥0)个不相交的有限集
T1,T2,……,Tm，其中每个集合又是一棵树，称为根的子树。ABCDEFGHIJMKL3任
何一棵非空树是一个二元组Tree=〔roo
2、t，F〕其中：root被称为根结点F被称为子树森林森林和树之间的联系：
一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树。森林：
是m〔m≥0〕棵互不相交的树的集合。4定义或为空树，或是由一个根结点和两
棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉
树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2子树有左右之分，
不能颠倒——有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概
念6.2二叉树的类型定义和实现5性质1在二叉树的第i层上至多有2i-1个结
点。(i≥1)二叉树的重要特性性质2深度为k的二叉树上至多含2k-1个结点(k≥1)
性质3对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必
存在关系式：n0=n2+1。性质4具有
3、n个结点的完全二叉树的深度为log2n+16满二叉树：深度为k，且有
2k-1个结点的二叉树；特点：每一层上的结点数都是最大数目。结点层序编号方
法：从根结点起自上而下逐层〔层内自左至右〕对二叉树的结点进行连续编号。
1367101415两类特别的二叉树：7完全二叉树：一棵深度为k有n
个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至
n的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次数最大
的两层上出现。只有最下一层的结点数可能未到达最大值。对任一结点，假如其
右子树的最大层次为L，则其左子树的最大层次为L或L＋1。完全二叉树结点数
2k-1-1n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若
2i+1n，则该结
4、点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。9证明：
先证⑵⑶，然后证⑴。证⑵⑶，用归纳法；当i=1时，即i为根结点，若2i存
在，即2存在，2为1的左孩子；若2i+1存在，即3存在，3为1的右孩子；结
论成立；假设当i=j时，结论成立；LChild(j)=2j;RChild(j)=2j+1;当i=j+1时，
依据完全二叉树的结构特点，j+1的左孩子应为j的右孩子的下一个结点，即
LChild(j+1)=RChild(j)+1=(2j+1)+1=2(j+1)RChild(j+1)=LChild(j+1)+1=2(j+
1)+1;结论成立；10下面证⑴：当i=1时，即1为根，无双亲；当i≠1时，假设
k为其双亲，即i为k的孩子；①假如i为k的左孩子，即i=2k，i为偶数，k=i/2，
即k
5、=i/2②假如i为k的右孩子，即i=2k+1，i为奇数，k=(i-1)/2，即
k=i/2故结论成立；证明〔续〕：11Q5:设一棵完全二叉树有700个结点，则
共有个叶子结点。答案：总层数k=log2700＋1=10;//〔29〕=512且前9层
总结点数为29-1=511因此，末层叶子数为700-511=189个。末层的189个叶子
只占据了上层的95个结点(189/2)，上层(k=9)右边的0度结点数还有
第14页
29-1-95=161个！所以，全部叶子数＝189(末层)＋161(k-1层)=350个。35012
另一法：可先求2度结点数,再由此得到叶子总数。首先，前k-2层的28-1〔255〕
个结点确定都是2度的〔完全二叉树〕另外，末层叶子〔刚刚已求出为189〕所
对应的双亲也是度＝2
6、，〔共有189/2＝94个〕。所以全部2度结点数为255(k-2层)＋94(k-1
层)=349个；总叶子数＝2度结点数＋1=350个。13Q5:设一棵完全二叉树有700
个结点，则共有个叶子结点。答：最快方法：总叶子数＝n/2＝
350350∵n=n0+n1+n2由公式n0=n2+1n=n0+n1+(n0-1)=2n0+n1-1n0=(n+1-n1)/2
又∵n1=1或n1=0，故n0=n/2或n0=(n+1)/2因n和n0都为整数，所以
n0=n/214Q6:一棵有124个叶子结点的完全二叉树，最多有个结点。答：由
n0=n2+1可知：n2=123；前6层有26-1=63个度为2的结点；第7层有123-63=60
个度为2的结点，则第8层对应有60*2=120个叶子结点；第7层总共2
7、7-1=64个结点，剩余64-60=4个非2度结点；若有1个度为1的结点，
总结点数为124+1+123=248若有0个度为1的结点，总结点数为124+0+123=247
所以，最多有248个结点。24815Q6:一棵有124个叶子结点的完全二叉树，最多
有个结点。答：由n0=n2+1可知：n2=123；n=n0+n1+n2=247+n1在完全二叉树中，
n1=0或n1=1；所以n的最大值为247+1=24824816#defineMAX_TREE_SIZE100//
二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存
储根结点SqBiTreebt;1.二叉树的顺序存储表示根据依次自上而下、自左至右的
顺序，存储完全。省略部分。(n1)n!=1(n=0,1)递归函数的定义都应包括两部分：
1.递归终止的条件，即对无需递归的最小问题的处理方法；2.将一般问题简化成
一个或多个规模较小的相同性质的问题，递归地调用同样的方法求解这些问题，
使这些问题最终到达递归终止。
33voidPreorder(BiTreeT,void(*visit)(TElemTypee)){//先序遍历二叉树
if(T){//递归终止条件(*visit)(T-data);//访问结点
Preorder(T-lchild,visit);//遍历左子树Preorder(T-rchild,visit);//遍历
右子树}}//Preorder算法的递归描述：二叉树算法实现基于二叉链表存储结构
34先序遍历非递归算法需要设置一个栈结
9、构，用以保存指向结点的指针，以便在遍历某结点的左子树之后，由该
指针找到该结点的右子树。算法思想从二叉树的根结点开始，令指针变量p指向
根结点，1)访问当前结点p，并将p压入栈中，然后令p指向它当前指向结点的
左孩子结点。2)若p不为空，重复执行第1)步，否则执行第3步；3)从栈中弹出
栈顶元素赋给指针变量p，并令p指向它当前指向结点的右孩子结点。4)重复以
上3步，直到p为空，并且栈也为空时结束。
35voidPreorder(BiTreeT,void(*visit)(TElemTypee)){//先序遍历二叉树
InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){//往左子树方向前进
(*visit)(p-data);Push(S,p)
10、;p=p-lchild;}else{//从左子树退回
Pop(S,p);p=p-rchild;}}//while}//Preorder算法的非递归描述：二叉树算法实
现基于二叉链表存储结构36若二叉树为空树，则空操作；否则，⑴中序遍历左
子树；⑵访问根结点；⑶中序遍历右子树。中(根)序的遍历算法：访问路径描述：
沿着左子树方向找到最“左边”的结点作为起点，从左子树退回时依次访问每个
结点及其右子树。中序遍历序列：
D,B,G,E,A,C,FAFGEDCB37voidInorder(BiTreeT,void(*visit)(TElemTypee)){/
第15页
/中序遍历二叉树if(T){Inorder(T-lchild,visit);//遍历左子树
(*visit)(T-data);//访问结点Inorder(T-rchild,visit);//遍历右子
树}}//Inorder算法的递归描述：二叉树算法实现基于二叉链表存储结构38中序
遍历非递归算法算法思想根结点先进栈，左孩子结点紧跟根后面进栈，右孩子结
点在根出栈后入栈；每个结点都要进一次栈和出一次栈，并且总是访问栈顶元素，
因此，算法时间冗杂度为O(n)。
39voidInorder(BiTreeT,void(*visit)(TElemTypee)){//中序遍历二叉树
InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){//往左子树方向前进
Push(S,p);p=p-lchild;}else{//从左子树退回Pop(S,p);(*v
12、isit)(p-data);p=p-rchild;}}//while}//Inorder算法的非递归描述：
二叉树算法实现基于二叉链表存储结构40中序遍历非递归执行过程Ⅰ栈状态动
作说明初始状态AA进栈转向A的左孩子BAB进栈掌握转向B的左孩子，左孩子
为空AB出栈输出B，转向B的右孩子DAD进栈转向D的左孩子EDAE进栈转向E
的左孩子，左孩子为空41中序遍历非递归执行过程Ⅱ栈状态动作说明DAE出栈
输出E，转向E的右孩子，右孩子为空AD出栈输出D，转向D的右孩子FAF进栈
转向F的左孩子，空AF出栈输出F，转向F的右孩子，右孩子为空A出栈输出A，
转向A的右孩子42中序遍历非递归执行过程Ⅲ栈状态动作说明CC进栈转向C的
左孩子，左孩子为空C出栈输出C，转向C的右孩子，右孩子为空栈空
13、，且p=NULL，结束输出：BEDFAC43若二叉树为空树，则空操作；否则，
⑴后序遍历左子树；⑵后序遍历右子树；⑶访问根结点。后(根)序的遍历算法：
访问路径描述：找到最“左边”的叶子结点作为起点，每次经过一个结点时需要
推断：假如是从左子树返回，则进入右子树；假如从右子树返回，则访问该结点
并后退。推断的方法是看该结点的右子树的根是否为刚刚访问的那个结点。后序
遍历序列：
D,G,E,B,F,C,AAFGEDCB44voidPostorder(BiTreeT,void(*visit)(TElemTypee))
{//后序遍历二叉树if(T){Postorder(T-lchild,visit);//遍历左子树
Postorder(T-rchild,visit);//遍历右子
14、树(*visit)(T-data);//访问结点}}//Postorder算法的递归描述：二叉
树算法实现基于二叉链表存储结构45习题1：写出下列图所示的二叉树先序遍历、
中序遍历、后序遍历的序列。⑴先序遍历序列：－,＋,a,*,b,－,c,d,/,e,f⑵中
序遍历序列：a,＋,b,*,c,－,d,－,e,/,f⑶后序遍历序列：a,b,c,d,－,*,
＋,e,f,/,－－＋/a*b－efcd46ABCDEFGHK习题2：先序序列：中序序列：后序序
列：ABCDEFGHKBDCAEHGKFDCBHKGFEA47习题3：先序序列：中序序列：后序序列：
ABDGCEFHDGBAECHFGDBEHFCAABGDCFHE48