第一章-算法概要PPT课件

软件技术基础,基本数据结构及其运算,2,.,第二章基本数据结构及其运算（五）,树的基本概念二叉树,3,.,1树的基本概念非线性结构对于结构中的一个结点，可能有多个前趋和多个后继线性表中是有且仅有一个前趋和一个后继1.1树的定义树是以分支关系定义的层次结构。倒生树：树根在上，根上分茎，茎上分叶是族谱、社会组织机构一类实体的逻辑抽象,树的基本概念,4,.,对定义的理解（1）有限集（2）递归定义：树，根，子树（3）有且仅有一个根结点（4）子树是互不相交的有限集（5）树的层次性,有且仅有一个根结点,除根结点以外的结点有且仅有一个父结点,树的定义,5,.,树是一种数据结构Tree=(D,R)D：元素的集合R：元素关系的集合（父、子关系前件、后件关系）各结点没有或仅有一个父结点有且仅有一个根结点各结点可以有任意个子树,树的定义,6,.,1.2树的术语1）结点2）度与深度,根结点,没有前驱，仅有后继,结点的度：该结点拥有的子树数目。,树的度：最大的结点度,深度：最大的层次数,叶结点,(茎)分支结点,没有后继，仅有前驱,有且仅有一个前驱，可以有多个后继,树的术语,7,.,树的术语,孩子,兄弟,祖先,子孙,双亲,孩子,A,3）A节点的,8,.,树的术语,4）路径（树枝，分支）从K1出发自上而下到K2所经历的所有结点序列,K1,K2,K3,K4,K5,K6,K7,K1K4K7K2,树上两节点之间的路径有？条,9,.,树的术语,5）有序树与无序树有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。,10,.,树的术语,6）森林不相交的树的集合,11,.,二叉树,2二叉树2.1、定义二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。对比树的定义：空二叉树树的定义中没有空树的概念不多于2个孩子树的节点可以有任意个子树子树有左右之分无序树可不区分左右树的其它定义适用于二叉树：根茎叶、度、路径,仍然是递归定义。,二叉树是树吗？,12,.,二叉树,（4）二叉树的形态,空树,无子树,仅有左子树,有左右子树,仅有右子树,13,.,二叉树的性质,2.2、二叉树的性质（1）在二叉树的第i层上最多有2i-1个结点第i层的结点数最多是第i-1层的两倍（2）深度为k的二叉树最多有2k-1个结点（3）叶结点数比具有两个孩子的结点数多个,1,二叉树的数学特性,二叉树与二进制之间存在必然联系，进而可以与整个数学发生关联了,14,.,二叉树的性质,（3）叶结点数比具有两个孩子的结点数多1个,设n0为叶结点个数，n1为具有一个孩子的分支结点个数，n2为具有两个孩子的分支结点个数，n为结点总个数,结论：n0=n2+1;,条件1、n=n0+n1+n2,条件2、n=分支的个数+1,设为分支的个数为B,条件3、B=2n2+n1,所以：2n2+n1+1=n0+n1+n2,15,.,二叉树的性质,（4）深度为K的满二叉树，结点个数为2k-1满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。满二叉树：“装满”节点的二叉树半满二叉树：深度为K的二叉树，K1层是满二叉树，K层节点个数不足2K1个,16,.,二叉树的性质,（5）具有n个节点的完全二叉树，深度为log2n+1完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。如果对节点数为n的完全二叉树自上而下，从左至右依次编号，则节点i的父结点为i/2,若2in，则i的左后继是2i；若2in,则i无左后继,若2i1n，则i的右后继是2i1；若2in,则i无右后继,17,.,完全二叉树,关于完全二叉树的其他描述形式如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1,18,.,二叉树,满二叉树,半满二叉树,完全二叉树,非完全二叉树,半满二叉树,半满二叉树,非完全二叉树,19,.,二叉树的遍历,2.3、二叉树的操作2.3.1遍历操作分支及根的遍历顺序,中根遍历中序遍历,A,C,先根遍历先序遍历,B,后根遍历后序遍历,A,A,B,B,C,C,以根被访问顺序来划分不同的遍历方法在子树的访问顺序中始终以左子树优先,特点：,左根右,根左右,左右根,20,.,二叉树的遍历,1）中根遍历（中序遍历）,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,FGCEHBDJIALNPOQMK,左根右,21,.,二叉树的遍历,2）先根遍历（先序遍历）,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,ABCFGEHDIJKLMNOPQ,根左右,22,.,二叉树的遍历,3）后根遍历（后序遍历）,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,GFHECJIDBPQONMLKA,左右根,23,.,思考：第一个被遍历的节点，最后一个被遍历的节点，,课堂练习,写出这颗二叉树的三种遍历顺序,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,3、后根遍历（左右根）,ABCFGEHDIJKLMNOPQ,GFHECJIDBPQONMLKA,1、中根遍历（左根右）,2、先根遍历（根左右）,FGCEHBDJIALNPOQMK,24,.,树的存储,2.4树的存储2.4.1连续顺序存储,K1,K2,K5,K4,K6,a0,a1,a2,a3,a4,连续线性的下标不能很好的反映树的分支关系（非线性）,25,.,DATA,子树1,2,3,树的存储,2.4.2、链接存储多重链表树的节点对应于链表的结点树节点间的分支关系用结点间的指针描述结点可能有多个指针多重链表，每个指针描述对应节点的一个分支关系有且仅有一个根结点不同的指针指向不同的子树根结点一个子树有仅有一个根结点问题，一个结点里究竟该有多少个指针呢？,26,.,顺序存储二叉树,2.5.1顺序存储二叉树将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点i，我们可以知道它的父结点为i/2，两个孩子分别为2i和2i1。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系如此存放，将浪费较多空间,27,.,顺序存储二叉树,例,H,A,C,B,D,E,G,F,I,K,J,M,O,U,P,H,A,C,B,E,G,F,I,U,P,M,数组的下标可以体现逻辑关系,28,.,用链表实现二叉树,2.5.2用链表实现二叉树二叉树链表结点的定义,structBtnodeTdata;Btnode*Lchild;Btnode*Rchild;,左孩子，左子树,右孩子，右子树,29,.,用链表实现二叉树,二叉树的链表结构,30,.,二叉树的建立,2.5.3建立二叉树设输入次序：（以先根为序）,ABC_DEF_G_H_I_JK_L_,A,B,C,_,_,D,E,F,_,_,G,_,_,_,H,_,I,_,J,K,_,_,L,_,_,每一个空格“_”表示一个空指针,利用先根遍历算法框架，建立二叉树,根据输入的情况，将新节点放在指定的位置，然后从新节点开始下一个过程,31,.,二叉树的建立,templatevoidBinary_Tree:creat_Binary_Tree(Tend)Btnode*p;Tx;cinx;,if(x=end)return;,createanewnodep;,p-d=x;p-lchild=NULL;p-rchild=NULL;,p=newBtnode;,根据输入，生成新链点，主要包括申请链点空间,输入新元素,生成整个树的根,BT=p;creat(p,1,end);creat(p,2,end);,return;,以先根遍历算法为基础递归生成二叉树,32,.,二叉树的建立,templatestaticcreat(Btnode*p,intk,Tend)Btnode*q;Tx;cinx;if(x!=end)q=newBtnode;q-d=x;q-lchild=NULL;q-rchild=NULL;if(k=1)p-lchild=q;if(k=2)p-rchild=q;creat(q,1,end);creat(q,2,end);return;,33,.,二叉树的遍历,中根遍历算法算法实现分析遍历过程：从根开始,A,B,C,1、找到B，但不访问B,2、根据B找到A，访问A,3、再回到B、访问B,4、根据B找到C，访问C,方法一、利用栈来实现回朔,X,34,.,1、树（子树）根入栈，不访问,2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤1,3、当左子树为空时，出栈，访问根结点,4、根节点右子树入栈（新树入栈，到步骤1去遍历右子树）,5、当右子树为空时，出栈，访问（祖先）爷结点，将爷结点的右子树入栈（新树入栈，回到步骤1),总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈,A,B,C,F,G,E,H,D,35,.,利用递归的遍历算法,方法二：利用递归调用来实现回溯中根遍历递归算法,templatestaticintrav(Btnode*p)if(p!=NULL)intrav(p-lchild);coutdrchild);return0;,左根右,36,.,后根遍历递归算法,templatestaticpostrav(Btnode*p)if(p!=NULL)postrav(