数据结构第4章树数据结构第4章树第4章树型结构第4章树型结构•树型结构是一种典型的分支结构，并且具有明显的层次特征。•树型结构在客观世界中是广泛存在的，如家族谱、组织机构、博弈等都可用树型结构形象地表示。•树型结构在计算机领域中也有着广泛的应用：编译程序、数据库系统、分析算法4.1树、森林的定义及基本术语4.1树、森林的定义及基本术语•树(tree)是n()个结点的有限集T，当n=0时称为空树，否则满足以下两个条件：–有且仅有一个特定的结点，称为树的根(root)–其余结点可分为m()个互不相交的子集T1,T2,…,Tm，其中每一个子集本身又是一棵树，并称其为根结点的子树(subtree)0n0mabfjecighd4.1树、森林的定义及基本术语4.1树、森林的定义及基本术语•森林是m（m≥0）棵互不相交的树的集合。•用森林的定义也可定义树：一棵非空的树由根结点及其子树森林所构成。•树和森林均为典型的树型结构，从形态上看，树结构类似于自然界倒长的一棵树4.1树、森林的定义及基本术语4.1树、森林的定义及基本术语•基本术语–结点：包含了数据元素及若干个指向其子树的分支。–结点的度：结点的子树数目或分支个数。–树的度：树中各结点的度的最大值。–分支结点（非终端结点）：度大于零的结点。–树叶结点（叶子结点、终端结点）：度为零的结点。–结点的路径：根结点到该结点所经分支和结点构成结点的路径。–结点的路径长度：根结点到该结点路径上所经分支的数目。4.1树、森林的定义及基本术语4.1树、森林的定义及基本术语•基本术语–结点的层次：设根结点的层次为1，则其子树的根结点层次为2；第L层结点的子树的根结点层次为L+1。–树的深度：树中结点（该结点必为树叶结点）的最大层次。–孩子结点及双亲结点：结点的子树的根结点称为该结点的孩子结点，该结点又称为孩子结点的双亲结点。–兄弟结点：拥有同一个双亲结点的若干个结点互称为兄弟结点。–堂兄弟结点：在同一层次上，但双亲结点不同的若干个结点称为堂兄弟结点。4.1树、森林的定义及基本术语4.1树、森林的定义及基本术语•基本术语–祖先结点：根结点到该结点路径上的所有结点均为该结点的祖先结点。–子孙结点：某结点的子树中所包含的所有结点均为该结点的子孙结点。–无序树：子树之间不存在次序关系，即子树能够调换，则称该树为无序树。–有序树：子树之间映射客观存在的次序关系（子树不能调换），则称该树为有序树。线性结构和树型结构的比较线性结构和树型结构的比较线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)4.2二叉树4.2二叉树4.2.1二叉树的结构定义•二叉树定义–二叉树是n（n≥0）个结点的有限集，当n=0时，二叉树为空；当n>0时，二叉树由一个根结点及至多两棵互不相交的左右子树组成，且左右子树都是二叉树。•二叉树特点–每个结点至多有二棵子树(即不存在度大于2的结点)–二叉树的子树有左、右之分，且其次序不能任意颠倒4.2.1二叉树的结构定义4.2.1二叉树的结构定义•二叉树的基本形态AABABAB空二叉树只有根结点的二叉树右子树为空左子树为空左右子树均非空C4.2.2几种特殊形态的二叉树4.2.2几种特殊形态的二叉树•满二叉树：一棵深度为k的二叉树若每一层上的结点数都达到最大，则称其为满二叉树。•完全二叉树：一棵具有n个结点且深度为k的二叉树若前k－1层的结点数都达到最大，剩余的结点在第k层中从左至右连续分布，则称其为完全二叉树。•拟满二叉树：一棵具有n个结点且深度为k的二叉树若前k－1层的结点数都达到最大，剩余的结点在第k层中随机分布，则称其为拟满二叉树。•正则二叉树（严格二叉树）：在一棵二叉树中，如果只存在度为0和度为2的结点，则称其为正则二叉树。•平衡二叉树：在一棵二叉树中，若其中任一结点均满足：|左子树的深度右子树的深度–|≤1，则称其为平衡二叉树。4.2.2几种特殊形态的二叉树4.2.2几种特殊形态的二叉树（a）（b）（d）（e）（c）4.2.3二叉树的性质4.2.3二叉树的性质•二叉树性质1–在二叉树的第i层上至多有2i-1个结点。(...
