树与二叉树

2020/3/141第3章树数据结构:线性结构和非线性结构线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。2020/3/142先来看一下有关树的实例祖父伯父父亲叔父堂兄堂姐本人堂弟侄儿(a)家族树家族关系表示：R={祖父，伯父,祖父，父亲，祖父，叔父，伯父，堂兄,伯父，堂姐，父亲，本人，叔父，堂弟,堂兄，侄儿}(b)家族谱系的关系表示数据结构线性表和广义表……树图栈队列树二叉树线性表广义表栈和队列（c）书的目录2020/3/1433.1树的基本术语1．树的定义树(Tree)是n(n≥0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m≥0)个互不相交的有限集合T0，Tl，…，Tm-1。其中每个集合又构成一棵树，树T0，Tl，…，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是一种十分重要的非线性的数据结构。2020/3/144AT(a)只有根结点的树ABDCJEGFHKILT1T2T3(b)有12个结点的树图(a)是一棵只有一个根结点的树；图(b)是一棵有12个结点的树，即T={A，B，C，…，K，L}。A是棵根，除根结点A之外，其余的11个结点分为三个互不相交的集合。T1，T2和T3是根A的三棵子树，且本身又都是一棵树。所以树的定义是递归的。2020/3/1452．树的基本术语1.结点的度:一个结点拥有的子树个数,度为零的结点称为叶子结点,其余结点称为非叶子节点或非终结结点。2.树的度:树中所有结点的度的最大值。树中最大分支数为树的度。3.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层。树中结点的最大层次称为树的深度或高度。2020/3/1463.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。4.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。5.祖先:从根结点到该结点路径上的所有结点。6.兄弟:同一个双亲的孩子之间互为兄弟。7.堂兄弟:双亲在同一层的结点互为堂兄弟。8.有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。9.森林:是m(m=0)棵互不相的树的集合。森林与树概念相近,相互很容易转换。2020/3/1473.2.1二叉树的定义与性质二叉树(BinaryTree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。1．二叉树的递归定义二叉树(BinaryTree)是n(n≥0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不相交的左子树和右子树。3.2二叉树例：试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。2020/3/148二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态：(a)(b)(c)(d)(e)图、二叉树的五种基本形态(a)空二叉树(b)只有根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左右子树均不为空的二叉树2020/3/149两种特殊形态的二叉树：满二叉树和完全二叉树。2.满二叉树(FullBinaryTree)深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大；（2）度为1的结点n1=0，树叶都在最下一层上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654k=3n=23-1=7满二叉树2020/3/14103.完全二叉树(CompleteBinaryTree)深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。图完全二叉树完全二叉树的特点：（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1＜n≤2k-1。（3）满二叉树一定是完全二叉树，反之不成立。452132020/3/14111324653241LH1=3RH1=1LH1-RH1=2非完全二叉树非完全二叉树LH2=0RH2=1LH2-RH2=0-1=-12020/3/14124.遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。遍历二叉树：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。2020/3/1413访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。一、遍历方案DLR先序遍历；LDR中序遍历；LRD后序遍历2020/3/14142）中序遍历二叉树算法思想:若二叉树非空，则：1）中序遍历左子树2）访问根结点3）中序遍历右子树算法描述:voidInorder(BiTreebt){//bt为根结点指针if(bt){//根非空Inorder(bt-lchild);visit(bt-data)；Inorder(bt-rchild);}}1）先序遍历二叉树算法思想:若二叉树非空，则：1）访问根结点2）先序遍历左子树3）先序遍历右子树算法描述:voidPreorder(BiTreebt){//bt为根结点指针if(bt){//根非空visit(bt-data)；Preorder(bt-lchild);Preorder(bt-rchild);}}2020/3/1415例1遍历结果:先序:-+a×b-cd/ef中序:a+b×c-d-e/f后序:abcd-×+ef/-acdef－b×＋－+3）后序遍历二叉树算法思想:若二叉树非空，则：1）后序遍历左子树2）后序遍历右子树3）访问根结点算法描述:voidPostorder(BiTreebt){//bt为根结点指针if(bt){Postorder(bt-lchild);Postorder(bt-rchild);visit(bt-data)；}}2020/3/1416例2遍历结果:先序:+-+*3*xxx/1x5中序:3*x*x+x–1/x+5后序:3xx**x+1x/-5++-+*35x/x*xx1例3已知一棵二叉树的中序遍历序列为BDCEAFHG，其后序遍历序列为DECBHGFA，试画出这棵二叉树并写出其先序遍历序列。ABFGHCED先序遍历序列：ABCDFGH2020/3/1417（1）先序遍历的递归算法如下（假定结点的元素值为字符型）：#includestdio.htypedefcharElemType;typedefstructnode//定义链表结构{ElemTypedata;//定义结点值structnode*lchild;//定义左子结点指针structnode*rchild;//定义右子结点指针}BTree;preorder(BTree*root)//前序遍历{if(root!=NULL)//如果不是空结点{printf(“%c\n”,root-data);//输出当前结点值preorder(root-lchild);//递归前序遍历左子结点preorder(root-rchild);//递归前序遍历右子结点}return;//结束}二、遍历算法2020/3/1418voidinorder(BTree*root)//中序遍历{if(root!=NULL)//如果不是空结点{inorder(root-lchild);//递归中序遍历左子结点printf(“%c\n”,root-data);//输出当前结点值inorder(root-rchild);//递归中序遍历右子结点}}(3)后序遍历的算法实现voidpostorder(BTree*root)//后序遍历{if(root!=NULL)//如果不是空结点{postorder(root-lchild);//递归后序遍历左子结点postorder(root-rchild);//递归后序遍历右子结点printf(“%c\n”,root-data);//输出当前结点值}}（2）中序遍历的递归算法如下（假定结点的元素值为字符型）：2020/3/14192．二叉树的性质性质1在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2深度为k的二叉树至多有2k-1个结点(k≥1)。（深度一定，二叉树的最大结点数也确定）性质3二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1性质4结点数为n的完全二叉树，其深度为log2n+l。性质5在按层序编号n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则，结点i的双亲为结点i/2(i1)。⑵2i＞n时，结点i无左孩子，为叶结点；否则结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。例：若一棵树具有n1个度为1的结点，n2个度为2的结点，……,nm个度为m的结点，则这棵树中的叶子结点有多少个。2020/3/14203.2.2二叉树的存储结构同线性表一样，二叉树的存储结构也有顺序和链表两种结构。1．顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。完全二叉树DCGFEBAbt[3]的双亲为3/2=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG00002020/3/1421这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的大量浪费。D二叉树CGFEBA一般二叉树也按完全二叉树形式存储，无结点处用0表示。123456789101112ABCDE0000FG00002020/3/1422例如：深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。⒉链式存储结构（二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表三叉