中国著名特级教师教学思想录96

《中国著名特级教师教学思想录96》由会员分享，可在线阅读，更多相关《中国著名特级教师教学思想录96（56页珍藏版）》请在金锄头文库上搜索。

1、树和图,西安交通大学计教中心 ,树的递归定义:,树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足： 1）其中有一个特定的元素称为T的根root。 2）除根以外的集合可被划分为m个不相交的子集T1，T2，Tm，其中每个子集都是树。它们称为根root的子树。,与树相关的术语, 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度的最大值。 叶子结点：没有非空子树的结点。 分支结点：至少有一个非空子树的结点。 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称

2、为其孩子结点的父结点。, 兄弟结点：具有相同父结点的结点互为兄弟结点。 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 树的深度：树中结点所在的最大层次。 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 森林：由零棵或有限棵互不相交的树组成的集合。,二叉树的定义,二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。,特殊形式的二叉树,满二叉树：当二叉树每个分支结点的度都

3、是2，且所有叶子结点都在同一层上，则称其为满二叉树。 完全二叉树：从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。满二叉树可看作是完全二叉树的一个特例。,二叉树有下列重要性质：,（1）在二叉树的第k层上至多有2k-1个结点(k1) 证明：当k=1时，命题显然成立。假定k=n-1时命题成立，则第n层（k=n）的结点数最多是第n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结点。命题成立。 （2）深度为h的二叉树上至多含2h-1个结点(h1) 证明：根据性质1容易知道深度为h的二叉树最多有20+21+2h-1个结点，即最多有2h-1个结点。,（3）包含n

4、(n0)个结点的二叉树总的分支数为n-1 证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。,（4）任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n0=n2+1 证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为： n0 + n1 + n2 （2-2） 再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1

5、 + 2n2 （2-3） 由（2-2）（2-3）两式可知：n0=n2+1,（5）具有n个结点的完全二叉树的深度为log2(n)+1 证明：假设二叉树的深度为h，则必有2h-1-1n2h-1，于是有2h-1n+12h，也就是 2h-1n2h，从而得到h-1log2(n)h，于是h=log2(n)+1。,（6） 若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点： 若i=1，则该结点是二叉树的根，无父结点。否则，编号为i/2的结点为其父结点； 若2in，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点； 若2i+1n，则该结点无右孩子。否则，编号

6、为2i+1的结点为其右孩子结点。 证明通过对i进行归纳即可得证。,二叉树的链式存储,结点定义： struct BinTreeNode ElemType data; struct BinTreeNode *leftChild, *rightChild; ; 这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶子结点或一个新生成的结点而言，其左孩子和右孩子指针都应为空值。,利用这种结点形式存储的树一般称为二叉链表。 从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。,二叉树的常用算法包括

7、：获取根结点指针、判断树是否为空、插入或删除结点、插入或删除子树、二叉树遍历等。 二叉树类可描述如下： class BinTree public: BinTreeNode *root; /定义根结点指针 BinTree() root=NULL; /构造函数，定义空树 /判断树是否为空 bool IsEmpty() return root=NULL; /在叶子结点p下插入左子树q void Ins_lchild(BinTreeNode *p,BinTreeNode *q) p-leftChild=q; ( 接下页 ),( 接上页 ) /在叶子结点p下插入右子树q void Ins_rchild(

8、BinTreeNode *p,BinTreeNode *q) p-rightChild=q; /删除结点p的左子树 void Del_lchild(BinTreeNode *p) p-leftChild=NULL; /删除结点p的右子树 void Del_rchild(BinTreeNode *p) p-rightChild=NULL; void PreOrder(BinTreeNode *t); /先序遍历 void InOrder(BinTreeNode *t); /中序遍历 void PostOrder(BinTreeNode *t); /后序遍历 ;,二叉树的遍历,二叉树遍历是只按照某

9、种顺序访问二叉树的每个结点，并且每个结点只被访问一次。这是二叉树中经常用到的操作，有三种主要的遍历算法先序遍历、中序遍历和后序遍历。,（1）先序遍历 对一颗非空二叉树进行先序遍历时，首先访问根结点，然后按先序遍历方式访问左子树，最后按先序遍历方式访问右子树。先序遍历算法如下： void BinTree:PreOrder(BinTreeNode *t) if (t) Visit( t ); /访问根结点 PreOrder( t-leftChild ); /遍历左子树 PreOrder( t-rightChild ); /遍历右子树 ,（2）中序遍历 对一颗非空二叉树进行中序遍历时，首先按中序遍历

10、方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。中序遍历算法如下： void BinTree:InOrder(BinTreeNode *t) if(t) InOrder( t-leftChild ); / 遍历左子树 Visit( t ); / 访问根节点 InOrder( t-rightChild ); / 遍历右子树 ,（3）后序遍历 对一颗非空二叉树进行中序遍历时，首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点。后序遍历算法如下： void BinTree:PostOrder(BinTreeNode *t) if(t) PostOrder( t-

11、leftChild ); /遍历左子树 PostOrder( t-rightChild ); /遍历右子树 Visit( t ); /访问根节点 ,图的基本概念,图的来源：通信网、交通网等，它表现了数据对象间多对多的联系。在该结构中，数据元素一般称为顶点。 图的定义： 图是由顶点集合及顶点间的关系集合组成的一种数据结构。一般记作Graph( V, E )。其中V是顶点的有限非空集合；E是顶点之间关系的有限集合。,以下是图的相关术语 边：若顶点x到y是的一条双向通路，则称为边，用(x，y)表示。 弧：若顶点x到y是的一条单向通路，则称为弧，用表示。 邻接点：如果(x,y)是图中的一条边，则称x与

12、y互为邻接点；如果是图中的一条弧，则称y为x的邻接点。 顶点的度：一个顶点v的度是与它相关联的边的条数。, 无向图：若图是由一些顶点和边构成则称之为无向图。 有向图：若图是由一些顶点和弧构成则称之为有向图。 权：某些图的边或弧具有与它相关的数，称之为权。这种带权图叫做网络。, 路径：在图中，若从顶点vi出发，沿一些边或弧，经过顶点vp1，vp2，vpm，到达顶点vj。则称顶点序列( vi，vp1，vp2，vpm，vj )为从顶点vi到顶点vj的路径。若路径上各顶点均不互相重复，则称这样的路径为简单路径。 路径长度：非带权图的路径长度是指此路径上边或弧的条数，带权图的路径长度是指路径上各边或弧的

13、权之和。, 子图：设有两个图G(V，E)和G(V，E)。若V包含V且E包含E，则称图G是图G的子图。 连通图：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。 强连通图：在有向图中，若对于每一对顶点vi和vj，都存在从vi到vj和从vj到vi的路径，则称此图是强连通图。, 生成树：一个连通图的生成树是它的极小连通子图。即包含了所有顶点以及最少的边或弧的子图，并且这些边或弧使得任意两顶点相互连通。在含有n个顶点的无向图中，生成树一定有n-1条边，且生成树的形式可能有多个。,图的存储方式,1邻接矩阵 利用数组实现的。它利用一维

14、数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵。 邻接矩阵 存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,图的邻接矩阵存储可以用下面的结构体表示： #define MAX_NUM 100 / 最大顶点个数 typedef struct VertexType vexsMAX_NUM; /顶点信息数组 ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵 int vexnum,arcnum; /图的实际顶点数和弧(边)数 int kind; /图的种类标志, 1有向图, /2有向网,3无向图,4无向网 MG

15、raph; 其中ArcType是顶点关系的数据类型。VertexType是顶点的数据类型。MAX_NUM表示最多可存的顶点数。,假设无向图G=(V,E)是一个有n个顶点的图，则图的邻接矩阵A是n阶方阵，其内容如下：,其中W(i, j)是与边或弧相关的权。,对于含权的网络而言，其邻接矩阵可定义如下：,(a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵,2邻接表 邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。 （1）头结点都存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。 （2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。 （3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。,邻接表的结点结构,(c)网络的表结点,(a)头结点,(b)无权图的表结点,图的邻接表描述,#define MAX_NUM 100 /顶点最大允许数量 struct AdjNode /表结点类型定义 int adjvex; /该邻接点在数组中的位置 InfoType info; /该弧相关信息 struct AdjNode *next; /指向下一邻接点的指针 ; typedef stru