第五章树 东南大学计算机学院方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件
东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 第五章 树
本章主要内容 树的基本概念 二叉树 n二叉树的存储表示 二叉树的遍历及其应用 二叉树遍历的非递归算法 二叉树的计数 n树与二叉树的转换 堆 Huffman树及其应用
本章主要内容 ◼ 树的基本概念 ◼ 二叉树 ◼ 二叉树的存储表示 ◼ 二叉树的遍历及其应用 ◼ 二叉树遍历的非递归算法 ◼ 二叉树的计数 ◼ 树与二叉树的转换 ◼ 堆 ◼ Huffman树及其应用 2
树的基本概念 a树是由n(n>0)个结点组成的有限集合: 口有一个特定的称之为根(rot的结点; a除根以外的其它结点划分为m(m≥0)个互不相交 的有限集合T1T2,…,Tm,其中每个集合也是一棵 树,并被称为根的子树。 这个定义是递归的
树的基本概念 ◼ 树是由n (n>0) 个结点组成的有限集合： 有一个特定的称之为根 (root) 的结点； 除根以外的其它结点划分为 m (m≥0) 个互不相交 的有限集合T1 , T2 , …, Tm，其中每个集合也是一棵 树，并被称为根的子树。 ◼ 这个定义是递归的 3
树的基本概念 根 1层 深度=2 B 2层深度=4 高度=4 高度=3①⑥ 3层 4层 结点 子女结点 结点所处层次 有序树 结点的度 父结点 树的深度 无序树 叶结点 兄弟结点 树的高度 森林 分支结点 祖先结点 树的度 子孙结点
树的基本概念 4 结点 结点的度 叶结点 分支结点 1层 2层 4层 3层 深度 = 4 高度 = 4 A C G B D E F K L H M I J 根 子女结点 父结点 兄弟结点 祖先结点 子孙结点 结点所处层次 树的深度 树的高度 树的度 有序树 无序树 森林 高度 = 3 深度 = 2
树的基本概念 n树的其他表示方法 B E A匚 K E K影影影影 C(G F G K d② D H(M H A D M影影 J 集合表示 凹入表表示 目录表示
树的基本概念 ◼ 树的其他表示方法 5 A B C D E F G H I J K L M A B C D E F G H I J K L M A B C D E F G H I J K L M 目录表示 集合表示 凹入表表示
二叉树 n二叉树是结点的有限集合: 该集合或者为空; 或者由一个根结点加上两棵分别称为左子树和右子 树的、互不相交的二叉树组成 这个定义也是递归的 R R 空 只有根右子树为空右子树为空 左右子树不为空
二叉树 ◼ 二叉树是结点的有限集合： 该集合或者为空； 或者由一个根结点加上两棵分别称为左子树和右子 树的、互不相交的二叉树组成。 ◼ 这个定义也是递归的 6 Ф L R L R 空 只有根 右子树为空 右子树为空 左右子树不为空
二叉树 性质1 口若二叉树的层次从1开始,则在二叉树的第i(论1) 层最多有21个结点。 口证明:(用数学归纳法) i=1时,根结点只有1个,21=20=1; >若设i=k时性质成立,即该层最多有2k1个结点, 则当i=k+1时,由于第k层每个结点最多可有2个 子女,第k+1层最多结点个数可有2k1=2k个,故 性质成立
二叉树 ◼ 性质1 若二叉树的层次从1 开始, 则在二叉树的第i ( i≥1) 层最多有 2 i-1 个结点。 证明：(用数学归纳法) ➢ i = 1时，根结点只有1个，2 1-1 = 20 =1； ➢ 若设 i = k 时性质成立，即该层最多有2 k-1 个结点， 则当 i = k+1 时，由于第k 层每个结点最多可有2 个 子女，第 k+1 层最多结点个数可有2*2k-1 = 2k 个，故 性质成立。 7
二叉树 n性质2 口高度为h(h21)的二叉树最多有2-1个结点。 口证明:(用求等比级数前k项和的公式) 高度为h的二叉树有h层,各层最多结点个数相加, 得到等比级数,求和得: 20+21+22++2h-1=2h-1 a空树的高度为0,只有根结点的树的高度为1
二叉树 ◼ 性质2 高度为 h (h≥1) 的二叉树最多有 2 h -1个结点。 证明：(用求等比级数前k项和的公式) ➢ 高度为 h 的二叉树有 h 层，各层最多结点个数相加， 得到等比级数，求和得： ➢ 2 0 + 21 + 22 + … + 2h-1 = 2h-1 空树的高度为 0，只有根结点的树的高度为 1。 8
二叉树 性质3 口对任何一棵非空二叉树,如果其叶结点有n个,度 为2的非叶结点有n2个,则有n=n2+1 证明: 若设度为1的结点有n1个,总结点个数为n,总边 数为e,则根据二叉树的定义, n=n0+n+n2,且e=2n2+n1=n-1 因此,有2n2+n1=n0+n1+n21 0 +1
二叉树 ◼ 性质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 9
二叉树 n满二叉树 深度为k的满二叉树是有2k1个结点的二叉树 特点:每一层结点数都达到了最大数 完全二叉树 深度为k的完全二叉树中每一个结点的编号都与 深度为k的满二叉树中编号一一对应 特点:从第1层到第k-1层是满的,仅最下面第k层 或是满的,或是从右到左缺若千结点 10
二叉树 ◼ 满二叉树 深度为k的满二叉树是有2 k -1个结点的二叉树 特点：每一层结点数都达到了最大数 ◼ 完全二叉树 深度为 k 的完全二叉树中每一个结点的编号都与 深度为k的满二叉树中编号一一对应 特点：从第1层到第k-1层是满的，仅最下面第k层 或是满的，或是从右到左缺若干结点 10