数据结构队列、栈、二叉树、图.ppt

《数据结构队列、栈、二叉树、图.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、QQ群号常见数据结构线性表、栈、队列、二叉树、图（一）、线性表线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继，如图2.1所示。例如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B后面是字母C。（二）、栈栈是允许在一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固

2、定，而栈顶浮动；栈中元素个数为零时称为空栈。栈结构也称为后进先出表（LIFO）。a1a2……an栈底栈顶MAXSIZETOP队列(Queue)的定义队列是限定仅在表的一端进行插入，在另一端进行删除操作的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)。队列的插入操作，称为入队；队列的删除操作，称为出队。当队列中没有元素时称为空队列。设队列q=(a0，a1，a2，…，an-1)，则a0称为队头元素，an-1称为队尾元素。元素按a0，a1，a2，…，an-1的次序入队，出队也只能按照这个

3、次序。队列和栈相反，队列的操作是按先进先出（FirstInFirstOut）的原则进行的，又称为先进先出的线性表（简称FIFO表）。三、队列（四）、二叉树类型与定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树介绍基本术语叶子结点结点结点总数深度层abcdefghij结点的层次从根开始定义起，根为第一层，根的孩子为第二层，依次累计。树中结点的最

4、大层次称为树的深度或高度。性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点，2i-1=20=1；假设对所有的j，1≤ji，命题成立;二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关

5、系式：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的结点一一对应。123456789101112131415abcdefghij性质4：具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k即k-1≤log2n

6、因此，k=log2n+1满二叉树的叶节点为N，则它的节点总数（）A、NB、2NC、2N-1D、2N+1E、2^N-1高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。A.10B.11C.12D.13二叉树的遍历顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。对“二叉树”而

7、言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法根左子树右子树根根根根根若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）

8、后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：ABCDEFGHK例如：先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDCBHKGFEA前缀、后缀表达式二叉树的应用。中缀表达式转换后缀表达式从左向右扫描表达式、运算数送到输出队列、运算符进栈、如果运算优先级大于栈顶元素直接进栈，如果运算优先级小于或等于栈顶元素，则先弹出栈顶元素，再