第六章树和二叉树 6.1树的定义和基本概念 62二叉树 6.3遍历二叉树 ●64树和森林 65赫夫曼树及其应用 北京邮电大学自动化学院
北京邮电大学自动化学院 1 第六章 树和二叉树 ⚫ 6.1 树的定义和基本概念 ⚫ 6.2 二叉树 ⚫ 6.3 遍历二叉树 ⚫ 6.4 树和森林 ⚫ 6.5 赫夫曼树及其应用
61树的定义和基本术语 树型结构是一类重要的非线性结构。树结构在客观世界里是大 量存在的,树在计算机领域中也有着广泛的应用,例如在编译 程序中,用树来表示源程序的语法结构;在数据库系统中,可 用树来组织信息;在分析算法的行为时,可用树来描述其执行 过程等等。 1、定义树是n(m>=0)个结点的有限集T,T为空时称为空 树,否则它满足如下两个条件 ●(1)有且仅有一个特定的称为根的结点; ·(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集 T1,T2T3Tm,其中每个子集又是一棵树,并称其为根的子 树。 北京邮电大学自动化学院
北京邮电大学自动化学院 2 ⚫ 树型结构是一类重要的非线性结构。树结构在客观世界里是大 量存在的，树在计算机领域中也有着广泛的应用，例如在编译 程序中，用树来表示源程序的语法结构；在数据库系统中，可 用树来组织信息；在分析算法的行为时，可用树来描述其执行 过程等等。 6.1 树的定义和基本术语 ⚫ 1、定义 树是n(n>=0)个结点的有限集T，T为空时称为空 树，否则它满足如下两个条件： ⚫ （1）有且仅有一个特定的称为根的结点； ⚫ （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子 树
1、定义 只有根结点的树 A 有子树的树A根 B)IIC D E F从G(H K 子树 北京邮电大学自动化学院
北京邮电大学自动化学院 3 A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树 1、定义
2、基本术语 结点一表示树中的元素,包括数据项及若干指向其子树的分支 结点的度( degree)一结点拥有的子树数 叶子(eaf—一度为0的结点 孩子chid)—结点子树的根称为该结点的孩子 双亲( parents)——孩子结点的上层结点叫该结点的 兄弟( sibling——同一双亲的孩子 ●树的度—一棵树中最大的结点度数 结点的层次(eve)——从根结点算起,根为第一层,它的孩子 为第二层 ·深度( depth)—树中结点的最大层次数 森林( forest)-—m(m≥0)棵互不相交的树的集合 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 结点——表示树中的元素，包括数据项及若干指向其子树的分支 2、基本术语 ⚫ 结点的度(degree)——结点拥有的子树数 ⚫ 叶子(leaf)——度为0的结点 ⚫ 孩子(child)——结点子树的根称为该结点的孩子 ⚫ 双亲(parents)——孩子结点的上层结点叫该结点的~ ⚫ 兄弟(sibling)——同一双亲的孩子 ⚫ 树的度——一棵树中最大的结点度数 ⚫ 结点的层次(level)——从根结点算起，根为第一层，它的孩子 为第二层…… ⚫ 深度(depth)——树中结点的最大层次数 ⚫ 森林(forest)——m(m0)棵互不相交的树的集合
2、基本术语 结点A的度:3 叶子:K,L,F,G,M,l,J 结点B的度:2 结点M的度:0 A 树的深度:4 树的度:3 结点A的层次 D 结点M的层次: 结点双亲:D E F(G(H 结点L的双亲:E K 结点F,G为堂兄弟 结点A是结点F,G的祖先 结点A的孩子:B,C,D 结点B,C,D为兄弟 结点B的孩子:E,F 结点K,L为兄弟 北京邮电大学自动化学院
北京邮电大学自动化学院 5 A B C D E F G H I J K L M 结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 结点A的层次：1 结点M的层次：4 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先 2、基本术语