chapter06树和二叉树.ppt

第六章树和二叉树,6.1树,6.1.1树的定义,6.1.2基本术语,6.2二叉树,6.2.1二叉树的定义,6.2.2二叉树的性质,6.3二叉树的存储结构,6.3.1顺序存储结构,6.3.2链序存储结构,6.4二叉树的遍历与线索化,6.4.1二叉树的遍历,6.4.2二叉树的线索化,6.5.2森林与二叉树的转换,6.5.3树和森林的遍历,6.1树,6.1.1树的定义,（1）定义树（Tree）：是n（n0）个结点的有限集。定义一：（递归定义）：在任意一棵非空树中，有且仅有一个特定的称为根（root）的结点；当n1时，其余结点可分为m（m0）个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树。并且T1,T2,Tm，称为根的子树（SubTree）。定义二：（形式定义）任何一棵树是一个二元组Tree=(root,F)。其中：root是数据元素，称做树的根结点；F是m（m0）棵树的森林，F（T1,T2,Tm），其中Ti=(ri,Fi)称做根root的第i棵子树；当m0时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m;m0,（2）表示形式,该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集：T1=B,E,F,K,L，T2=C,G，T3=D,H,I,J,M;T1、T2和T3都是A的子树，其本身也是一棵树。,图6.1一般的树,该树又可表示为如下三种形式：,(a)嵌套集合表示,(c)凹入表示法,(A(B(E(K,L),F),C(G),D(H(M),I,J)(b)广义表表示,图6.2树的其他3种表示法,（3）树的抽象数据类型定义,CreateTree(初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。,Parent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。InsertChild(初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ADTTree,6.1.2基本术语,结点：包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。,结点的度（Degree）：结点拥有的子树树。,叶子（或终端结点）（Leaf）：度为0的结点。即没有子树的结点。,分支结点（或非终端结点）：度不为0的结点。,内部结点：除根结点之外的分支结点。,树的度：树内各结点的度的最大值。,孩子（Child）：结点的子树的根，称为该结点的孩子。,双亲（Parent）：结点的子树的根，称为该结点的孩子，该结点称为孩子的双亲。,兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。,子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。,祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。,森林（Forest）：是m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。,层次（Level）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第k层，则其子树的根就在第k1层。,堂兄弟：其双亲在同一层的结点互为堂兄弟。,深度（高度）（Depth）：树中结点的最大层次。,有序树：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。,6.2二叉树,6.2.1二叉树的定义,（1）定义二叉树（BinaryTree）：是另一种树型结构。特点：每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。子树有左右之分，其次序不能任意颠倒。,（2）图形表示,(a)(b)(c)(d)(e),图6.3二叉树的5种基本形态,(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左、右子树均非空的二叉树(e)左子树为空的二叉树,（3）二叉树的抽象数据类型定义,CreateBiTree(初始条件：二叉树T存在，e是T中某个结点。操作结果：结点e赋值为value。,Parent(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。LeftSibling(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。RightSibling(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。InsertChild(T,P,LR,c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。操作结果：根据LR为0或1，插入c为T中p指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。,DeleteChild(T,P,LR);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。PreOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：先序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：后序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：层序遍历T，对每个结点调用函数visit()一次且仅一次。一旦visit()失败，则操作失败。ADTBinaryTree,（4）特殊形态的二叉树,满二叉树：一棵深度为k且有2k1个结点的二叉树称为满二叉树。特点：每一层上的结点数都是最大结点数。,完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l1。,(a)满二叉树,(b)完全二叉树,图6.4特殊形态的二叉树,(c)非完全二叉树(d)非完全二叉树,6.2.2二叉树的性质,性质一：在二叉树的第i层上至多有2i-1个结点，(i1)。,性质二：深度为k的二叉树至多有2k1个结点，(k1)。,性质三：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,性质四：具有n个结点的完全二叉树的深度为。,6.3二叉树的存储结构,6.3.1顺序存储结构,/-二叉树的顺序存储表示-#defineMAX_TREE_SIZE100/二叉树的最大结点数typedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTreebt;,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i1的分量中。,例如，图6.5所示为图6.4(b)所示完全二叉树和图6.4(c)所示二叉树的顺序存储结构。,图6.5二叉树的顺序存储结构,(a)完全二叉树,(b)一般二叉树,图中以“0”表示不存在此结点,6.3.2链序存储结构,（1）二叉链表,定义二叉链表：用上述结点结构所得二叉树的存储结构称之为二叉链表。,图形表示,(a)单支树的二叉链表,(b)二叉链表,图6.7二叉链表存储结构,易知，在含有n个结点的二叉链表中有n1个空链域。,typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree,二叉链表的存储表示,StatusPostreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/后序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。StatusLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee);/采用二叉链表存储结构，Visit是对结点操作的应用函数。/层序遍历T，对每个结点调用函数Visit()一次且仅一次。/一旦Visit()失败，则操作失败。,其中，data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子；parent：双亲指针域，指向该结点的双亲结点。,（2）三叉链表,结点结构,定义三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表,图形表示,图6.8三叉链表存储结构,6.4二叉树的遍历与线索化,6.4.1二叉树的遍历,遍历二叉树（traversingbinarytree）：按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。,例如，图6.9所示的二叉树表示下述表达式：a+b*(cd)e/f。先序遍历：+a*bcd/ef表达式的前缀表示（波兰式）中序遍历：a+b*cde/f表达式的中缀表示后序遍历：abcd*+ef/表达式的后缀表示（逆波兰式）层序遍历：+/a*efbcd,图6.9(a+b*(cd)e/f)表达式的二叉树,（1）递归算法,先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。,中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。,后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。,层序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则按从上到下，从左到右的次序访问各结点。,StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。/最简单的Visit函数是：/StatusPrintElement(TElemTypee)/输出元素e的值/printf(e);/实用时，加上格式串/returnOK;/调用实例：PreOrderTraverse(T,PrintElement);if(T)if(Visit(Tdata)if(PreOrderTraverse(Tlchild,Visit)if(PreOrderTraverse(Trchild,Visit)returnOK;returnERROR;elsereturnOK;/PreOrderTraverse,若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下：,（2）非递归算法,以中序遍历为例说明二叉树遍历的非递归算法。,仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应的非递归算法：,工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树树根的指针进栈；,若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回,则应访问当前层即栈顶记录中指针所指的根结点；,若是从右子树返回，则表明当前层的遍历结束，应继续退栈。,由上述分析可得两个中序遍历二叉树的非递归算法如下所示：,算法6.2如下：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(GetTop(S,p)/InOrderTraverse,算法6.3如下：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数。/中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);P=T;while(p|!StackEmpty(S)if(p)/根指针进栈，遍历左子树Push(S,p);p=plchild;/ifelse/根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!Visit(pdata)returnERROR;p=prchild);/else/whilereturnOK;/InOrderTraverse,（3）二叉树的建立,算法6.4是一个按先序序列建立二叉树的二叉链表的过程。,算法6.4如下：StatusCreateBiTree(BiTree/CreateBiTree,图6.10二叉树,例如，对图6.10所示二叉树，按下列次序顺序读入字符：,ABCDEGF,6.4.2二叉树的线索化,当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。,作如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。,（1）线索链表的结点结构,其中：data：数据域；lchild：左指针域，指向该结点的左孩子；rchild：右指针域，指向该结点的右孩子；,（2）线索链表的定义线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之为线索链表。,（3）相关术语,线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。,线索二叉树（ThreadedBinaryTree）：加上线索的二叉树。,线索：在线索链表中指向结点前驱和后继的指针。,（4）图形表示,(a)(a+b*(cd)e/f)表达式的二叉树,(b)中序线索二叉树,图6.11线索二叉树及其存储结构,(c)中序线索链表,图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。,（5）C语言描述/-二叉树的二叉线索存储表示-typedefenumPointerTagLink,Thread;/Link=0:指针，Thread=1:线索typedefstructBiThrNodeTElemTypedata;structBiThrNode*lchild,*rchild;/左右孩子指针PointerTagLTag,RTag;/左右标志BiThrNode,*BiThrTree;,（6）遍历算法,仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。这就为二叉树建立了一个双向线索链表，既可从第一个结点起顺后继进行遍历，也可从最后一个结点起顺前驱进行遍历。下述算法正是以双向线索链表为存储结构时对二叉树进行遍历的算法。,算法6.5如下：StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)/T指向头结点，头结点的左链lchild指向根结点，可参加线索化算法。/中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p=Tlchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=Twhile(pLTag=Link)p=plchild;if(!Visit(pdata)returnERROR;/访问其左子树为空的结点while(pRTag=Thread/InOrderTraverse_Thr,（7）二叉树的线索化算法,算法6.6如下：StatusInOrderThreading(BiThrTree/InOrderThreading,指针pre始终指向刚刚访问过的结点,若指针p指向当前访问的结点,则pre指向它的前驱,算法6.7如下：voidInThreading(BiThrTreep)if(p)InThreading(plchild);/左子树线索化if(!plchild)/前驱线索pLTag=Thread;plchild=pre;if(!prerchild)/后继线索preRTag=Thread;prerchild=p;pre=p;InThreading(prchild);/右子树线索化/if/InThreading,线索化的过程是在遍历过程中修改二叉链表中的空指针为指向前驱或后继的线索的过程。,6.5树和森林,6.5.1树的存储结构,（1）双亲表示法,C语言描述假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。,#defineMAX_TREE_SIZE100typedefstructPTNode/结点结构TElemTypedata;intparent;/双亲位置域PTNodetypedefstruct/树结构PTNodenodesMAX_TREE_SIZE;intr,n;/根的位置和结点数PTree;,图形表示数组下标,图6.12树的双亲表示法示例,（2）孩子表示法,定义孩子表示法：把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。,C语言描述typedefstructCTNode/孩子结点intchild;structCTNode*next;*ChildPtrtypedefstructTElemTypedata;ChildPtrfirstchild;/孩子链表头指针CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根的位置；CTree,图形表示,(a)原树,(b)孩子链表,上图(c)是把双亲表示法和孩子表示法结合起来，即将双亲表示和孩子链表合在一起的存储结构。,(c)带双亲的孩子链表,图6.13树的另外两种表示法,（3）孩子兄弟表示法,定义孩子兄弟表示法：又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。,C语言描述typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree,图形表示,图6.14树的二叉链表表示法,6.5.2森林与二叉树的转换,（1）森林转换成二叉树,如果F=T1,T2,Tm是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。若F为空，即m0，则B为空树；若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1=T11,T12,T1m转换而成的二叉树;其右子树RB是从森林F=T2,T3,Tm转换而成的二叉树。,（2）二叉树转换成森林,如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F=T1,T2,Tm。若B为空，则F为空；,若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T1中的根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F=T2,T3,Tm是由B的右子树RB转换而成的森林。,例，图6.15展示了森林与二叉树之间的对应关系。,图6.15森林与二叉树的对应关系,6.5.3树和森林的遍历,树的遍历方法：先根（次序）遍历，即：先访问树的根结点，然后依次先根遍历根的每棵子树；后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。,例如，对图6.16的树进行遍历，可得树的序列为：先根遍历：ABCDE后根遍历：BDCEA,图6.16,森林的遍历方法：,先序遍历森林若森林非空，则可按下述规则遍历之：1访问森林中第一棵树的根结点；2先序遍历第一棵树中根结点的子树森林；3先序遍历除去第一棵树之后剩余的树构成的森林。,中序遍历森林若森林非空，则可按下述规则遍历之：1中序遍历森林中第一棵树的根结点的子树森林；2访问第一棵树的根结点；3中序遍历除去第一棵树之后剩余的树构成的森林。,例如，对图6.15中森林进行遍历，得到森林的序列为：先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG,6.6赫夫曼树及其应用,6.6.1最优二叉树（赫夫曼树）,（1）基本概念,路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。,路径长度：路径上分分支数目。,树的路径长度：从树根到每一结点的路径长度之和。,结点的带权路径长度：指从该结点到树根之间的路径长度与结点上权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：,最优二叉树（或赫夫曼树）：带权路径长度WPL最小的二叉树。,例1，图6.17中3棵二叉树，都有4个叶子结点a、b、c、d，分别带权7、5、2、4，它们的带权路径长度分别为：,(a)WPL=7252224236(b)WPL=7353214246(c)WPL=7152234335,图6.17具有不同带权路径长度的二叉树,例2，利用赫夫曼树得到最佳判定树（见书P144）。,（2）赫夫曼树的构造,赫夫曼算法：根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是赫夫曼树。,例如，图6.18展示了图6.17的赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。,(a),(b),(c),(d),图6.18赫夫曼树的构造过程,6.6.2赫夫曼编码,（1）前缀编码前缀编码：任一个字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。,约定：在二叉树中，左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。,例如，假设有图6.19所示的二叉树，其4个叶子结点分别表示A、B、C、D这4个字符。,由图6.19所得A、B、C、D的二进制前缀编码分别为0、10、110、111,图6.19前缀编码示例,（2）赫夫曼编码,由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵赫夫曼树的问题,由此得到的二进制前缀编码便称为赫夫曼编码。,（3）赫夫曼树和赫夫曼编码的存储表示typedefstructunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree/动态分配数组存储赫夫曼树typedefchar*HuffmanCode;/动态分配数组存储赫夫曼编码表,（4）求赫夫曼编码的算法,voidHuffmanCoding(HuffmanTree/for,算法6.8如下：,向量HT的前n个分量表示叶子结点，最后一个分量表根结