数据结构 第07章 树和二叉树1.pdfVIP

第7 章 树和二叉树 本章 树的定义，遍历及存储； 知识 二叉树的概念，性质，存储； 要点 二叉树的遍历及基本算法 哈夫曼树与哈夫曼编码 二叉树的性质，存储表示； 本章 二叉树的遍历及算法实现； 重点 树与二叉树的关系； 哈夫曼树及其应用。 二叉树遍历的非递归算法； 本章 二叉树的基本操作； 难点 线索二叉树。 7.1 树的逻辑结构 7.1.1 树的定义及基本术语 1.树的定义 离散数学中，树：连通但没有回路的图。 在树中，常将数据元素称为结点（node）。 树(tree)是n （n≥0）个结点的有限集合。当n＝0时， 称为空树；任意一棵非空树满足以下条件： ⑴当n=1时，有且仅有一个特定的称为根的结点； ⑵ 当n＞1时，除根结点之外的其余结点被分成m （ m0）个互不相交的有限集合T ,T ,… ,T ，其中每个集合 1 2 m 又是一棵树，并称为这个根结点的子树。 显然，树的定义是递归的。 7.1 树的逻辑结构 7.1.1 树的定义及基本术语 以下是一些具体树的示例： A A B C D E J G H I 7.1 树的逻辑结构 7.1.1 树的定义及基本术语 树的应用实例： My Computer C: D: E: …… …… …… WINDOWS Program Files Music Picture …… …… …… …… …… 组织结构，菜单结构…… 7.1 树的逻辑结构 7.1.1 树的定义及基本术语 注意树的以下特点 1）定义方法是递归的（操作方法也常用递归）。 2 ）树中的数据元素称为结点（node）。 3 ）多个有关系的结点称为集合（子树）。 4 ）非空树有唯一的根结点。 5）子树间互不相交（无公共结点，无关系）。 7.1 树的逻辑结构 7.1.1 树的定义及基本术语 2.树的基本术语 1）结点的度：结点拥有子树的个数。 树的度：树中各结点度的最大值。 A B C D E F G