清华大学：《数据结构》课程电子教案（PPT课件讲稿）第6章 树和二叉树

第6章树和二叉树 树的定义和基本术语 二叉树( Binary Tree 二叉树的存储结构 遍历二叉树( Binary Tree Traversal 线索化二叉树( Threaded Binary tree 树与森林(Tree& Forest 赫夫曼树( Huffman tree 二叉树的让数

树的定义和基本术语 二叉树 (Binary Tree) 二叉树的存储结构 遍历二叉树 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 树与森林 (Tree & Forest) 赫夫曼树 (Huffman Tree) 二叉树的计数

6树的定义和基本术语 1树的定义 树是由n(n≥0个结点组成的有限集合。 如果n=0,称为空树 如果n>0,则 有一个特定的称之为根(roo的结点,它只有 后继,但没有前驱; 除根以外的其它结点划分为m(m≥0)个互不 相交的有限集合T,T,…,Tm1,每个集合本身又 是一棵树,并且称之为根的子树( subTree每棵 子树的根结点有且仅有一个直接前驱,但可以有 0个或多个后继

6.1 树的定义和基本术语 1. 树的定义 树是由n (n  0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n > 0，则: ▪ 有一个特定的称之为根(root)的结点，它只有 后继，但没有前驱； ▪ 除根以外的其它结点划分为m (m  0)个互不 相交的有限集合T0 , T1 , …, Tm-1，每个集合本身又 是一棵树，并且称之为根的子树(subTree)。每棵 子树的根结点有且仅有一个直接前驱，但可以有 0个或多个后继

root root . Level 1 (a) (b) ① . level 2 depth= 4 E)(F)(G)(H level 3 K M leve l 4 (C) 0结点(mode) 0兄弟( ( Sibling)结点有序树 结点的度( degree)祖先 ancestor)结点无序树 分支( branch)结点子孙 descendant)结点·森林 叶(ea结点 0结点所处层次eve) 孩子chid结点树的深度 depth) 双亲 parent)结点。树的度( degree)

结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 孩子(child)结点 双亲(parent)结点 兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的深度(depth) 树的度(degree) ◼ 有序树 ◼ 无序树 ◼ 森林

2.树的基本术语 1)度(次数、级) (1)结点的度:一个结点所拥有的子数的个数 (2)树的度:树内各结点的度的最大值 2)描述上下及左右的关系 孩子结点:一个结点的子树的根 双亲结点:P120 兄弟结点:同一个双亲的孩子之间互称兄弟 祖先:结点的祖先是从根到该结点所经分支上的 所有结点 子孙:P120结点的后代 3)层次 (1)结点的层次 (2)树的深度(高度)

1）度（次数、级） （1）结点的度：一个结点所拥有的子数的个数 （2）树的度：树内各结点的度的最大值 2）描述上下及左右的关系 孩子结点：一个结点的子树的根 双亲结点： P120 兄弟结点：同一个双亲的孩子之间互称兄弟 祖先：结点的祖先是从根到该结点所经分支上的 所有结点 子孙：P120结点的后代 3）层次 （1）结点的层次 （2）树的深度（高度） 2. 树的基本术语

树的抽象数据类型 树的基本操作:p119 树的建立和遍历—重点

树的基本操作：p119 树的建立和遍历——重点 树的抽象数据类型

62二叉树( Binary Tree) 二叉树的定义 一棵二叉树是结点的一个有限集合,该 集合或者为空,或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点:1)每个结点的度<2:2)是有序树 (a)(b) R (c)(d) (e) 二叉树的五种不同形庵

6.2 二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合，该 集合或者为空，或者是由一个根结点加上两 棵分别称为左子树和右子树的、互不相交的 二叉树组成。 特点：1）每个结点的度≤2；2）是有序树

二叉树的抽教据类型 基本操作:p121~p123 二叉树的建立和遍历

基本操作：p121~p123 二叉树的建立和遍历 二叉树的抽象数据类型

二叉树的性质 性质1若二叉树的层次从1开始,则在二叉树的 第i层最多有2个结点。(i≥1) i证明用数学归纳法 性质2深度为k的二叉树最多有2k-1个结点。 (k≥1) 证明用求等比级数前k项和的公式 性质3对任何一棵二叉树,如果其叶结点个数为 np度为2的非叶结点个数为m2,则有 noEn+1

性质1 若二叉树的层次从1开始, 则在二叉树的 第 i 层最多有 2 i-1个结点。(i  1) [证明用数学归纳法] 性质2 深度为k的二叉树最多有 2 k -1个结点。 (k  1) [证明用求等比级数前k项和的公式] 性质3 对任何一棵二叉树, 如果其叶结点个数为 n0 , 度为2的非叶结点个数为n2 , 则有 n0＝n2＋1 二叉树的性质

证明:考设度为1的结点有n1个,总结点个 数为n,总边数为e,则根据二叉树的定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n1=n0+n1+m2-1 2 0 0-2 +1 同理 三次树:n0=1+n2+2n3 四次树:n0=1+n2+2n3+3n4 K次树:n0=1+n2+2n3+…+(kx-1)nk

证明：若设度为1的结点有n1个，总结点个 数为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 同理： 三次树： n0=1+n2+2n3 四次树： n0=1+n2+2n3+3n4 … K次树： n0=1+n2+2n3+…+(k-1)nk

定义1满二叉树( Full Binary tree) 定义2完全二叉树( Complete binary tree 若设二叉树的深度为h,则共有h层。除第层 外,其它各层(0~h-1)的结点数都达到最大个数 第h层从右向左连续缺若干结点,这就是完全二 叉树。 ((8 (a)满二叉树 b)完全二叉树

定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的深度为h，则共有h层。除第h层 外，其它各层(0h-1)的结点数都达到最大个数， 第h层从右向左连续缺若干结点，这就是完全二 叉树