第六章树与二叉树 2007.9
2007.9 第六章 树与二叉树
61树的定义和基本概念 62二叉树 62.1二叉树的定义和基本术语 622二叉树的性质 62.3二叉树的存储结构 6.3遍历二叉树 6.31遍历二叉树 6.32线索二叉树 64树和森林 64.1树的存储结构 64.2森林与二叉树的转换 64.3树和森林的遍历 6.5哈夫曼树及哈夫曼编码
6.1 树的定义和基本概念 6.2 二叉树 6.2.1 二叉树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历 6.5 哈夫曼树及哈夫曼编码
61树的定义和基本概念
6.1 树的定义和基本概念
树的定义 树(Tree是nn>=0)个结点的有限集T,T为空时称为空树, 否则它满足如下两个条件: (1)有且仅有一个特定的称为根(ROO的结点; 2)其余的结点可分为mm>=0个互不相交的子集 2,T3…Tm,其中每个子集又是一棵树,并称其为子树 Subtree)。 AICG D E( H K M
树的定义 树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树， 否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2) 其余的结点可分为m(m>=0)个互不相交的子集 T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树 (Subtree)。 I J A B C D E F G H K L M
树的基本概念 结点(node) 根结点(root)、叶子/叶结点(eaf) 孩子结点( child)、双亲结点( parent) 兄弟( brother) 度( degree 结点的度 树的度:max(结点的度) 树的深度/高度( depth):max(结点的层次) 有序树/无序树 ●森林( forest)
树的基本概念 结点（node） 根结点（root）、叶子/叶结点（leaf） 孩子结点（child）、双亲结点（parent）、 兄弟（brother） 度（degree） 结点的度 树的度：max(结点的度) 树的深度/高度（depth）：max（结点的层次） 有序树/无序树 森林（forest）