武汉理工大学：《软件技术基础》课程教学资源（PPT课件）第3章 基本数据结构及运算（3/4）

3.5树与二叉树 351树的基本概念 352树的存储 353二叉树的基本概念 354二叉树的存储 3.55二叉树的遍历 35.6树与森林的二叉树表示 3.57二叉树的应用

◼ 3.5.1 树的基本概念 ◼ 3.5.2 树的存储 ◼ 3.5.3 二叉树的基本概念 ◼ 3.5.4 二叉树的存储 ◼ 3.5.5 二叉树的遍历 ◼ 3.5.6 树与森林的二叉树表示 ◼ 3.5.7 二叉树的应用 3.5 树与二叉树

树的定义 351树的基本概念 1.树的定义 ◆树是以分支关系定义的层次结构。 ◆倒生树:树根在上,根上分茎,茎上分吐 ◆是族谱、社会组织机构一类实体的逻辑抽象

◼ 3.5.1 树的基本概念 ◼ 1. 树的定义 ◆树是以分支关系定义的层次结构。 ◆倒生树：树根在上，根上分茎，茎上分叶 ◆是族谱、社会组织机构一类实体的逻辑抽象 树的定义

树的定义 对定义的理解 ◆(1)有限集 ◆(2)递归定义:树,根,子树 ◆(3)有且仅有一个根结点不存在空树 ◆(4)子树是互不相交的有限集除根结点以外 ◆(5)树的层次性 的结点有且仅 有且仅有 有一个父结点 个根结点

◼ 对定义的理解 ◆（1）有限集 ◆（2）递归定义：树，根，子树 ◆（3）有且仅有一个根结点不存在空树 ◆（4）子树是互不相交的有限集 ◆（5）树的层次性 有且仅有一 个根结点 除根结点以外 的结点有且仅 有一个父结点 树的定义

树的定义 树是一种数据结构 ◆Tree=(D,R cD:元素的集合 cR:元素关系的集合 (父、子关系前驱、后继关系) ÷各结点没有或仅有一个父结点 ÷有且仅有一个根结点 各结点可以有任意个子树

◼ 树是一种数据结构 ◆ Tree = ( D , R ) D：元素的集合 R：元素关系的集合 ❖（父、子关系 前驱、后继关系） ❖各结点没有或仅有一个父结点 ❖有且仅有一个根结点 ❖各结点可以有任意个子树 树的定义

树的术语 2.树的术语 11)结点 根结点(茎)分支结点叶结点 没有后继,仅有前驱 有且仅有一个前驱,可以有多个后继 没有前驱,仅有后继 2)度与深度 结点的度:该结点拥有的子树数目。 树的度:最大的结点度 深度:最大的层次数

◼ 2. 树的术语 ◼ 1）结点 ◼ 2）度与深度 根结点 没有前驱，仅有后继 结点的度：该结点拥有的子树数目。 树的度：最大的结点度 深度：最大的层次数 (茎)分支结点 叶结点 没有后继，仅有前驱 有且仅有一个前驱，可以有多个后继 树的术语

树的术语 3)A节点的双亲孩子兄弟祖先子孙 A

树的术语 双亲 孩子 兄弟 祖先 子孙 A 3）A节点的

树的术语 4)路径(树枝,分支) ◆从K1出发自上而下到K2所经历的所有结点序列 K1K4K7K2 K1 K3 K4 K5 K6 K7 K2

树的术语 ◼ 4）路径（树枝，分支） ◆从K1出发自上而下到K2所经历的所有结点序列 K1 K2 K3 K4 K5 K6 K7 K1 K4 K7 K2

树的术语 5)有序树与无序树 ◆有序树:兄弟有长幼之分,从左至右。交换兄弟 位置,变成不同的树

树的术语 ◼ 5）有序树与无序树 ◆有序树：兄弟有长幼之分，从左至右。交换兄弟 位置，变成不同的树

树的术语 6)森林 ◆不相交的树的集合

树的术语 ◼ 6）森林 ◆不相交的树的集合

树的存储 352树的存储 1.连续顺序存储 a[0 (K2 K5 a[2] a[3] K6 a[4] 连续线性的下标不能很好的反映树的分支关系(非线性)

树的存储 ◼ 3.5.2 树的存储 ◼ 1. 连续顺序存储 K1 K2 K5 K4 K6 a [ 0 ] a [ 1 ] a [ 2 ] a [ 3 ] a [ 4 ] 连续线性的下标不能很好的反映树的分支关系（非线性）