1、第六章 树和二叉树6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和搜索二叉树6.4 树和森林6.6 赫夫曼树及其应用6.1 树的定义和基本术语o 树的定义树的定义 树是由树是由 n (n 0) 个结点组成的有限集合个结点组成的有限集合 .如果如果n=0,称为空树称为空树 ;如果如果 n0， 则称为非空树。在一棵非空树则称为非空树。在一棵非空树中：中： 有且仅有一个称为有且仅有一个称为 根根 (Root)的结点，它只有直接的结点，它只有直接后继，但没有直接前驱；后继，但没有直接前驱； 当当 n1时，时， 除根以外的其它结点可划分为除根以外的其它结点可划分为 m (m 0) 个互不相交
2、的有限集合个互不相交的有限集合 T1, T2, , Tm， 每个集合每个集合本身又是一棵树本身又是一棵树 ， 并且称之为根的并且称之为根的 子树子树 (Sub Tree)。n 每棵子树的根结点有且仅有一个直接前驱，但每棵子树的根结点有且仅有一个直接前驱，但可以有可以有 0个或多个直接后继。个或多个直接后继。1层2层4层3层height= 4ACGB DE FK LHMI JA只有根结点的树只有根结点的树T1=B,E,F,K,LT2T3T1T11=E,K,L T12=F树的抽象数据类型定义：ADT Tree数据对象 D： 数据关系 R：基本操作： ADT Tree若 D为空集，则称为空树；否则
3、: (1)在 D中存在唯一的称为根的数据元素root,(2)当 n1时，其余结点可分为 m(m0)个互不相交的有限集 T1,T2, ,Tm, 其中每一个子集本身又是一棵符合本定义的树 ,称为根 root的子树。D是具有相同特性的数据元素的集合。基本术语o 结点 : 数据元素 + 若干指向子树的分支o 结点的度 : 分支的个数o 树的度 : 树中所有结点的度的最大值o 叶子结点 : 度为零的结点o 分支结点 : 度大于零的结点o 从根到结点的路径 :由从根到该结点所经分支和结点构成。o 孩子结点o 双亲结点o 兄弟结点o 祖先o 子孙ACBD EACGB DE FK LHMI J1层2层4层3层
4、ACGB DE FK LHMI Jo 结点的层次 : 假设根结点的层次为 1,第 L层的结点的子树根结点的层次为 L+1o 堂兄弟 ：双亲在同一层的结点互为堂兄弟。o 树的深度 ：树中叶子结点所在的最大层次数。o 有序树 ：树中结点的子树从左到右是有次序的。o 无序树：o 森林 ：是 m（ m0 ） 棵互不相交的树的集合o 任何一棵非空树是一个二元组Tree = （ root， F）其中： root被称为根结点， F被称为子树森林ACGB DE FK LHMI JCGB DE FK LHMI J基本操作o 查找 o 插入 o 删除 查找（ 8）Root(T); Value(T, cur_e); Parent(T, cur_e);LeftChild(T, cur_e); RightSibling(T, cur_e);TreeEmpty(T); TreeDepth(T);TraverseTree(T, Visit();特定查找按关系查找按树的特性查找插入（ 4）InitTree( CreateTree(Assign(T, cur_e, value); InsertChild(在 P结点下面插入一棵以 c为根的子树，作为 P结点的第 i 棵子树赋值
