自考——数据结构第四章02142

第四章树和二叉树第四章树和二叉树4.1树的基本概念4.2二叉树4.3二叉树的存储结构4.4二叉树的遍历4.5树和森林4.6判定树和哈夫曼树树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。4.1树的定义和基本术语树（Tree）——是n(n=0)个结点的有限集合T，满足：(1)当n=0时，称为空树；(2)当n0时，有且仅有一个特定的称为根的结点,其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集Ti又是一棵树，并称为根的子树。一、树的定义递归是树的固有特性二、树的逻辑表示▲一般表示法(直观表示法)：FCEGBDAb、嵌套括号法：(根(子树,子树…子树))(A(B(E,F),C,D(G))根ABFCDGEc、凹入法表示：▲另三种表示法a、文氏图法：BACDEFG——第一层第二层第三层三、树的基本术语●度——结点的度：该结点的子树数（即分支数）。树的度：树中结点的度最大值。●结点—由一个数据元素及若干指向其它结点的分支所组成。●叶子（终端结点）——度为零的结点。●孩子（子结点）——结点的子树的根称为该结点的孩子。相应的该结点称为孩子的双亲（父结点）。●非终端结点——度不为零的结点。●祖先——结点祖先指根到此结点的一条路径上的所有结点。●子孙——从某结点到叶结点的分支上的所有结点称为该结点的子孙。●兄弟——父结点相同的结点互称兄弟。●结点的层次——从根算起，根为第一层，其孩子在第二层,….，L层上任何结点的孩子都在L+1层上。●树的深度——树中结点的最大层次数。●森林——是m（≥0）棵互不相交的树的集合。●有序树——若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。●无序树——若树中各结点的子树是无次序的，可以互换，则成为无序树。求根Root(T):求树T的根结点；求双亲Parent(T,X):求结点X在树T上的双亲结点；若X是树T的根或X不在T上，则结果为一特殊标志；求孩子Child(T,X,i):求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志；建树Create(X,T1,…,Tk),k1:建立一棵以X为根，以T1,…,Tk为第1,…,k棵子树的树；剪枝Delete(T,X,i):删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作；遍历TraverseTree(T):遍历树，即访问树中每个结点，且每个结点仅被访问一次。四、树的基本操作二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。4.2二叉树1、定义：二叉树是n(n=0)个结点的有限集合，它或为空(n=0)，或是由一个根结点及两棵互不相交的左、右子树组成，且每棵子树都是二叉树。4.2.1二叉树的基本概念这是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。ABDCFGHE2、特点：①二叉树可以是空的，称空二叉树；②每个结点最多只能有两个孩子；③子树有左、右之分且次序不能颠倒。３、二叉树与树的比较：结点子树结点顺序树n≥0不定(有限)无二叉树n≥0≤2有(左、右)二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态，图(c)和（d）是不同的两棵二叉树。(a)空二叉树A(b)左右子树均为空的二叉树A(c)右子树为空的二叉树A(d)左子树为空的二叉树A(e)左右子树非空的二叉树二叉树的5种形式初始化Initiate(BT):建立一棵空二叉树，BT=∅。求双亲Parent(BT,X):求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为NULL。建二叉树Create(BT):建立一棵二叉树BT。先序遍历PreOrder(BT)(根、左、右):按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。4、二叉树的基本运算（见P96）中序遍历InOrder(BT)（左、根、右）:按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。后序遍历PostOrder(BT)（左、右、根）:按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。层次遍历LevelOrder(BT):按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。1、性质1：在二叉树的第i(i=1)层上至多有2i-1个结点。二叉树具有下列重要性质：4.2.2二叉树的性质2、性质2：深度为k(k=1)的二叉树至多有2k－1个结点。3、性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。即：叶结点数n0=度为2的结点数n2+1满二叉树（结点数=23-1=7）▲满二叉树中结点顺序编号：即从第一层结点开始自上而下，从左到右进行连续编号。▲满二叉树——深度为k(k=1)且有2k-1个结点的二叉树。123456712345612345712367注：满二叉树是完全二叉树的特例。▲完全二叉树——深度为K的二叉树中，K-1层结点数是满的(2k-2)，K层结点是左连续的(即结点编号是连续的)。如下图（a）(a)完全二叉树YES!(b)非完全二叉树NO!(c)非完全二叉树NO!符号[x]表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1n=2k-1或2k-1=n2k取对数得到：k－1log2nk因为k是整数。所以：k＝[log2n]＋1。4、性质4：具有n个结点的完全二叉树的深度为[log2n]＋1。5、性质5：对有n个结点的完全二叉树的结点按层编号（从第1层到第[log2n]+1层，每层从左到右),则对任一结点i（1≤i≤n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i1，则i的双亲Parent(A)是结点[i/2];（2）如果2*i≤n，则其左孩子是结点2*i,否则，结点i无左孩子且为叶子结点；（3）如果2*i＋1≤n，则其右孩子是结点2*i＋1，否则，结点i无右孩子。A1B2C3D4EF6H8IJ10G759思考题:结点数最少个?▲深度为5的二叉树结点数最多个?结点数最少个?▲深度为5的完全二叉树结点数最多个?53116311.树最适合用来表示()A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.根据定义，树的叶子结点其度数（）A.必大于0B.必等于0C.必等于1D.必等于23.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（）A.99B.98C.97D.504.树形结构中，若结点Ａ有3个兄弟，Ｂ是Ａ的双亲，则Ｂ的度为____________。5.深度为15的满二叉树上，第11层有个结点。6.三个结点可构成种不同形态的二叉树。想一想CBB4210=10245它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。二叉树的顺序存储结构——即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中编号为i的结点存储在数组中下标为i的分量中。——该方法称为“以编号为地址”策略4.3.1二叉树的顺序存储结构4.3二叉树的存储结构对于完全二叉树来说，采用以编号作为数组的下边的方法将结点存入一位数组中，也就是将编号为i的结点存入一维数组的以i为下标的数组元素中。对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。lkjihgfedcba123456789101112abcdefghijkl1234567891011120Btree：lkjihgfedcba123456789101112▲此方法用于完全二叉树，则：●节省内存●结点位置确定方便abcdefghijklABCDEFG^表示该处没有元素存在ABCDE^^^^FG▲用于一般二叉树：（浪费空间）▲用于单分支二叉树则存储空间浪费极大。1234567891011^^^^1234567891011从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！二叉树的顺序存储结构的缺点lchilddatarchild结点形式：左孩指针—指向其左孩结点；右孩指针—指向其右孩结点；▲二叉链表类型定义typedefstructbtnode{Datatypedata;structbtnode*lchild,*rchild;}*Bintree;;——二叉链表类型4.3.2二叉树的链式存储结构▲二叉链表表示法：例：^CAB^DE^^F^^G^^H^▲三叉链表表示法：lchilddataparentrchild结点形式：指向双亲ABDCFGHE二叉链表T注：在含n个结点的二叉链表中有2n个指针域，其中n-1个用来指向结点的左右孩子，其余n+1个空链域.一、遍历含义在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。遍历二叉树——是指按一定规律对二叉树中的每个结点访问且仅访问一次——即访遍树中每一结点（只一次），打印或处理结点。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律（或次序），能把二叉树上的各结点都访问一次且只访问一次。二、遍历规则bc(根结点D)(右子树R)(左子树L)由二叉树的递归定义知，二叉树的三个基本组成单元是：根结点、左子树和右子树。a4.4二叉树的遍历令：L——遍历左子树D——访问根结点R——遍历右子树组合LDR、LRD、DLR、RDL、RLD、DRL先左后右DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。1、先序遍历DLR——首先访问根结点，其次遍历根的左子树，最后遍历根右子树，对每棵子树同样按这三步（先根、后左、再右）进行。2、中序遍历LDR——首先遍历根的左子树，其次访问根结点，最后遍历根右子树，对每棵子树同样按这三步（先左、后根、再右）进行。3、后序遍历LRD——首先遍历根的左子树，其次遍历根的右子树，最后访问根结点，对每棵子树同样按这三步（先左、后右、最后根）进行。三、遍历算法1、先序遍历（递归算法）：▲步骤：若二叉树为空，则退出；否则:（1）访问根结点；（2）先序遍历根的左子树；（3）先序遍历根的右子树。▲算法：voidpreorder(BinTreebt){/*先序遍历根指针为bt的二叉树*/if(bt!=NULL){visit(bt);/*访问根结点*/preorder(bt-lchild)；preorder(bt-rchild);/*先序遍历以右子树*/}}；2、中序遍历运算（递归算法）▲步骤：若二叉树为空，则退出；否则:（1）中序遍历根的左子树；（2）访问根结点；（3）中序遍历根的右子树。▲算法：voidinorder(BinTree