第7章树形结构 7.1树的基本概念 7.2二叉树概念和性质 7.3二叉树存储结构 7.4二叉树的遍历 7.5二叉树的基本运算及其实现 7.6二叉树的构造 7.7线索二叉树 7.8哈夫曼树 本章小结
第7章 树形结构 7.1 树的基本概念 7.2 二叉树概念和性质 7.3 二叉树存储结构 7.4 二叉树的遍历 7.5 二叉树的基本运算及其实现 7.6 二叉树的构造 7.8 哈夫曼树 本章小结 7.7 线索二叉树
7.1树的基本概念 7.1.1树的定义 7.1.2树的表示 7.1.3树的基本术语 7.1.4树的性质 7.1.5树的基本运算 7.1.6树的存储结构
7.1 树的基本概念 7.1.1 树的定义 7.1.3 树的基本术语 7.1.2 树的表示 7.1.4 树的性质 7.1.5 树的基本运算 7.1.6 树的存储结构
7.1.1树的定义 形式化定义: 树:T={K,R}。K是包含n个结点的有穷集合 (m>0)关系R满足以下条件: (1)有且仅有一个结点k0∈K,它对于关系R来 说没有前驱结点结点k称作树的根。 (2)除结点M外,K中的每个结点对于关系R来 说都有且仅有一个前驱结点。 (3)K中每个结点对于关系R来说可以有多个 后继结点
7.1.1 树的定义 形式化定义： 树：T＝{K,R}。K是包含n个结点的有穷集合 (n>0),关系R满足以下条件: （1）有且仅有一个结点k0∈K,它对于关系R来 说没有前驱结点,结点k0称作树的根。 （2）除结点k0外,K中的每个结点对于关系R来 说都有且仅有一个前驱结点。 （3）K中每个结点对于关系R来说可以有多个 后继结点
递归定义: 树是由n(n>0)个结点组成的有限集合(记为 T)。其中 如果n=0,它是一棵空树,这是树的特例; 如果m>0,这n个结点中存在(有仅存在)一个结 点作为树的根结点,简称为根(root),其余结点可 分为m(m>0)个互不相交的有限集T,,T2,… m 其中每一棵子集本身又是一棵符合本定义的树 称为根rot的子树
递归定义： 树是由n（n≥0）个结点组成的有限集合（记为 T）。其中， 如果n=0，它是一棵空树，这是树的特例； 如果n>0，这n个结点中存在（有仅存在）一个结 点作为树的根结点，简称为根（root），其余结点可 分为m （m>0）个互不相交的有限集T1 ,，T2，…， Tm，其中每一棵子集本身又是一棵符合本定义的树， 称为根root的子树
7.1.2树的表示 (1)树形表示法。这是树的最基本的表示,使用 棵倒置的树表示树结构非常直观和形象。下图就是 采用这种表示法。 E 树形表示法
7.1.2 树的表示 （1）树形表示法。这是树的最基本的表示,使用一 棵倒置的树表示树结构,非常直观和形象。下图就是 采用这种表示法。 A C G J B E D F H I K L M 树形表示法
(2)文氏图表示法。使用集合以及集 合的包含关系描述树结构。下图就是树的文 氏图表示法。 A C B ECF 文氏图表示法
（2）文氏图表示法。使用集合以及集 合的包含关系描述树结构。下图就是树的文 氏图表示法。 H L D I K M C G J E B F 文氏图表示法 A
(3)凹入表示法。使用线段的伸缩描述树 结构。下图是树的凹入表示法。 1令 F 凹入表示法
（3）凹入表示法。使用线段的伸缩描述树 结构。下图是树的凹入表示法
(4)括号表示法。将树的根结点写在括号的 左边,除根结点之外的其余结点写在括号中并用逗 号间隔来描述树结构。下图是树的括号表示法。 A(B(E, F,C(G),D(H,I(K,L,M) 括号表示法
（4）括号表示法。将树的根结点写在括号的 左边,除根结点之外的其余结点写在括号中并用逗 号间隔来描述树结构。下图是树的括号表示法
17.1.3树的基本术语 1.结点的度与树的度:树中某个结点的子树的个 数称为该结点的度。树中各结点的度的最大值称为 树的度,通常将度为m的树称为m次树或m叉树。 2.分支结点与叶结点:度不为零的结点称为非 终端结点,又叫分支结点。度为零的结点称为终端 结点或叶结点。在分支结点中,每个结点的分支数 就是该结点的度。如对于度为1的结点,其分支数为 1,被称为单分支结点;对于度为2的结点,其分支 数为2,被称为双分支结点,其余类推
7.1.3 树的基本术语 1. 结点的度与树的度：树中某个结点的子树的个 数称为该结点的度。树中各结点的度的最大值称为 树的度，通常将度为m的树称为m次树或m叉树。 2. 分支结点与叶结点：度不为零的结点称为非 终端结点，又叫分支结点。度为零的结点称为终端 结点或叶结点。在分支结点中，每个结点的分支数 就是该结点的度。如对于度为1的结点，其分支数为 1，被称为单分支结点；对于度为2的结点，其分支 数为2，被称为双分支结点，其余类推
3.路径与路径长度:对于任意两个结点k和k 若树中存在一个结点序列k,k1,k2,…,km,k 使得序列中除k外的任一结点都是其在序列中的前 个结点的后继,则称该结点序列为由k到k的一条路 径,用路径所通过的结点序列(kk1,k12…,)表示这 条路径。路径的长度等于路径所通过的结点数目减1 (即路径上分支数目)。可见,路径就是从k出发 自上而下”到达k所通过的树中结点序列。显然, 从树的根结点到树中其余结点均存在一条路径
3. 路径与路径长度：对于任意两个结点ki和kj， 若树中存在一个结点序列ki，ki1，ki2，…，kin，kj， 使得序列中除ki外的任一结点都是其在序列中的前一 个结点的后继，则称该结点序列为由ki到kj的一条路 径，用路径所通过的结点序列(ki ,ki1 ,ki2 ,…,kj )表示这 条路径。路径的长度等于路径所通过的结点数目减1 （即路径上分支数目）。可见，路径就是从ki出发 “自上而下”到达kj所通过的树中结点序列。显然， 从树的根结点到树中其余结点均存在一条路径