文档介绍：数据结构树型结构
学****要点
熟练掌握二叉树的结构特性,了解相应的证明方法。
建立存储结构是进行操作的前提。故须熟悉二叉树的各种存储结构、并把握各种存储结构的特点及适用范围。
遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法,灵活运用遍历算法实现二叉树的其他操作。理解包括层次遍历在内的各种非递归遍历的算法。
理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系,熟练掌握二叉树的线索化过程以及在中序线索化二叉树上找到给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历,而线索二叉树上的线索又为相应的遍历提供了方便。
熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。
学会编写实现树的各种操作的算法。
理解等价关系和等价类问题。
了解最优树的特性,掌握建立最优树和赫夫曼编码的方法。
树型结构
树型结构是一种典型的分支结构,并且具有明显的层次特征。
树型结构在客观世界中是广泛存在的,如家族谱、组织机构、博弈等都可用树型结构形象地表示。
树型结构在计算机领域中也有着广泛的应用:编译程序、数据库系统、分析算法
1 树、森林的定义及基本术语
树(tree)是n ( )个结点的有限集T,当n=0时称为空树,否则满足以下两个条件:
有且仅有一个特定的结点,称为树的根(root)
其余结点可分为m( )个互不相交的子集T1,T2,…,Tm,其中每一个子集本身又是一棵树,并称其为根结点的子树(subtree)
1 树、森林的定义及基本术语
森林是m(m≥0)棵互不相交的树的集合。
用森林的定义也可定义树:一棵非空的树由根结点及其子树森林所构成。
树和森林均为典型的树型结构,从形态上看,树结构类似于自然界倒长的一棵树
1树、森林的定义及基本术语
基本术语
结点:包含了数据元素及若干个指向其子树的分支。
结点的度:结点的子树数目或分支个数。
树的度:在树中取各结点的度的最大值。
分支结点(又称非终端结点):度大于零的结点。
树叶结点(又称终端结点):度为零的结点。
结点的路径:根结点到该结点所经分支和结点构成结点的路径。
结点的路径长度:根结点到该结点路径上所经分支的数目。
1树、森林的定义及基本术语
基本术语
结点的层次:设根结点的层次为1,则其子树的根结点层次为2;第L 层结点的子树的根结点层次为L+1。
树的深度:树中结点(该结点必为树叶结点)的最大层次。
孩子结点及双亲结点:结点的子树的根结点称为该结点的孩子结点,该结点又称为孩子结点的双亲结点。
兄弟结点:拥有同一个双亲结点的若干个结点互称为兄弟结点。
堂兄弟结点:在同一层次上,但双亲结点不同的若干个结点称为堂兄弟结点。
1树、森林的定义及基本术语
基本术语
祖先结点:根结点到该结点路径上的所有结点均为该结点的祖先结点。
子孙结点:某结点的子树中所包含的所有结点均为该结点的子孙结点。
无序树:子树之间不存在次序关系,即子树能够调换,则称该树为无序树。
有序树:子树之间映射客观存在的次序关系(子树不能调换),则称该树为有序树。
线性结构和树型结构的比较
线性结构
树型结构
第一个数据元素(无前驱)
根结点(无前驱)
最后一个数据元素(无后继)
多个叶子结点(无后继)
其它数据元素(一个前驱、一个后继)
其它数据元素(一个前驱、多个后继)
2 二叉树
二叉树的结构定义
二叉树定义
二叉树是n(n≥0)个结点的有限集,当n=0时,二叉树为空;当n>0时,二叉树由一个根结点及至多两棵互不相交的左右子树组成,且左右子树都是二叉树。
二叉树特点
每个结点至多有二棵子树(即不存在度大于2的结点)
二叉树的子树有左、右之分,且其次序不能任意颠倒