数据结构(线性表、栈、队列、二叉树、图).pptVIP

又如，有6个足球队之间进行循环赛，他们比赛的场次可以用图1-3(1)来表示。有3个人相互写信，可以用图1—3(2)来表示。从上面两个例子可看出，我们这里所说的图(graph)，与人们通常所熟悉的图，如圆、四边形、函数图象等是很不相同的。是指某些具体事物和这些事物之间的联系。如果我们用点来表示事物(如地点、队)，用线段来表示两事物之间的联系，那么一个图就是表示事物的点集和表示事物之间联系的线段集合所构成。其中线段仅表示两点的关系，它的长短与曲直是无关紧要的。例如图1-4中3个图，被认为是同一个图。常见数据结构线性表、栈、队列、二叉树、图（一）、线性表线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，如图2.1所示。例如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。（二）、栈栈是允许在一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。a1a2……an栈底栈顶MAXSIZETOP队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。设队列q=(a0，a1，a2，…，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2，…，an-1的次序入队，出队也只能按照这个次序。队列和栈相反，队列的操作是按先进先出（FirstInFirstOut）的原则进行的，又称为先进先出的线性表（简称FIFO表）。队列(Queue)的定义三、队列（四）、二叉树类型与定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树介绍基本术语叶子结点结点结点总数深度层abcdefghij结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次累计。树中结点的最大层次称为树的深度或高度。性质1：

在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点，2i-1=20=1；假设对所有的j，1≤j?i，命题成立;二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-2?2=2i-1。证明：1基于上一条性质，深度为k的二叉树上的结点数至多为220+21+??????+2k-1=2k-1性质2：

深度为k的二叉树上至多含2k-1个结点（k≥1）3性质3：

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。1234567891011121314abcdefghij性质4：

具有n个结点的完全二叉树的深度为?log2n?+1证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n2k即k-1≤log2nk因为k只能是整数，因此，k=?log2n?+1满二叉树的叶节点为N，则它的节点总数（）A、NB、2N