第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 树形表示法