第五章树 东南大学计算机学院方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件
东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 第五章 树
本章主要内容 树的基本概念 二叉树 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 目录表示 集合表示 凹入表表示