第6章-树和二叉树-2

第6章树和二叉树YL-2011一、树的定义和基本术语二、二叉树三、二叉树的遍历四、线索二叉树五、树和森林六、赫夫曼树及其应用主要内容YL-2011一、树的定义和基本术语1、树的定义（教材P118）树是n（n≥0）个结点的有限集合。n=0时称为空树。在任意一颗非空树中：（1）有且仅有一个特定的结点被称为根（Root）的结点；（2）当n1时，其余结点被分成m（m0）个互不相交的有限集T1，T2，...，Tm，其中每一集合本身又是一棵树，并且成为根的子树（SubTree）。树的定义是一个递归YL-2011ABCDEFGHIJMKL树根例如:T1T2T3YL-2011结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM2、基本术语（教材P120）YL-2011孩子:结点子树的根双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：ABCDEFGHIJMKL假设某结点在第L层,则其子树的根就在第L+1层树中叶子结点所在的最大层次第1层第2层第3层第4层YL-2011任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF有序树、无序树：如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。YL-2011线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)YL-2011ABCDEFGHK根结点左子树右子树二、二叉树1、二叉树的定义（教材P121）二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分YL-2011二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。YL-2011二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树YL-20112、特殊二叉树（1）斜树所有的结点都只有左子树的二叉树叫左斜树；所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。（2）满二叉树（教材P124）在一颗二叉树中，如果所有分支都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树成为满二叉树。YL-2011（3）完全二叉树（教材P124）树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。12345678910111213141512345678910YL-2011•性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)3、二叉树的性质（重点内容，教材P123-124）•性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。注意：性质1、2的区别例如，高度为4的二叉树，第4层的最大结点数为，总结点数最多为。815YL-2011•性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。12345678910•性质4：具有n个结点的完全二叉树的深度为log2n+1。YL-2011•性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；12345678910(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。YL-2011（1）顺序存储结构4、二叉树的存储结构用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。0123456781234567884567231YL-2011例如:ABCDEFABDCEF0123456789101112131401326YL-2011ADEBCFrootlchilddatarchild结点结构:--二叉链表（2）二叉树的链式存储表示YL-2011typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:（教材P127）YL-2011三、二叉树的遍历所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。YL-20111、按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。按层次遍历该二叉树的序列为：ABCDEFGHKKABECFDGHYL-20112、按根、左子树和右子树三个部分进行遍历二叉树的遍历方式存在六种可能：DLR（根左右）、LDR（左根右）、LRD（左右根）DRL（根右左）、RDL（右根左）、RLD（右左根）如果限定先左后右，则只有前三种方式，即DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。YL-2011ABCDEFGDLRTDLRDLRABEDLRDLRDLRDLRCFDG先序遍历结果:ABCDEFGT（1）DLR先序遍历YL-2011ABCDEFGLDRTLDRLDRABELDRLDRLDRLDRCFDG中序遍历结果:BDCAGFET（2）LDR中序遍历YL-2011（3）LRD后序遍历ABCDEFGT后序遍历结果:DCBGFEAYL-2011ABCDEFGHK练习：分别写出先序、中序、后序遍历的结果。先序序列:ABCDEFGHK中序序列:BDCAHGKFE后序序列:DCBHKGFEAYL-2011【问题1】若已知二叉树结点的先序序列和中序序列，能否确定这棵二叉树呢？这样确定的二叉树是否是唯一的呢？任意一棵二叉树结点的先序序列、中序序列和后序序列都是唯一的。回答是肯定的。【问题2】若已知二叉树结点的先序序列和后序序列，能否确定这棵二叉树？回答是不能。想一想，为什么？YL-20113、由遍历序列恢复二叉树【例】一棵二叉树的前序序列为：ABDEC，中序序列为：DBEAC。请画出这棵树。ABCDE练习：已知二叉树的中序和后序序列分别为：DCBEA和DCEBA；请画出这棵树，并写出先序序列。ABCDEYL-2011若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。（1）先序的遍历算法：（教材P129，算法6.1）4、遍历算法voidPreOrderTraverse(BiTreeT）{if(T==NULL)return;printf(“%c”,T-data);//访问根结点PreOrderTraverse(T-lchild);//遍历左子树PreOrderTraverse(T-rchild);//遍历右子树}YL-2011若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。（2）中序的遍历算法：voidInOrderTraverse(BiTreeT）{if(T==NULL)return;InOrderTraverse(T-lchild);//遍历左子树printf(“%c”,T-data);//访问根结点InOrderTraverse(T-rchild);//遍历右子树}YL-2011若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。（2）后序的遍历算法：voidPostOrderTraverse(BiTreeT）{if(T==NULL)return;PostOrderTraverse(T-lchild);//遍历左子树PostOrderTraverse(T-rchild);//遍历右子树printf(“%c”,T-data);//访问根结点}YL-2011（1）输入结点值，构造二叉树（教材P131算法6.4）算法基本思想:先序(或中序或后序)遍历二叉树，读入一个字符，若读入字符为空，则二叉树为空,若读入字符非空，则生成一个结点。将算法中“访问结点”的操作改为：生成一个结点，输入结点的值。5、遍历算法的应用YL-2011voidCreateBiTree(BiTree*T){charch;scanf(“%c”,&ch);if(ch＝＝’#’)*T=NULL;//以#表示虚结点的值else{*T=(BiTree)malloc(sizeof(BiTNode));(*T)-data=ch;//生成根结点CreateBiTree(&(*T)-lchild);//构造左子树CreateBiTree(&(*T)-rchild);//构造右子树}}YL-2011（2）求二叉树的深度(后序遍历)算法基本思想:首先分析二叉树的深度和它的左、右子树深度之间的关系。从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。需先分别求得左、右子树的深度，算法中“访问结点”的操作改为：求得左、右子树深度的最大值，然后加1。YL-2011intDepth(BiTreeT){intdepthleft,depthright;if(T==NULL)return0;else{depthleft=Depth(T-lchild);depthright=Depth(T-rchild);if(depthleft=depthright)returndepthleft+1;elsereturndepthright+1;}}YL-2011（3）统计二叉树中叶子结点的个数算法基本思想:类似求二叉树深度的算法。二叉树的叶子总数等于它的左、右子树叶子数之和。需先判断结点是否为叶子。YL-2011intCountLeaf(BiTreeT){intlnum,rnum;if(T==NULL)return0;elseif(T-lchild==NULL)&&(T-rchild==NULL))return1;else{lnum=CountLeaf(T-lchild);rnum=CountLeaf(T-rchild);return(lnum+rmum);}}YL-2011四、线索二叉树1、为什么要建线索二叉树？--n个结点，一共有2n个指针域，有n-1条分支线，也就是说，其实存在2n-（n-1）=n+1个空指针域。--在二叉链表中，想知道某个结点的前驱和后继必须遍历一次。线索二叉树可以将遍历时结点的线性关系保留下来YL-2011指向遍历顺序中的“前驱”和“后继”的指针，称作“线索”ABCDEFGHK^D^C^^BE^2、什么叫线索？包含“线索”的存储结构，称作“线索链表”；加上“线索”的二叉树，称为“线索二叉树”。线索化（教材P132）线索化的实质（教材P134）YL-2011增加两个标志域，Ltag和Rtag在二叉链表中，若结点有孩子，则让指针指向它的孩子，否则，指向其前驱（后继）。3、建立线索二叉树的方法【问题】如何区分指针的是左右孩子的指针还是前驱、后继的线索？lchildLTagdataRTagrchild关于LTag和RTag的具体含义：教材P132LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继YL-2011typedefstructBiThrNod{TElemTypedata;structBiThrNode*lchild,*rchild;//左右指针PointerThrLTag,RTag;//左右标志}BiThrNode,*B