软件技术基础课件-第3章 算法与数据结构(三)

软件技术基础电子教案第3章算法与数据结构2/52第3章内容摘要3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序《软件技术基础》电子教案3/523.4树和二叉树上面谈的是线性数据结构，下面谈一谈非线性数据结构。树型结构是一类重要的非线性数据结构。在此结构中，元素之间存在着明显的层次或嵌套关系。本节主要内容:树的基本概念二叉树二叉树的遍历《软件技术基础》电子教案4/523.4.1树的基本概念1.定义：是一种常非线性结构树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。递归定义的《软件技术基础》电子教案5/52树的示例《软件技术基础》电子教案6/522.树的特点（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点（2）树中所有结点可以有零个或多个后继结点《软件技术基础》电子教案7/523.树的相关概念1)结点数据元素的内容及其指向其子树根的分支统称为结点2)结点的度结点的分支数。3)终端结点（叶子）度为0的结点。4)非终端结点度不为0的结点。5)结点的层次树中根结点的层次为1，根结点子树的根为第2层，以此类推。6)树的度树中所有结点度的最大值。7)树的深度树中所有结点层次的最大值。8)有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。《软件技术基础》电子教案8/529)森林是m（m≥0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：10)孩子、双亲结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。11)子孙以某结点为根的子树中的所有结点都被称为是该结点的子孙。12)祖先从根结点到该结点路径上的所有结点。13)兄弟同一个双亲的孩子之间互为兄弟。14)堂兄弟双亲在同一层的结点互为堂兄弟。《软件技术基础》电子教案9/524.树的表示法①直观表示法②嵌套集合表示法③凹入表示法//不清晰④广义表表示法约定每对括号括着前一结点名下的所有子树，同级子树用逗号分隔。(1)(2)(3)(4)《软件技术基础》电子教案10/523.4.2二叉树1.定义：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个称为左子集，另一个称为右子集，每个子集又是一个二叉树递归定义的《软件技术基础》电子教案11/522.二叉树的五种形态例《软件技术基础》电子教案12/523.二叉树的性质①在二叉树的第i层上最多有2i-1个结点（i≥1）②深度为k的二叉树最多有2k-1个结点（k≥1）③对于任意一棵二叉树，如果度为0的结点(叶结点)个数为n0，度为2的结点个数为n2，则n0=n2+1二叉树的总度数＝n1+2n2二叉树的节点数＝n0＋n1＋n2二叉树的总度数＝二叉树的节点数－1n1+2n2=n0＋n1＋n2-1即：n0=n2+1《软件技术基础》电子教案13/52满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树：n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树《软件技术基础》电子教案14/52④具有n个结点的完全二叉树的深度为log2n+1证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1n≤2K-1将不等式两端加1得到：2K-1≤n2K取以2为底的对数，化简：K-1≤log2nK得到：log2n=K-1。整理：K=log2n+1《软件技术基础》电子教案15/52⑤对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），有:A.如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。B.如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。C.如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。证明：采用数学归纳法，请大家自行证明《软件技术基础》电子教案16/524.二叉树的存储结构1.顺序存储结构2.链式存储结构通常二叉树可以用下面两种方式存储：下页介绍《软件技术基础》电子教案17/52(1)顺序存储结构适用完全二叉树，用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容如下图所示：下页给出C实现《软件技术基础》电子教案18/52#defineMaxTreeNodeNum1024typedefstruct{DataTypedata[MaxTreeNodeNum];/*根存储在下标为1的数组单元中*/intn;/*当前完全二叉树的结点个数*/}QBTree;顺序存储特点：A.二叉树是完全二叉树时，空间利用率高、寻找孩子和双亲比较容易。B.若二叉树不是完全二叉树，需要将空缺的位置用特定的符号填补，造成空间利用率的下降引出链式存储19/52(2)链式存储结构注：Lchild和Rchild是分别指向该结点左孩子和右孩子的指针下页C实现《软件技术基础》电子教案20/52typedefcharDataType/*设结点内容的数据类型为字符型*/typedefstructbnode{DataTypedata;structbnode*lchild,*rchild;}Bnode,*BTree;二叉树链接存储的节点定义《软件技术基础》电子教案21/523.4.3二叉树的遍历定义：按照一定规则访问二叉树的所有节点一次①先序遍历DLR②中序遍历LDR③后序遍历LRD下页分述DLR《软件技术基础》电子教案22/52(1)先序遍历DLR若二叉树为空，则结束遍历操作；否则1)访问根结点；2)先序遍历根的左子树；3)先序遍历根的右子树递归算法，思考它所对应的非递归算法先看遍历的结果《软件技术基础》电子教案23/52下页C实现《软件技术基础》电子教案24/52voidPreOrder(BTreet){if(t){visite(t-data);/*访问结点内容*/PreOrder(t-lchild);/*遍历左子树*/PreOrder(t-rchild);/*遍历右子树*/}}思考：1.visite函数能做什么？2.visite(t-data)这条语句执行次数？3.如何计算结点个数、叶子个数？4.改变visite(t-data)这条语句的位置会产生什么效果?思考如何得到中序和后序遍历的算法？《软件技术基础》电子教案25/52（2）中序遍历和后序遍历算法中序遍历voidInOrder(BTreet){if(t){InOrder(t-lchild);Visite(t-data);InOrder(t-rchild);}}后序遍历voidPostOrder(BTreet){if(t){PostOrder(t-lchild);PostOrder(t-rchild);Visite(t-data);}}《软件技术基础》电子教案26/52三种访问序列的结果《软件技术基础》电子教案27/52（3）三种遍历的非递归算法树的定义是递归的，容易实现遍历的递归算法思考遍历算法的执行过程找出它们所对应的非递归算法？《软件技术基础》电子教案28/521)先序遍历的非递归算法voidPreOrder(BTreet){PSeqStackS;BTreep=t;/*初始化*/S=Init_SeqStack();/*栈初始化*/while(p||!Empty_SeqStack(S)){if(p){Visite(p-data);Push_SeqStack(S,p);/*预留p指针在栈中*/p=p-lchild;}else{Pop_SeqStack(S,&p);p=p-rchild;}/*左子树为空,进右子树*/}//endwhile}//endpreorder29/522)中序遍历的非递归算法•将上述算法稍微改动就能写出中序遍历的非递归算法,请读者思考两个算法的差异.voidInOrder(BTreeT){PSeqStackS;BTreep=t;S=Init_SeqStack();/*初始化*/while(p||!Empty_SeqStack(S)){if(p){Push_SeqStack(S,p);/*预留p指针在栈中*/p=p-lchild;}else{Pop_SeqStack(S,&p);Visite(p-data);p=p-rchild;}/*左子树为空,进右子树*/}}30/523)后序遍历的非递归算法typedefstruct{Bnode*node;intflag;}DataType;voidPostOrder(BTreet){PSeqStackS;DataTypeSq;inttag;BTreep=t;S=Init_SeqStack();/*栈初始化*/while(p||!Empty_SeqStack(S)){if(p){Sq.flag=0;Sq.node=p;Push_SeqStack(S,Sq);/*将p指针以及flag压入栈中*/p=p-lchild;}else{Pop_SeqStack(S,&Sq);p=Sq.node;if(Sq.flag==0){Sq.flag=1;Push_SeqStack(S,Sq);/*二次压栈*/p=p-rchild;}else{Visite(p-data);p=null;//思考为什么？？/*把p赋空从栈中弹出下个结点*/}//endif}//endif}//endwhile}endpostorder31/52(4)二叉树遍历算法的应用二叉树是递归定义，可以写出它的递归遍历算法，同时借助遍历算法可以实现一些基本的应用，如：节点计数创建二叉树计算二叉树的高度等《软件技术基础》电子教案32/52例1：创建二叉树1.有多种创建二叉树的方法(按先序建,按中序和后序遍历结果建等),以下算法按先序建2.在输入先序序列时，需要在空节点填补一个特殊的字符，比如，‘#’。如果读入的字符是‘#’，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。3.采用先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成下页给出C实现《软件技术基础》电子教案33/52创建二叉树BTreeCreateBinTree(){/*以加入空结点的先序序列输入，构造二叉链表*/charch;BTreet;ch=getchar();if(ch==‘＃’)t=null;/*读入＃时，将相应结点指针置空*/else{t=(BTree)malloc(sizeof(Bnode));/*生成结点空间*/t-data=ch;t-lchild=CreateBinTree();/*构造二叉树的左子树*/t-rchild=CreateBinTree();/*构造二叉树的右子树*/`}returnt;}？《软件技术基础》电子教案34/52例2：求二叉树每层结点个数思路：二叉树中每个结点都对应一个层次,如果当前结点T对应的层次是L,则T-Lchild和T-Rchild所对应的层次就是L+1,利用这个特性,我们很容易用遍历算法求出结果设置一个数组，数组的下标表示树的层数，该下标元素的值记录该层元素的个数；通过树的遍历算法来得到最终数组元素的值下页给出C实现《软件技术基础》电子教案35/52voidLevcoun(BTreet,intL,intnum[])/*求链式存储的二叉树t中每层结点个数，L表示当前t所指结点的层次，当t初值为根时，L初值为1，num数组元素初始化0*/{if(t){Visite(t-data);//访问当前结点num