《2019年《树和二叉树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《2019年《树和二叉树》PPT课件.ppt（36页珍藏版）》请在三一文库上搜索。
1、执行校长,李 伟,树和二叉树,数据结构(第十一讲 ),课程回顾,什么是稀疏矩阵 稀疏矩阵表示 广义表定义,本讲目录,树的定义和基本术语 二叉树,本讲重点、难点,重点 二叉树的定义 二叉树的性质 二叉树的存储结构 难点 二叉树的定义 二叉树的性质,树的定义和基本术语,树的定义和基本术语 二叉树,树的定义,树的定义,示例：家族树,树的定义,示例本书的目录,树的定义,树的定义 树是由n (n 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n 0，则: 有一个特定的称之为根(root)的结点，它只有后继，但没有前驱； 除根以外的其它结点划分为m(m0)个互不相交的有限集合T1, T2,
2、, Tm。 每个集合本身又是一棵树，并且称之为根的子树(subTree)。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。 树的定义是递归的。,树的定义,示例,图(a) 是一棵空树，没有结点 图(b) 是一棵只有根结点的树，根结点是A 图(c) 是一棵有13个结点的树，其中A是根结点 三个互不相交的子集：T1=B,E,F,K,L,T2=C,G,T3=D,H,I,J,M,树的定义,抽象数据类型树的定义 ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时
3、，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 基本操作P：(见教材) ADT Tree,树的表示 树的逻辑表示方法有多种，常见的有 ： 树形图表示法 嵌套集合表示法（文氏图表示法） 凹入表示法 广义表表示法,树的定义,树的基本术语,基本术语 结点：数据元素+若干指向子树的分支 结点的度：分支的个数（或 子树的个数） 叶子结点（终端结点）：度为零的结点 分支结点（非终端结点）：度不等于零的结点 树的度：树中所有结点的度的最大值 孩子结点：结点的子树的根结点为该结点的孩子结点 双亲结点：与孩子结点相
4、对应的结点 兄弟结点：同一个双亲的孩子结点之间的互称 祖先结点：从根结点起到该结点所经分支上的所有结点 子孙结点：以某结点为根的子树中的任意结点,树的基本术语,基本术语 层次：从根结点起，根结点为第一层，跟的孩子为第二层，依次类推 假设根结点的层次为1,第l 层的结点的子树根结点的层次为 l+1 堂兄弟：双亲在同一层的结点互称 深度：树中叶子结点所在的最大层次 有序树：子树之间存在确定的次序关系 无序树：子树之间不存在确定的次序关系 森林：是m（m0）棵互不相交的树的集合。 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林,F,A,r
5、oot,二叉树,树的定义和基本术语 二叉树,二叉树的定义,二叉树的定义 二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。 二叉树的每个结点至多只有两棵子树（结点的度最多为2）。 二叉树的子树有左右之分，其次序不能任意颠倒。,根结点,右子树,左子树,E,F,二叉树的定义,抽象数据类型二叉树的定义 ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空二叉树； 否则: (1) 在D中存在唯一的称为根的数据元素root (2) 当n1时，其余结点可分为2个互不相
6、交的有限集 Dl，Dr (3)若Dl ， Dr都不为空集，则Dl ， Dr本身又是一棵符合 本定义的二叉树，称为根root的左右子树。 基本操作P：(见教材) ADT BinaryTree,二叉树的定义,二叉树的5种基本形态,A,A,B,A,B,A,C,B,(b) 根和空的左右子树,(c) 根和左子树,(d) 根和右子树,(e) 根和左右子树,(a) 空二叉树,53！=30棵,二叉树的定义,示例：由三个结点组成的二叉树的基本类型有几种？,由三个结点组成的二叉树的基本形态有5种。,如果这三个结点分别是A,B,C。则可以组成几棵二叉树？,二叉树的性质,二叉树的性质 性质1：在二叉树的第i层上至多有
7、2i-1 个结点。(i1) 证明：,用归纳法证明： 归纳基： i = 1 层时，只有一个根结点， 2i-1 = 20 = 1； 归纳假设：假设对所有的 j，1 j i，命题成立; 归纳证明：二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。,按照题意，二叉树除最后一层，其余每一层上的结点都有两个孩子结点，则每一层均比上一层的结点个数多一倍。 按照等比数列的定义，每一项都可以看作是相应每一层上的结点个数，则，ai=ai*qi-1=2i-1,二叉树的性质,性质2：深度为k的二叉树上至多含2k-1个结点（k1） 证明：,基于上一条性质，深度为 k 的二叉树上的结
8、点数至多为 20+21+ +2k-1 = 2k-1,二叉树的性质,性质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 的结点一一对应。,特点：每一层上的结点数都是最大结点数,特点： 叶子结点只能在层次最大的两层出现 任意
9、结点，若其右分支下的子孙最大层数为L,则左分支下的子孙的最大层次为L或L+1,两类特殊的二叉树,二叉树的性质,性质4：具有n个结点的完全二叉树的深度为 log2n +1,证明：,设 完全二叉树的深度为 k,则 根据第二条性质得 2k-1 n 2k,即 k-1 log2 n k,因为 k 只能是整数， 因此， k =log2n + 1,二叉树的性质,性质 5 ：若对含 n 个结点的完全二叉树从上到 下且从左至右进行 1 至 n 的编号，则对完全二 叉树中任意一个编号为 i 的结点： 若 i=1，则该结点是二叉树的根，无双亲, 否 则，编号为 i/2 的结点为其双亲结点; 若 2in，则该结点无左
10、孩子， 否则，编号为 2i 的结点为其左孩子结点； 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,二叉树的性质,二叉树的存储结构,顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。 必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：从树根起，自上层至下层，每层自左至右的给所有结点编号。 顺序存储表示 #define MAX_TREE_SIZE 100 typedef int TElemType; typedef TElemType SqBiTreeMAX_TREE_SIZE； Sq
11、BiTree bt;,二叉树的存储结构,示例：完全二叉树的数组表示,二叉树的存储结构,示例：一般二叉树的数组表示,0,0,0,0,0,二叉树的存储结构,顺序存储结构的缺点 由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。 若经常需要插入与删除树中结点时，顺序存储方式需要大量移动数据。,二叉树的存储结构,链式存储结构 二叉链表 二叉链表结构：数据域、左指针域、右指针域,二叉链表存储表示： typedef char TElemType; typedef struct BiTNode TElemType data; struct BiTNode *lchild，*rchild；/左右孩子指针 BiTNode，*BiTree；,二叉树的存储结构,链式存储结构 三叉链表 三叉链表结构：数据域、左指针域、右指针域、双亲指针域,思考：二叉树的三叉链表存储表示如何定义？,二叉树的存储结构,二叉树链式存储结构示例,教学内容,树的定义和基本术语 二叉树,本讲总结,为什么说树的定义是递归的？ 二叉树的性质有哪些？ 二叉树的顺序存储结构有什么缺点？,上机实验,实验14-1 建立一棵含有n个结点的二叉树，采用二叉链表存储（ex6-1.c）,Thank You !,