1、6 树与二叉树,树是由n（n0）个结点组成的有限集合。若n=0，则树是一棵空树；若n0，则树是一棵非空树。一棵非空树满足如下两个条件： 有且仅有一个特定的结点，称为根结点； 除根结点外的其他结点可分为m（m0）个互不相交的有限集合T1, T2, , Tm，其中每个集合本身又是一棵树，这些集合称为根结点的子树。,6.1 树的定义,T=A, B, C, D, E, F, G, H, I, J，K，L，MA是根，其余结点可划分为3个互不相交的集合：T1=B, E, F，K，L , T2=C, G , T3=D, H, I, J，M,6.1 树的定义,6.1 树的定义,树是一种非线性数据结构，其特点是
2、：1）树中每个结点都可以有零个或多个直接后继，若有多个后继结点，则后继结点是该结点的每个子树的根结点。2）除根结点之外的所有结点，有且仅有一个直接前驱。3）数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。4）树型结构中数据元素之间的关系是一对多或者多对一的关系。,6.2 树的基本术语,1结点的度和树的度结点具有的子树（分支）个数称为结点的度。一棵树中所有结点的度的最大值称为树的度。2叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。,6.2 树的基本术语,3双亲结点、孩子结点和兄弟结点树中每个结点的子树的根称为该结点的孩子或儿子或
3、子女；相应地，该结点称为孩子结点的双亲或父亲。具有同一个双亲的孩子们之间互称为兄弟。每个结点的祖先是从树的根结点到该结点所经过路径上的所有结点。反之，以某结点为根的子树中的所有结点都称为该结点的子孙。,6.2 树的基本术语,4结点的层数和树的高度结点的层数从树的根结点开始计算。假设树的根结点为第一层，它的孩子结点为第二层，其余类推。树中结点的最大层数就称为树的高度或深度。5森林森林是m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。6有序树和无序树若树中结点的各子树从左到右是有次序的，且相对次序是不能变换的，则该树被称为有序树，否则称为无序树。,6.3 二叉树的定义,二
4、叉树是有限的结点集合，这个集合或者为空，或者有一个根结点，它由两棵不相交的分别称为根的左子树和右子树的二叉树组成。左子树和右子树同样又都是一棵二叉树。,二叉树的5种基本形态,6.2 二叉树的定义,两棵不同的二叉树,一棵普通的无序树,6.3 二叉树的性质,性质1：在二叉树的第i 层上最多有2i-1个结点。性质2：深度为 h 的二叉树最多有 2h-1 (h=1)个结点。性质3：设二叉树叶子结点数为n0，度为2的结点数为n2，则 n0 = n2 +1。满二叉树：如果深度为 k 的二叉树，有2k-1个结点则称为满二叉树。,6.3 二叉树的性质,完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大
5、，并且最下层结点都集中在该层的最左端，则称为完全二叉树。性质4：具有n个结点的完全二叉树的深度为log2n+1,或 log2n +1,6.3 二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任一结点i (11，则其双亲是结点 i/2；2）2in：结点无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。3）2i+1n：结点无右孩子（结点I为叶子结点）；否则其右孩子是结点2i+1。,6.4 二叉树的顺序存储结构,把二叉树的所有结点，按照一定的次序顺序存放到一组地址连续的存储单元中。对完全二叉树中所有结点进行编号得到一个结点的线性序列，然后将完全二叉树各
6、结点按其编号顺序存放到一个一维数组中，即将完全二叉树上编号为 i 的结点存入一维数组下标为 i 的分量中。对于编号为 i 的结点，若有左孩子，它的左孩子的编号为 2i；若有右孩子，它的右孩子的编号为 2i+1。,6.4 二叉树的顺序存储结构,6.4 二叉树的顺序存储结构,普通二叉树的顺序存储方法,6.5 二叉树的链接存储结构,6.6 二叉树的遍历,按一定的次序“访问”二叉树的所有结点，使得每个结点仅被“访问”一次。实际上就是把二叉树的所有结点放入一个线性序列的过程。需要寻找一种规律来系统地访问二叉树的各个结点。三种方式：DLR，LDR，LRD,根,6.6 二叉树的遍历,其第一个元素值为二叉树中
7、根结点的数据值。,以根结点的数据值为界，将中序遍历序列分为两部分。,其最后一个元素值为二叉树中根结点的数据值。,算法见教材p76,6.6 二叉树的遍历,例如，有二叉树中序序列为：ABCEFGHD，后序序列为：ABFHGEDC，画出此二叉树。,6.6 二叉树的遍历,例如，假设先序遍历某二叉树的结点次序为ABCDEFGHIJ，中序遍历该二叉树的结点次序为CBEDAGHFJI，试画出此二叉树。,6.7 二叉树的遍历运算,（1）先序遍历二叉树的递归算法void preorder ( bitree *t ) if (t!=NULL) n=n+1; printf(tdata%2d=%3d, n, t-da
8、ta); /* 打印结点 */ preorder(t-lchild); /* 递归前序遍历左子树*/ preorder(t-rchild); /* 递归前序遍历右子树*/ /* PREORDER */,6.7 二叉树的遍历运算,（2）中序遍历二叉树的递归算法void inorder ( bitree *t ) if ( t!=NULL) inorder(t-lchild); /* 递归中序遍历左子树 */ printf(tdata%2d=%3d,t-data); /* 打印结点 */ inorder(t-rchild); /* 递归中序遍历右子树 */ /* INORDER */,6.7 二叉
9、树的遍历运算,“&A”，“&B”等表示结点A、B的地址,6.7 二叉树的遍历运算,（3）后序遍历二叉树的递归算法void postorder ( bitree *t ) if (t!=NULL) postorder(t-lchild); /* 递归后序遍历左子树*/ postorder(t-rchild); /* 递归后序遍历右子树*/ printf (t data%2d=%3d,t-data); /*打印结点 */ /* POSTORDER */,6.8 用递归方法建立二叉树,操作步骤：（1）将结点空指针引出孩子结点，得到一棵新二叉树。（2）前序遍历这棵新的二叉树得到一个前序序列，将此前序序
10、列作为该算法的输入序列，依次输入下列整数：23, 10, 0, 88, 0, 0, 15, 0, 34, 0, 0, 0（其中最后一个整数“0”表示结束标志），就可得到相应的二叉链表。,6.8 用递归方法建立二叉树,先序序列：23, 10, 0, 88, 0, 0, 15, 0, 34, 0, 0, 0,6.8 用递归方法建立二叉树,bitree *creat_preorder() bitree *t； datatype x; printf(ntt请输入正整数以0作为结束标志: ); scanf(%d, /* 返回树的根结点 */* CREAT_PREORDER */,6.9 二叉树的其他运算
11、,求二叉树的高度运算求二叉树的高度的递归模型如下： 0 若bt = NULL Max f (bt-lchild) , f ( bt-rchild ) + 1,f( bt ) =,6.9 二叉树的其他运算,求二叉树的高度运算Int BTHeight ( bitree *bt ) int lchilddep, rchilddep; if ( bt = = NULL) return ( 0 ); else lchilddep = BTHeight ( bt -lchild ); rchilddep = BTHeight ( bt-rchild ); return(lchilddeprchilddep
12、)?(lchilddep+1):(rchilddep +1 ); ,6.9 二叉树的其他运算,求二叉树结点个数运算算法对应的递归模型如下： 0 若bt = NULL f ( bt -lchild ) + f ( bt-rchild ) +1,f( bt ) =,6.9 二叉树的其他运算,求二叉树结点个数运算算法Int NodeCount ( bitree *bt ) int num1, num2; if ( bt = = NULL) return 0; Else num1 = NodeCount ( bt -lchild ); num2 = NodeCount ( bt -rchild );
13、return ( num1 + num2 +1 ); ,6.9 二叉树的其他运算,求二叉树叶子结点个数运算算法对应的递归模型如下： 0 bt = NULL 1 bt为叶子结点 F ( bt -lchild ) + f ( bt -rchild ) 其他情况,F (bt) =,6.9 二叉树的其他运算,求二叉树叶子结点个数运算算法Int LeafCount ( bitree *bt ) int num1, num2; if ( bt = = NULL ) return 0; else if ( bt -lchild = = NULL ,6.10 树的存储结构,孩子兄弟链表存储结构,Fchild
14、data nsibling,第一个孩子,下一个兄弟,6.10 树的存储结构,树的遍历两种方式先根遍历后根遍历,6.11 树、二叉树、森林的转换,6.11 树、二叉树、森林的转换,树、二叉树,习题,7 图,定义一个图G是由两个集合V(G)和E(G)组成的，图的二元组可定义为：G=(V, E) V(G)是顶点的有穷非空集合，每个顶点都可以标上不同的字符或数字。 E(G)是V中顶点边的有穷集合，而边是V中顶点的偶对。在特殊情况下，E(G)可以是空集。,7.1 图的定义,V(G1) = V1, V2, V3, V4 E(G1) = (V1, V2)，(V1, V3)，(V1, V4)， (V2, V3
15、)，(V2, V4)，(V3, V4),V(G3)=V1, V2, V3 E(G3)=， ,7.2 图的基本术语,顶点的度、入度和出度无向图中，与顶点v相邻接的边数称为该顶点的度。有向图中，以顶点v为终点的弧的数目称为顶点v的入度；以顶点v为起点的弧的数目称为顶点v的出度；有向图顶点v的度为该顶点的入度和出度之和。,弧,V1的度为3,V1的出度为2，入度为0,7.2 图的基本术语,完全图假设图的边或弧的两个顶点不能相同：有n(n1)/2条边的无向图称为无向完全图。有n(n1)条弧的有向图称为有向完全图。,7.2 图的基本术语,路径、回路和路径长度在无向图G中，若存在一个顶点序列（Vp , Vi
16、1 , , Vin , Vq），使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均为图G的边，则称从顶点Vp到顶点Vq存在一条路径。有向图路径由有向边，组成。路径长度定义为路径上的边数或者弧的数目。若一条路径上除起点Vp和终点Vq可以相同外，其余顶点均不重复出现，则称此路径为简单路径。起点和终点相同的路径（Vp=Vq）称为回路或环。除了起点和终点相同外，其余顶点不相同的回路，称为简单回路。,7.2 图的基本术语,子图,7.2 图的基本术语,连通、连通分量和连通图在无向图G中，如果从顶点Vi 到顶点Vj 有路径，则称Vi和Vj是连通的。如果图中任意两个不同的顶点Vi和Vj都连通则称
17、G为连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量即其自身，而非连通图有多个连通分量。,7.2 图的基本术语,连通、连通分量和连通图,7.2 图的基本术语,强连通、强连通分量和强连通图在有向图G中，如果从顶点Vi到顶点Vj有路径，则称从Vi到Vj是连通的。如果图中任意两个不同的顶点Vi和Vj都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。有向图G的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即其自身，非强连通的有向图有多个强连通分量。,7.2 图的基本术语,强连通、强连通分量和强连通图,7.3 图的存储结构,图的存储结构至少要保存两
18、类信息： 1）顶点的数据 2）顶点间的关系两种常用的图的存储表示方法： 1）邻接矩阵 2）邻接表,7.4 邻接矩阵的定义,假设G = (V, E)是具有n (n1)个顶点的图，则G的邻接矩阵A是一个具有下述性质的nn阶方阵： 1 若(vi,vj)E 或 E 0 否则,Aij =,7.4 邻接矩阵的定义,0 1 1 0 1 11 0 0 1 0 11 0 0 1 1 00 1 1 0 1 11 0 1 1 0 01 1 0 1 0 0,0 1 1 0 0 00 0 0 1 0 00 1 0 0 1 10 0 0 0 0 10 0 0 1 0 00 1 0 0 1 0,7.5 邻接矩阵的特点, 一
19、个图的邻接矩阵表示是惟一的。 对于无向图来说，它的邻接矩阵是关于主对角线对称的，因此，按照压缩存储的思想，只需要存放邻接矩阵的上三角矩阵（或下三角矩阵）。 借助邻接矩阵可以很容易判断出两个顶点是否有边相邻接，查找图中任意一条边或边上的权很方便。 顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1（或wij）或清0；图G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图。,7.5 邻接矩阵的特点,利用邻接矩阵能很容易计算出图中各顶点的度。无向图：有向图：有向图各顶点Vi 的总度数就等于出度与入度之和，即D(Vi)=OD(Vi)+ID(Vi)。,矩阵A中第i行（或第j列）非零元素
20、的个数,矩阵A中第i行非零元素的个数,矩阵A中第i列非零元素的个数,7.6 邻接表表示法,1邻接表的组成邻接表是一种顺序和链接相结合的图的存储方法：为图中每个顶点建立一个邻接关系的单链表，并把单链表的表头结点存储到一个数组中；数组下标i表示顶点Vi邻接表表头结点的存储位置；邻接表表头数组称为顶点表。,7.6 邻接表表示法,1邻接表的组成每个顶点都要建立一个邻接关系的单链表。无向图：第i个单链表中的结点表示依赖于顶点Vi的相邻边；有向图：它表示以顶点Vi为尾的弧。单链表中的结点用于存储以该顶点为起点的边的信息，称为边结点或表结点。,7.6 邻接表表示法,对于无向图，顶点Vi邻接表中的结点数就是顶
21、点Vi的度数、边数或邻接点数。,数据域,指针域,邻接域（序号）,7.6 邻接表表示法,对于有向图，顶点Vi邻接表中的结点数就是顶点Vi的出度数、出边数或出边邻接点数。,7.6 邻接表表示法,有向图的逆邻接表：第i个链表由图中以顶点Vi为终点的所有顶点链接而成。,7.7 邻接表的特点,一个图的邻接表表示不是惟一的。若一个图有n个顶点e条边，对于无向图，其邻接表中需要n+2e个结点，n个顶点构成顶点表，2e个边结点构成邻接表；对于有向图，则其邻接表中需要n+e个结点，n个顶点结点构成顶点表，e个边结点构成邻接表。在边稀疏的情况下，邻接表比邻接矩阵更节省存储空间。,7.7 邻接表的特点,在邻接表中，
22、查找图中某个顶点的边（出边）或邻接点（出边邻接点）很方便，只要从表头数组中取出对应的表头指针，然后从表头指针出发进行查找即可。借助于邻接表计算图中某顶点的度很容易。对于无向图，顶点Vi的度就是顶点Vi对应的第i个链表中的结点数；对于有向图，顶点Vi 对应的第i个单链表中的结点个数是顶点Vi的出度，但求顶点的入度比较难，须扫描整个邻接表。,7.8 图的遍历,图的遍历是指从任意指定的某个顶点（初始点）出发，按照一定的搜索方法依次访问图中所有顶点，且每个顶点仅被访问一次。为了避免同一个顶点被重复访问，必须记住每个顶点是否被访问过，为此可设置一个辅助数组visitedn，用来记录图中所有被访问过的顶点
23、。根据搜索路径不同，有两种遍历方法： 深度优先搜索遍历（DFS），广度优先搜索遍历（BFS）。,深度优先搜索的基本思想,首先访问初始出发点V0，并将其标记设置为已访问；然后任选一个与V0相邻接且没有被访问的邻接点V1访问，将其标记设置为已访问；再以V1为新的出发点，继续进行深度优先搜索，访问与V1相邻接且没有被访问的任一个顶点V2；重复上述过程，若遇到一个所有邻接点均被访问过的结点，则回到已访问结点序列中最后一个还没有被访问的相邻结点的顶点，再从该顶点出发继续进行深度优先搜索，直到图中所有顶点都被访问过，搜索结束。,深度优先搜索的基本思想,从顶点1出发进行深度优先遍历下面的无向图,广度优先搜索的基本思想,从图G = (V, E)的某个起始点V0出发，首先访问起始点V0，接着依次访问V0所有邻接点V1, V2, ,Vp，然后，分别从这些邻接点V1, V2, , Vp出发，按广度优先遍历的方法，依次访问与其相邻接的所有未被访问过的顶点；其余类推，直到图中所有顶点都被访问到为止。这个过程称为连通图的广度优先搜索遍历，简称BFS。,广度优先搜索的基本思想,对下面的无向图进行广度优先遍历，给出从顶点V1出发进行遍历的结果。,
