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）度与深度 根结点 没有前驱，仅有后继 结点的度：该结点拥有的子树数目。 树的度：最大的结点度 深度：最大的层次数 (茎)分支结点 叶结点 没有后继，仅有前驱 有且仅有一个前驱，可以有多个后继 树的术语