第6章二叉树和树 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第6章树和二叉树 胡建华 2021/2/19 计算机教研室 第 1 页 第 6 章 二叉树和树
树型结构是一类重要的非线性结构。树型结 构是结点之间有分支,并且具有层次关系的结构, 它非常类似于自然界中的树。树结构在客观世界 中是大量存在的。例如家谱、行政组织机构都可 用树形象地表示。 树结构在计算机领域中也有着广泛的应用, 例如在编译程序中,用树结构来表示源程序的语 8法结构;在数据库系统中,可用树结构来组织信 意息;在分析算法的行为时,可用树结构来描述其 执行过程等等。 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第2页 树型结构是一类重要的非线性结构。树型结 构是结点之间有分支，并且具有层次关系的结构， 它非常类似于自然界中的树。树结构在客观世界 中是大量存在的。例如家谱、行政组织机构都可 用树形象地表示。 树结构在计算机领域中也有着广泛的应用， 例如在编译程序中，用树结构来表示源程序的语 法结构；在数据库系统中，可用树结构来组织信 息；在分析算法的行为时，可用树结构来描述其 执行过程等等
6.1二叉树 二叉树在树结构的应用中起着非常重要的作 用,因为对二叉树的许多操作算法简单,而任何 树都可以与二叉树相互转换,这样就解决了树的 存储结构及其运算中存在的复杂性。 计算机教研宦 第3页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第3页 6.1 二叉树 二叉树在树结构的应用中起着非常重要的作 用，因为对二叉树的许多操作算法简单，而任何 树都可以与二叉树相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性
6.1.1二叉树的定义 ·二叉树( Binary Tree)是由n(n≥0)个结点的 有限集合构成,此集合或者为空集,或者由 个根结点及两棵互不相交的左右子树组成,并 且左右子树都是二叉树 ·这是一个递归定义。二叉树可以是空集合,根 章和吕风街 可以有空的左子树或空的右子树 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第4页 6.1.1 二叉树的定义 • 二叉树（Binary Tree）是由n(n≥0)个结点的 有限集合构成，此集合或者为空集，或者由一 个根结点及两棵互不相交的左右子树组成，并 且左右子树都是二叉树。 • 这是一个递归定义。二叉树可以是空集合，根 可以有空的左子树或空的右子树
@基本术语 结点(node)表示树中的元素, 包括数据项及若干指向其子树的 分支 结点的度( degree)结点拥有的 子树数 叶子ean)度为0的结点 ·的子子的为①画间画 双亲( parents)孩子结点的上层 结点叫该结点的~ 意·兄弟bing)同一双亲的孩子 ,树的度一棵树中最大的结点度数 结点的层次(evel)—从根结点算起,根为第一层,它的孩子为第二 层 深度( depth)树中结点的最大层次数 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第5页 基本术语 • 结点(node)——表示树中的元素， 包括数据项及若干指向其子树的 分支 • 结点的度(degree)——结点拥有的 子树数 • 叶子(leaf)——度为0的结点 • 孩子(child)——结点子树的根称为 该结点的孩子 • 双亲(parents)——孩子结点的上层 结点叫该结点的~ 1 2 3 11 4 5 8 9 12 6 7 10 •兄弟(sibling)——同一双亲的孩子 •树的度——一棵树中最大的结点度数 •结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二 层…… •深度(depth)——树中结点的最大层次数