第六章 Part1(树的基本概念与二叉树遍历).pdf

本讲重点难点 第六章 二叉树和树 树是一类重要的非线性数据结构，是以分支关系定义的层 基本内容 次结构 典型例子： 二叉树的定义性质存储结构 企业的管理机构 二叉树遍历和线索化 计算机文件系统 树和森林、存储结构、树的多种应用 重点难点 二叉树结构特性及证明方法 二叉树各种存储结构的特点及适用 二叉树遍历 建立huffman树 基于二叉链表表示的二叉树的算法 8-Nov-07 1 8-Nov-07 2 第一节 树的定义 树的示例 树(Tree)的定义 树是由n (n ≥ 0)个节点组成的有限集合。 根 T T 如果n = 0，称为空树； A 1 A 3 如果n 0，则:有且仅有一个特定的称之为根(root)的 节点，它只有直接后继，但没有直接前驱； B C D 如果n1，则：除根以外的其它节点可以划分为m 只有根节点的树 (m0)个互不相交的有限集合T , T , …, T ，每个集 0 1 m-1 合又是一棵树，并且称为根的子树(subTree)。每棵子 E F G H I J 树的根节点有且仅有一个直接前驱，但可以有0个或多个 直接后继。 特点： K L M