答是要 6.1树的定义及基本术语 6.2二叉树 6.3编历二叉树 64线索二叉树 6.5二叉排序字树 6.6平衡二又树 6.7树和森林 68哈夫曼树及应用
1 内容提要 6.1 树的定义及基本术语 6.2 二叉树 6.3 编历二叉树 6.4 线索二叉树 6.5 二叉排序树 6.6 平衡二叉树 6.7 树和森林 6.8 哈夫曼树及应用
61的定义基水水 1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合,在这个集合上定义了 个唯一的关系,这个关系满足下面的条件 .存在唯一的一个结点,它没有前驱,称为根 ∥.除了根结点外,其它结点有且仅有一个前驱 M.除了根结点外,在何结点a(0≤1m),都存在唯 的一个从根到的结点序列0,a1,a2,an,其中, a入a0是根。这个序列称为从根到白的路径 a2 日
2 6.1 树的定义及基本术语 1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合，在这个集合上定义了 一个唯一的关系，这个关系满足下面的条件： I. 存在唯一的一个结点，它没有前驱，称为根 II. 除了根结点外，其它结点有且仅有一个前驱 III. 除了根结点外，任何结点ai (0 im)，都存在唯一 的一个从根到ai的结点序列a0 , a1 , a2 ,.., am ，其中， a0 a0是根。这个序列称为从根到ai的路径。 a1 a2 a3 a4 a5
的定业差水米con (2)树的递归定义 树是包含m个结点的有限集,在这个集合上定义了 唯一的关系,它满足下面的条件: .有个待定的称为根的结点; ∥.-mn>1的,除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集71,72,,Tm,其中 ,每个有限集都是一棵树。这些树称为根的子树 Tl={b,e,f};T2={c};T3={d}
3 树的定义及基本术语(cont’d) (2)树的递归定义 树是包含n个结点的有限集，在这个集合上定义了 唯一的关系，它满足下面的条件： I. 有个特定的称为根的结点； II. 当n>1时，除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集T1,T2,..,Tm，其中 ，每个有限集都是一棵树。这些树称为根的子树。 a b c d e f T1={b,e,f};T2={c};T3={d}
(3)树的基本术语 1.根,唯一没有前驱的结点 2.度,结点的度是结点的子树数,树的度是指结点 度的最大值 3.叶子,度为0的结点,也称终端结点 4.分枝结点,叶子之外的结点,也称非终端结点。 除了根以外的分枝结点又称内部结点 5.双亲、子女、祖先、子孙,结点子树的根称为结 点的子女,该结点就是它子女的双来;某结点的 祖先是指从根到该结点的路径上的全部结点;结 点的子树中全部结点都是该结点的子孙 d
4 树的定义及基本术语(cont’d) (3)树的基本术语 1. 根,唯一没有前驱的结点 2. 度,结点的度是结点的子树数目,树的度是指结点 度的最大值 3. 叶子，度为0的结点，也称终端结点 4. 分枝结点，叶子之外的结点，也称非终端结点。 除了根以外的分枝结点又称内部结点。 5. 双亲、子女、祖先、子孙，结点子树的根称为结 点的子女，该结点就是它子女的双亲；某结点的 祖先是指从根到该结点的路径上的全部结点；结 点的子树中全部结点都是该结点的子孙。 a b c d e f
的定差水语cm (3)树的基本术语 6.兄弟、堂兄弟,同一个结点的子女互为兄弟,双 亲为兄弟的结点互称堂兄弟 7.结点的层次、树的深高度,根为第1层,结点 的层次是其双来层次加1。树的深度是指结点的最 大层数 8.有序树、无序树,如果结点的各子树自左向右是 有次序的,则称有序树,否则称无序树 9.森林,m棵互不相交的树就构成了森林 a 第1层 d 第2层 c 3层 e f g
5 树的定义及基本术语(cont’d) (3)树的基本术语 6. 兄弟、堂兄弟，同一个结点的子女互为兄弟，双 亲为兄弟的结点互称堂兄弟。 7. 结点的层次、树的深度(高度)，根为第1层，结点 的层次是其双亲层次加1。树的深度是指结点的最 大层数。 8. 有序树、无序树，如果结点的各子树自左向右是 有次序的，则称有序树，否则称无序树 9. 森林，m棵互不相交的树就构成了森林。 a b c d e f g 第1层 第2层 第3层