福州大学：《数据结构》课程教学资源（PPT课件讲稿）第六章 树与森林

第六章树与森林 树和森林的概念 二叉树 二叉树遍历 二叉树的计数 堆 树与森林 n霍夫曼树

◼ 树和森林的概念 ◼ 二叉树 ◼ 二叉树遍历 ◼ 二叉树的计数 ◼ 堆 ◼ 树与森林 ◼ 霍夫曼树

树和森林的概念 树的定义 树是由n(n≥0)个结点组成的有限集合。 如果n=0,称为空树;如果n>0,则 有一个特定的称之为根(root)的结点, 它只有直接后继,但没有直接前驱 除根以外的其它结点划分为m(m≥0) 个互不相交的有限集合T。飞根的子树。 91m1 每 个集合又是一棵树,并且称之

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

树的特点 每棵子树的根结点有且仅有一个直接前 驱,但可以有0个或多个直接后继。 A 0层 B D -1层 height BOO①“2层 K(L 3层

树的特点 ◼ 每棵子树的根结点有且仅有一个直接前 驱，但可以有0个或多个直接后继。 0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J

结点子女祖先来树的度 结点的度米双亲癥子孙树高度 ※分支结点*兄弟*结点层次*森林 ※叶结点 A 0层 B D -1层 height O-2层3 K(L 3层

0层 1层 3层 2层 height = 3 A C G B D E F K L H M I J  结点  结点的度  分支结点  叶结点  子女  双亲  兄弟  祖先  子孙  结点层次  树的度  树高度  森林

二叉树( Binary Tree 二叉树的定义 一棵二叉树是结点的一个有限集合, 该集合或者为空,或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 R LR 二叉树的五种不同形恋

二叉树 (Binary Tree) 二叉树的定义 二叉树的五种不同形态 一棵二叉树是结点的一个有限集合， 该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不 相交的二叉树组成。 L R L R

二叉树的性质 性质1若二叉树的层次从0开始,则在二叉 树的第i层最多有2个结点。(≥0) i证明用数学归纳法] 性质2高度为h的二叉树最多有2+1-1个 结点。(≥-1) i证明用求等比级数前项和的公式] 20+21+22+….+2h=2h+1-1

性质1 若二叉树的层次从0开始, 则在二叉 树的第 i 层最多有 2 i 个结点。(i  0) [证明用数学归纳法] 性质2 高度为 h 的二叉树最多有 2 h+1-1个 结点。(h  -1) [证明用求等比级数前k项和的公式] 2 0 + 21 + 22 + … + 2h = 2h+1-1 二叉树的性质

性质3对任何一棵二叉树,如果其叶结点 有n0个,度为2的非叶结点有m2个,则有 =n2+1 证明:若设度为1的结点有n1个,总结点 个数为n,总边数为e,则根据二叉树的 定义, n=n0+n1+n2e=2n2+n1=n-1 因此,有2n2+n1=+m1+n2-1 0 n=n+1 0

性质3 对任何一棵二叉树, 如果其叶结点 有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0＝n2＋1 证明：若设度为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

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

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

性质4具有n(≥0)个结点的完全二叉树 的高度为「og2(n+1)1-1 证明:设完全二叉树的高度为h,则有 2h-1<n≤2h+1-1 上面h层结点数包括第h层的最大结点数 变形2h<n+1≤2h+1 取对数h<log2n+1)sh+1 因此有「og2(n+1)1=h+1 h=「log2n+1)1-1

性质4 具有 n (n  0) 个结点的完全二叉树 的高度为 log2 (n+1) -1 证明：设完全二叉树的高度为h，则有 2 h - 1 < n  2 h+1 - 1 变形 2 h < n+1  2 h+1 取对数 h < log2 (n+1)  h+1 因此有 log2 (n+1) = h+1 h = log2 (n+1) -1 上面h层结点数 包括第h层的最大结点数

性质5如将一棵有n个结点的完全二叉树自 顶向下,同一层自左向右连续给结点编号0, 1,2,…,n-1,则有以下关系: 若i=0,则i无双亲 若i>0,则i的双亲为(-1)2」 若2*计1<n,则i的左子女为2计1,若 2*计+2<n,则i的右子女为2*计2 若i为偶数,且=0, 则其左兄弟为i-1,若 i为奇数,且i!=n-1, 则其右兄弟为计1680

性质5 如将一棵有n个结点的完全二叉树自 顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系： ◼ 若i = 0, 则 i 无双亲 若i > 0, 则 i 的双亲为(i -1)/2 ◼ 若2*i+1 < n, 则 i 的左子女为 2*i+1，若 2*i+2 < n, 则 i 的右子女为2*i+2 ◼ 若 i 为偶数, 且i != 0, 则其左兄弟为i-1, 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 0 1 2 3 7 4 5 6 8 9