第6章树与二叉树 6.1树的概念和运算 6,2二叉树 6.3和林 6.4树的典型应用 65本章小结
第6章 树与二叉树 6.1 树的概念和运算 6.2 二叉树 6.3 树和森林 6.4 树的典型应用 6.5 本章小结
6.1树的概念和运算 树形结构是线性结构的拓广。 除了首元(唯一存在,在树形结构中称 为“根”节点)没有前驱元素以外,树中其 他所有元素(节点)都有且只有一个直接前 驱元素(父节点);直接后继元素则没有限 制:没有直接后继元素的节点(叶节点)可 以有多个;存在直接后继元素的节点,其直 接后继元素的个数也可以有多个
6.1 树的概念和运算 树形结构是线性结构的拓广。 除了首元（唯一存在，在树形结构中称 为“根”节点）没有前驱元素以外，树中其 他所有元素（节点）都有且只有一个直接前 驱元素（父节点）；直接后继元素则没有限 制：没有直接后继元素的节点（叶节点）可 以有多个；存在直接后继元素的节点，其直 接后继元素的个数也可以有多个
61.1树的定义与表示 树的定义: 树的逻辑结构可以这样描述: 树是包含N(N>0)个节点的有穷集合D 且在D上定义了一个关系R,关系R满足以 下条件:
6.1.1 树的定义与表示 • 树的定义： 树的逻辑结构可以这样描述： 树是包含N(N>0)个节点的有穷集合D， 且在D上定义了一个关系R，关系R满足以 下条件：
(1)有且仅有一个节点e∈D,它对于关系 R来说没有前驱,节点e称作树的根。 (2)除节点e外,D中的每个节点对于关系 R来说都有且仅有一个前驱。 (3)除节点e0外的任何节点eS,都存在 个节点序列(eo2e1,en),其中e就是树根 且en=e,有序对<e1,e>∈R(l≤i≤m)。这 样的节点序列称为从根到节点e的一条路径
(1) 有且仅有一个节点e0D，它对于关系 R来说没有前驱，节点e0称作树的根。 (2) 除节点e0外，D中的每个节点对于关系 R来说都有且仅有一个前驱。 (3) 除节点e0外的任何节点eS，都存在一 个节点序列(e0 ,e1 ,…,em )，其中e0就是树根， 且em=e，有序对<ei-1 ,ei>R（1≤i≤m）。这 样的节点序列称为从根到节点e的一条路径
递归是树的固有属性 树的递归定义: 树是由一个或多个节点组成的有限集T, 它满足下面两个条件: (1)有一个特定的节点称之为根; (2)其余的节点分成m(m≥0)个互不相 交的有限集里1,里2,…,里n,其中每个集 合本身又是一棵树,称里1,里2,…,T为 根的子树
树的递归定义： 树是由一个或多个节点组成的有限集T， 它满足下面两个条件： (1)有一个特定的节点称之为根; (2)其余的节点分成m(m≥0)个互不相 交的有限集T1，T2，…，Tm，其中每个集 合本身又是一棵树，称T1，T2，…，Tm为 根的子树。 递归是树的固有属性