《树和二叉树》教学课件

《树和二叉树》幻灯片本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！《树和二叉树》幻灯片本课件PPT仅供大家学习使用课程回忆什么是稀疏矩阵稀疏矩阵表示广义表定义课程回忆什么是稀疏矩阵本讲目录树的定义和根本术语二叉树树的定义树的基本术语二叉树的定义二叉树的性质二叉树的存储结构本讲目录树的定义和根本术语树的定义二叉树的定本讲重点、难点重点二叉树的定义二叉树的性质二叉树的存储构造难点二叉树的定义二叉树的性质本讲重点、难点重点树的定义和根本术语树的定义和根本术语二叉树树的定义树的基本术语树的定义和根本术语树的定义和根本术语树的定义树的定义树型结构是一类重要的非线性数据结构。直观看来树是以分支关系定义的层次结构。树型结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也有着广泛的应用，如在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。树的定义树型结构是一类重要的非线性数据结构。树的定义例如：家族树树的定义例如：家族树树栈和队列数组和广义表线性表和广义表数据结构……线性表广义表栈队列……树的定义例如本书的目录树栈和队列数组和广义表线性表和广义表数据结构……线性表广义表树的定义树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，那么:有一个特定的称之为根(root)的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m>0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的定义是递归的。树的定义树的定义树的定义例如图(a)是一棵空树，没有结点图(b)是一棵只有根结点的树，根结点是A图(c)是一棵有13个结点的树，其中A是根结点三个互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}树的定义例如图(a)是一棵空树，没有结点树的定义抽象数据类型树的定义ADTTree{数据对象D：D是具有一样特性的数据元素的集合。数据关系R：假设D为空集，那么称为空树；否那么:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。根本操作P：(见教材)}ADTTree树的定义抽象数据类型树的定义树的表示树的逻辑表示方法有多种，常见的有：树形图表示法嵌套集合表示法〔文氏图表示法〕凹入表示法广义表表示法树的定义树的表示树的定义树的根本术语根本术语结点：数据元素+假设干指向子树的分支结点的度：分支的个数〔或子树的个数〕叶子结点〔终端结点〕：度为零的结点分支结点〔非终端结点〕：度不等于零的结点树的度：树中所有结点的度的最大值孩子结点：结点的子树的根结点为该结点的孩子结点双亲结点：与孩子结点相对应的结点兄弟结点：同一个双亲的孩子结点之间的互称祖先结点：从根结点起到该结点所经分支上的所有结点子孙结点：以某结点为根的子树中的任意结点树的根本术语根本术语树的根本术语根本术语层次：从根结点起，根结点为第一层，跟的孩子为第二层，依次类推假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1堂兄弟：双亲在同一层的结点互称深度：树中叶子结点所在的最大层次有序树：子树之间存在确定的次序关系无序树：子树之间不存在确定的次序关系森林：是m〔m≥0〕棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=〔root，F〕其中：root被称为根结点，F被称为子树森林CGFHIJMDEKLBFAroot树的根本术语根本术语CGFHIJMDEKLBFAroot二叉树树的定义和根本术语二叉树二叉树的定义二叉树的性质二叉树的存储结构二叉树树的定义和根本术语二叉树的定义二叉树的定义二叉树的定义二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树的每个结点至多只有两棵子树〔结点的度最多为2〕。二叉树的子树有左右之分，其次序不能任意颠倒。根结点右子树左子树EFHKCBADGEF二叉树的定义二叉树的定义根结点右子树左子树EFHKCBADG二叉树的定义抽象数据类型二叉树的定义ADTBinaryTree{数据对象D：D是具有一样特性的数据元素的集合。数据关系R：假设D为空集，那么称为空二叉树；否那么:(1)在D中存在唯一的称为根的数据元素root(2)当n>1时，其余结点可分为2个互不相交的有限集Dl，Dr(3)假设Dl，Dr都不为空集，那么Dl，Dr本身又是一棵符合本定义的二叉树，称为根root的左右子树。根本操作P：(见教材)}ADTBinaryTree二叉树的定义抽象数据类型二叉树的定义二叉树的定义二叉树的5种根本形态AABABACB

(b)根和空的左右子树

(c)根和左子树(d)根和右子树(e)根和左右子树

(a)空二叉树二叉树的定义二叉树的5种根本形态AABABACB(5×3！=30棵二叉树的定义例如：由三个结点组成的二叉树的根本类型有几种？由三个结点组成的二叉树的根本形态有5种。如果这三个结点分别是A,B,C。那么可以组成几棵二叉树？5×3！=30棵二叉树的定义例如：由三个结点组成的二叉树的根二叉树的性质二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)证明：用归纳法证明：归纳基：i=1层时，只有一个根结点，2i-1=20=1；归纳假设：假设对所有的j，1≤ji，命题成立;归纳证明：二叉树上每个结点至多有两棵子树，那么第i层的结点数=2i-22=2i-1。按照题意，二叉树除最后一层，其余每一层上的结点都有两个孩子结点，那么每一层均比上一层的结点个数多一倍。按照等比数列的定义，每一项都可以看作是相应每一层上的结点个数，那么，ai=ai*qi-1=2i-1二叉树的性质二叉树的性质用归纳法证明：按照题意，二叉树除最后二叉树的性质性质2：深度为k的二叉树上至多含2k-1个结点〔k≥1〕证明：基于上一条性质，深度为k

的二叉树上的结点数至多为

20+21++2k-1=2k-1

二叉树的性质性质2：深度为k的二叉树上至多含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二叉树的性质性质3：对任何一棵二叉树，假设它含有n0个叶子满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1

至n

的结点一一对应。123456789101112131415abcdefghij特点：每一层上的结点数都是最大结点数特点：叶子结点只能在层次最大的两层出现任意结点，假设其右分支下的子孙最大层数为L,那么左分支下的子孙的最大层次为L或L+1两类特殊的二叉树二叉树的性质满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二性质4：具有n个结点的完全二叉树的深度为

log2n+1证明：设完全二叉树的深度为k

那么根据第二条性质得2k-1≤n<2k即k-1≤log2n<k

因为k

只能是整数，因此，k=log2n

+1二叉树的性质性质4：具有n个结点的完全二叉树的深度为证明：设完全二叉树性质5：假设对含n个结点的完全二叉树从上到下且从左至右进展1至n的编号，那么对完全二叉树中任意一个编号为i的结点：假设i=1，那么该结点是二叉树的根，无双亲,否那么，编号为i/2的结点为其双亲结点;假设2i>n，那么该结点无左孩子，

否那么，编号为2i的结点为其左孩子结点；假设2i+1>n，那么该结点无右孩子结点，

否那么，编号为2i+1的结点为其右孩子结点。二叉树的性质性质5：假设对含n个结点的完全二叉树从上到二叉树的二叉树的存储构造顺序存储构造它是用一组连续的存储单元存储二叉树的数据元素。必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：从树根起，自上层至下层，每层自左至右的给所有结点编号。顺序存储表示#defineMAX_TREE_SIZE100typedefintTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE]；SqBiTreebt;二叉树的存储构造顺序存储构造二叉树的存储构造例如：完全二叉树的数组表示二叉树的存储构造例如：完全二叉树的数组表示二叉树的存储构造例如：一般二叉树的数组表示00000二叉树的存储构造例如：一般二叉树的数组表示00000二叉树的存储构造顺序存储构造的缺点由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。假设经常需要插入与删除树中结点时，顺序存储方式需要大量移动数据。二叉树的存储构造顺序存储构造的缺点二叉树的存储构造链式存储构造二叉链表二叉链表构造：数据域、左指针域、右指针域

lchilddatarchild二叉链表存储表示：typedefcharTElemType;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild，*rchild；//左右孩子指针}BiTNode，*BiTree；二叉树的存储构造链式存储构造lchilddat二叉树的存储构造链式存储构造三叉链表三叉链表构造：数据域、左指针域、右指针域、双亲指针域

lchilddataparentrchild思考：二叉树的三叉链表存储表示如何定义？二叉树的存储构造链式存储构造lchild二叉树的存储构造二叉树链式存储构造例如二叉树的存储构造二叉树链式存储构造例如教学内容树的定义和根本术语二叉树树的定义树的基本术语二叉树的定义二叉树的性质二叉树的存储结构教学内容树的定义和根本术语树的定义二叉树的定本讲总结为什么说树的定义是递归的？二叉树的性质有哪些？二叉树的顺序存储构造有什么缺点？本讲总结为什么说树的定义是递归的？上机实验实验14-1建立一棵含有n个结点的二叉树，采用二叉链表存储〔ex6-1.c〕上机实验实验14-1ThankYou!ThankYou!《树和二叉树》幻灯片本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！本课件PPT仅供大家学习使用学习完请自行删除，谢谢！《树和二叉树》幻灯片本课件PPT仅供大家学习使用课程回忆什么是稀疏矩阵稀疏矩阵表示广义表定义课程回忆什么是稀疏矩阵本讲目录树的定义和根本术语二叉树树的定义树的基本术语二叉树的定义二叉树的性质二叉树的存储结构本讲目录树的定义和根本术语树的定义二叉树的定本讲重点、难点重点二叉树的定义二叉树的性质二叉树的存储构造难点二叉树的定义二叉树的性质本讲重点、难点重点树的定义和根本术语树的定义和根本术语二叉树树的定义树的基本术语树的定义和根本术语树的定义和根本术语树的定义树的定义树型结构是一类重要的非线性数据结构。直观看来树是以分支关系定义的层次结构。树型结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也有着广泛的应用，如在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。树的定义树型结构是一类重要的非线性数据结构。树的定义例如：家族树树的定义例如：家族树树栈和队列数组和广义表线性表和广义表数据结构……线性表广义表栈队列……树的定义例如本书的目录树栈和队列数组和广义表线性表和广义表数据结构……线性表广义表树的定义树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，那么:有一个特定的称之为根(root)的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m>0)个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的定义是递归的。树的定义树的定义树的定义例如图(a)是一棵空树，没有结点图(b)是一棵只有根结点的树，根结点是A图(c)是一棵有13个结点的树，其中A是根结点三个互不相交的子集：T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}树的定义例如图(a)是一棵空树，没有结点树的定义抽象数据类型树的定义ADTTree{数据对象D：D是具有一样特性的数据元素的集合。数据关系R：假设D为空集，那么称为空树；否那么:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。根本操作P：(见教材)}ADTTree树的定义抽象数据类型树的定义树的表示树的逻辑表示方法有多种，常见的有：树形图表示法嵌套集合表示法〔文氏图表示法〕凹入表示法广义表表示法树的定义树的表示树的定义树的根本术语根本术语结点：数据元素+假设干指向子树的分支结点的度：分支的个数〔或子树的个数〕叶子结点〔终端结点〕：度为零的结点分支结点〔非终端结点〕：度不等于零的结点树的度：树中所有结点的度的最大值孩子结点：结点的子树的根结点为该结点的孩子结点双亲结点：与孩子结点相对应的结点兄弟结点：同一个双亲的孩子结点之间的互称祖先结点：从根结点起到该结点所经分支上的所有结点子孙结点：以某结点为根的子树中的任意结点树的根本术语根本术语树的根本术语根本术语层次：从根结点起，根结点为第一层，跟的孩子为第二层，依次类推假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1堂兄弟：双亲在同一层的结点互称深度：树中叶子结点所在的最大层次有序树：子树之间存在确定的次序关系无序树：子树之间不存在确定的次序关系森林：是m〔m≥0〕棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=〔root，F〕其中：root被称为根结点，F被称为子树森林CGFHIJMDEKLBFAroot树的根本术语根本术语CGFHIJMDEKLBFAroot二叉树树的定义和根本术语二叉树二叉树的定义二叉树的性质二叉树的存储结构二叉树树的定义和根本术语二叉树的定义二叉树的定义二叉树的定义二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树的每个结点至多只有两棵子树〔结点的度最多为2〕。二叉树的子树有左右之分，其次序不能任意颠倒。根结点右子树左子树EFHKCBADGEF二叉树的定义二叉树的定义根结点右子树左子树EFHKCBADG二叉树的定义抽象数据类型二叉树的定义ADTBinaryTree{数据对象D：D是具有一样特性的数据元素的集合。数据关系R：假设D为空集，那么称为空二叉树；否那么:(1)在D中存在唯一的称为根的数据元素root(2)当n>1时，其余结点可分为2个互不相交的有限集Dl，Dr(3)假设Dl，Dr都不为空集，那么Dl，Dr本身又是一棵符合本定义的二叉树，称为根root的左右子树。根本操作P：(见教材)}ADTBinaryTree二叉树的定义抽象数据类型二叉树的定义二叉树的定义二叉树的5种根本形态AABABACB

(b)根和空的左右子树

(c)根和左子树(d)根和右子树(e)根和左右子树

(a)空二叉树二叉树的定义二叉树的5种根本形态AABABACB(5×3！=30棵二叉树的定义例如：由三个结点组成的二叉树的根本类型有几种？由三个结点组成的二叉树的根本形态有5种。如果这三个结点分别是A,B,C。那么可以组成几棵二叉树？5×3！=30棵二叉树的定义例如：由三个结点组成的二叉树的根二叉树的性质二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)证明：用归纳法证明：归纳基：i=1层时，只有一个根结点，2i-1=20=1；归纳假设：假设对所有的j，1≤ji，命题成立;归纳证明：二叉树上每个结点至多有两棵子树，那么第i层的结点数=2i-22=2i-1。按照题意，二叉树除最后一层，其余每一层上的结点都有两个孩子结点，那么每一层均比上一层的结点个数多一倍。按照等比数列的定义，每一项都可以看作是相应每一层上的结点个数，那么，ai=ai*qi-1=2i-1二叉树的性质二叉树的性质用归纳法证明：按照题意，二叉树除最后二叉树的性质性质2：深度为k的二叉树上至多含2k-1个结点〔k≥1〕证明：基于上一条性质，深度为k

的二叉树上的结点数至多为

20+21++2k-1=2k-1

二叉树的性质性质2：深度为k的二叉树上至多含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二叉树的性质性质3：对任何一棵二叉树，假设它含有n0个叶子满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1

至n

的结点一一对应。123456789101112131415abcdefghij特点：每一层上的结点数都是最大结点数特点：叶子结点只能在层次最大的两层出现任意结点，假设其右分支下的子孙最大层数为L,那么左分支下的子孙的最大层次为L或L+1两类特殊的二叉树二叉树的性质满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二性质4：具有n个结点的完全二叉树的深度为

log2n+1证明：设完全二叉树的深度为k

那么根据第二条性质得2k-1≤n<2k即k-1≤log2n<k

因为k

只能是整数，因此，k=log2n

+1二叉树的性质性质4：具有n个结点的完全二叉树的深度为证明：设完全二叉树性质5：假设对含n个结点的完全二叉树从上到下且从左至右进展1至n的编号，那么对完全二叉树中任意一个编号为i的结点：假设i=1，那么该结点是二叉树的根，无双亲,否那么，编号为i/2的结点为其双亲结点;假设2i>n，那么该结点无左孩子，

否那么，编号为2i的结点为其左孩子结点；假设2i+1>n，那么该结点无右孩子结点，

否那么，编号为2i+1的结点为其右孩子结点。二叉树的性质性质5：假设对含n个结点的完全二叉树从上到二叉树的二叉树的存储构造顺序存储构造它是用一组连续的存储单元存储二叉树的数据元素。必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法