《树和二叉树》ppt课件2

《《树和二叉树》ppt课件2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树(1)主要内容树的定义和基本术语二叉树遍历二叉树线索二叉树树和森林赫夫曼树及其应用1、树的定义和基本术语树的定义：树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：⑴有且仅有一个特定的称为根的结点；⑵当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。树的定义是采用递归方法ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T

2、3T2树根例如:有向树：(１)有确定的根；(２)树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。数据结构中讨论的一般都是有序树基本术语（1）树的结点：数据元素和所有指向子树根的分支构成树中一个“结点”。结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。DHIJM基本术语（2）(从根到结点的)路径：由从根到该结点所经分支和结点构成。孩子、双亲：树中某结点子

3、树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点。兄弟：具有同一个双亲的孩子结点互称为兄弟。堂兄弟：其双亲在同一层的结点互为堂兄弟。结点的祖先：是从根到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。ABCDEFGHIJMKL基本术语（3）结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJAArootBCDEFGHIJ

4、MKLF基本术语（4）森林：是m（m≥0）棵互不相交的树的集合。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林树的抽象类型定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：P119}对比树型结构和

5、线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)2、二叉树2.1二叉树的定义2.2二叉树的性质2.3二叉树的存储结构2.1二叉树的定义二叉树的定义二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。研究二叉树

6、的意义？问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。二叉树的抽象数据类型定义：P121ABCDEFGHK根结点左子树右子树二叉树的特点：⑴每个结点最多有两棵子树；⑵二叉树是有序的，其次序不能任意颠倒。注意：二叉树和树是两种树结构。ABCDEFGABAB具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结构。二叉树的基本形态Ф空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树特殊的二叉树1、斜树（1）所有结点都只有左子树的二叉树称

7、为左斜树；（2）所有结点都只有右子树的二叉树称为右斜树；（3）左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。斜树的特点：ABCABC特殊的二叉树2、满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。A15234678910BCDEFGHIJKLMNO1112131415特殊的二叉树满二叉树不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二

8、叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM893、完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。A15234678910BCDEFGHIJKLMNO1112131415A15234678910BCDEFGHIJ特殊的二叉树在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即