第六章树和二叉树 数据结构 线性结构(线性表栈队列等) 非线性结构:至少存在一个数据元素有不 止一个直接前驱或后继(树图等)
第六章 树和二叉树 数据结构: • 线性结构(线性表, 栈,队列等) • 非线性结构: 至少存在一个数据元素有不 止一个直接前驱或后继(树,图等)
第六章树和二叉树 6.1树的定义和基本概念 62二叉树 621树的定义和基本术语 622二叉树的性质 623二叉树的存储结构 63遍历二叉树 631遍历二叉树 632线索二叉树 64树和森林 64.1树的存储结构 642森林与二叉树的转换
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 森林与二叉树的转换 第六章 树和二叉树
第六章树和二叉树 643树和森林的遍历 6.6赫夫曼树及其应用 6.6.1最优二叉树(赫夫曼树) 6.62赫夫曼编码 树型结构是一类重要的非线性结构。树型结构是结点之间 有分支,并且具有层次关系的结构,它非常类似于自然界中的 树。树结构在客观世界国是大量存在的,例如家谱、行政组织 机构都可用树形象地表示。树在计算机领域中也有着广泛的应 用,例如在编译程序中,用树来表示源程序的语法结构;在数 据库系统中,可用树来组织信息;在分析算法的行为时,可用 树来描述其执行过程。等等
6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码 第六章 树和二叉树 树型结构是一类重要的非线性结构。树型结构是结点之间 有分支，并且具有层次关系的结构，它非常类似于自然界中的 树。树结构在客观世界国是大量存在的，例如家谱、行政组织 机构都可用树形象地表示。树在计算机领域中也有着广泛的应 用，例如在编译程序中，用树来表示源程序的语法结构；在数 据库系统中，可用树来组织信息；在分析算法的行为时，可用 树来描述其执行过程。等等
第六章树和二叉树 §6.1树的定义 树(tree)是n个数据元素的有限集(记为 T),对任意一棵树T有: 1.存在唯一一个称为根(r0Ot)的数据元素; 2当n>1时,其它数据元素可分为m(m>0) 个互不相交的有限集T,T2,…,Tm,其中每个 集合T;(i=1,2,…m)本身又是一棵树,并称 树T是根的子树( subtree)
第六章 树和二叉树 §6.1 树的定义 树(tree)是n个数据元素的有限集(记为 T)，对任意一棵树T有： ⒈ 存在唯一一个称为根(root) 的数据元素； ⒉ 当n＞1时，其它数据元素可分为m(m＞0) 个互不相交的有限集T1,T2,•…,Tm，其中每个 集合Ti(i=1,2,…,m)本身又是一棵树，并称 树 Ti是根的子树(subtree)
第六章树和二叉树 树的表示法 1.分支图表示法 2.嵌套集合表示法 3.广义表表示法 (A(B) C)
第六章 树和二叉树 树的表示法 1. 分支图表示法 2. 嵌套集合表示法 A B C D A B C D 3. 广义表表示法 (A(B(D),C))
第六章树和二叉树 树的基本术语 7点:包含一不D和指向其了树的所有分支 2.结点的度:一个结点拥有的子树的个数,度为零的 结点称为叶结点或终端结点。度不为零的结点称为 分支结点或非终端结点。除根结点外,树的其它分 支结点称为树的内部结点。 3.树的度:树中所有结点的度的最大值Max(D(I)) 含义:树中最大分支数为树的度 4.结点的层次及树的深度:根为第一层,根的孩子为 第二层,若某结点为第k层,则其孩子为k+1层 树中结点的最大层次称为树的深度或高度
第六章 树和二叉树 树的基本术语 1. 树的结点:包含一个DE和指向其子树的所有分支; 2. 结点的度:一个结点拥有的子树的个数,度为零的 结点称为叶结点或终端结点。度不为零的结点称为 分支结点或非终端结点。除根结点外，树的其它分 支结点称为树的内部结点。 3. 树的度:树中所有结点的度的最大值Max(D(I)) 含义:树中最大分支数为树的度; 4. 结点的层次及树的深度:根为第一层,根的孩子为 第二层,若某结点为第k层,则其孩子为k+1层. 树中结点的最大层次称为树的深度或高度
第六章树和二叉树 5.森林:是m(m>=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换 6.孩子:一个结点的子树的根称为该结点的孩子。相 应的,该结点称为孩子的双亲。仿此不难理解祖先 结点、子孙结点、兄弟结点的称呼。 7.有序树、无序树:如果树中各结点的子树从左到右 看成是有序且不能交换则此树称为有序树,否则称 为无序树。 树的抽象数据类型定义:见教材P.118-119
第六章 树和二叉树 5.森林:是m(m>=0)棵互不相的树的集合 森林与树概念相近,相互很容易转换. 6.孩子:一个结点的子树的根称为该结点的孩子。相 应的，该结点称为孩子的双亲。仿此不难理解祖先 结点、子孙结点、兄弟结点的称呼。 7.有序树、无序树:如果树中各结点的子树从左到右 看成是有序且不能交换则此树称为有序树，否则称 为无序树。 树的抽象数据类型定义：见教材P.118-119
第六章树和二叉树 §6.2树的基本运算 初始化操作 Inittree(&T):创建一棵空树。 2求根函数Root(T):求树T的根; 3求双亲函数 Parent(T,cure):在树T中求x的双亲 4判树空函数 TreeEmpty(T):若树T为空树,则返回 TRUE,否则返回 faLse。 5求兄弟函数: 在T中求x的左兄弟 LeftChild(T,cure) 在树T中求x的右兄弟 Right Child(T,cure)
第六章 树和二叉树 §6.2 树的基本运算 ⒈ 初始化操作InitTree(&T)：创建一棵空树。 ⒉ 求根函数Root(T)：求树T的根； ⒊ 求双亲函数Parent(T,cur_e)：在树T中求x的双亲。 ⒋ 判树空函数TreeEmpty(T)：若树T为空树，则返回 TRUE，否则返回FALSE。 ⒌ 求兄弟函数： 在T中求x的左兄弟LeftChild(T,cur_e) 在树T中求x的右兄弟RightChild(T,cur_e)
第六章树和二叉树 6.建树函数 CreateTree(&T, definition):按 definitio构造树T。 7.插入子树操作 Insert Child(&T,&P,i,c):插入 c为TP所指结点的第i棵子树。 8.删除子树操作 DeleteChild(&T,&P,i:删除T 中P所指结点的第i棵子树。 9.遍历树操作 Traversetree(T, visit):按某 种顺序按 visit0访问树T中各个结点。 10.置空树操作 Cleartree(&T):将树T置为空树
第六章 树和二叉树 ⒍ 建树函数CreateTree(&T,definition)：按 definitio构造树T。 ⒎ 插入子树操作InsertChild(&T,&P,i,c)：插入 c为T P所指结点的第i棵子树。 ⒏ 删除子树操作DeleteChild(&T,&P,i)：删除T 中P所指结点的第i棵子树。 ⒐ 遍历树操作TraverseTree(T,visit())：按某 种顺序按visit()访问树T中各个结点。 ⒑ 置空树操作ClearTree(&T)：将树T置为空树
第六章树和二叉树 §6.3二叉树概念及性质 二叉树概念 二叉树是结点数为0或每个结点最多只有 左右两棵子树的树。二叉树是一种特殊的树, 它的特点是: (1)每个结点最多只有两棵子树,即不存结点 度大于2的结点; (2)子树有左右之分,不能颠倒
第六章 树和二叉树 §6.3 二叉树概念及性质 一. 二叉树概念 二叉树是结点数为0或每个结点最多只有 左右两棵子树的树。二叉树是一种特殊的树， 它的特点是： ⑴每个结点最多只有两棵子树，即不存结点 度大于2的结点； ⑵子树有左右之分，不能颠倒