数据结构与算法 (22).pdf
1第 7 章二 叉 树7.1 二叉树的基本概念7.2 二叉树的存储7.3 二叉树的遍历7.4 二叉树的创建7.5 线索二叉树7.6 哈夫曼树和哈夫曼编码提出的问题：如何查找二叉树中结点的前趋和后继。提出的问题：如何查找二叉树中结点的前趋和后继。解决的方法：解决的方法：1、遍历费时间2、增设前趋、后继指针域降低存储空间的利用率。3、利用二叉链表中的空指针域。237.5.1 线索二叉树的概念7.5.2 二叉树的线索化7.5.3 线索二叉树的运算7.5 线索二叉树如何利用二叉链表的空指针域？将空的左孩子指针域改为指向其前趋，空的右孩子指针域改为指向其后继这种指向前驱或后继的指针称为“线索”加上了线索的二叉链表称为线索链表；相应的二叉树 称为线索二叉树4 线索二叉树的结点结构线索二叉树的结点结构typedeftypedef structstruct nodenodedatatypedatatype datadata;structstruct nodenode*lchildlchild,*,*rchildrchild;intint ltag,rtagltag,rtag;BiThrNodeBiThrNode，*BiThrTreeBiThrTree其中：其中：ltag，rtag为两个标志域为两个标志域ltag=0lchlch域指示结点的左孩子域指示结点的左孩子1lchlch域域指示结点的前驱指示结点的前驱rtag=0rchrch域指示结点的右孩子域指示结点的右孩子1rchrch域指示结点的后继域指示结点的后继dataltagrtaglchildrchild56 二叉树的先序、中序、后序线索化将二叉树中每个结点中的空的左右孩子指针域分别修改为指向其给定顺序（先序、中序、后序）的前趋和后继结点。这样，每个结点的线索化操作应包括以下内容：(1)若左子树为空，则将其左孩子域线索化：左孩子指针lchild 指向其前趋，ltag 置1(2)若右子树为空，则将其右孩子域线索化：右孩子指针rchild 指向其后继，rtag 置1例：先序例：先序,中序和后序线索链表中序和后序线索链表A00B01C00D10E10G11H11F11先序先序 ABDGCEHF7A00B01C00D10E10G11H11F11中序中序DGBAEHCF897.5.1 线索二叉树的概念 7.5.2 二叉树的线索化7.5.3 线索二叉树的操作7.5 线索二叉树在遍历过程中修改结点的空左、右指针域，保存当前访问结点的“前驱”或“后继”信息。遍历过程中，附设指针pre指向刚访问过的结点，p指向当前访问结点。即：pre是p的前驱 如何建立线索二叉树？1011主要步骤：对结点p的线索化分两步进行：当p 为当前结点时，可进行p的前趋线索化p-lchild=pre 当p为当前结点时，对其前趋pre的后继线索化pre-rchild=p111111prep12二叉树非空时，遍历该二叉树，对任一结点 p，有：若其前趋结点 pre 不空，且 pre 无右孩子，则将 pre 后继线索化：pre-rtag=1;pre-rchild=p;若 p 无左孩子，则将p前驱线索化：p-ltag=1,p-lchild=pre 将pre后移，指向其后继结点 p，即 pre=p 二叉树线索化算法：对应遍历算法的扩展。13 重复上述3步，直到遍历全部结点。prep111111prep14BiThrTree pre=NULL;void PreThread(BiThrTreeroot)BiThrTreep;p=root;if(p)if(pre&pre-rchild=NULL)pre-rtag=1;pre-rchild=p;/前驱结点后继线索化前驱结点后继线索化if(p-lchild=NULL)p-ltag=1;p-lchild=pre;/当前结点前驱线索化当前结点前驱线索化pre=p;PreThread(p-lchild);PreThread(p-rchild);线索化节点p 先序线索化算法15void InThreading(BiThrTree p)if(p)InThreading(p-lchild)；/左子树线索化左子树线索化if(pre&pre-rchild=NULL)pre-rtag=1;pre-rchild=p;/前驱结点后继线索化前驱结点后继线索化if(p-lchild=NULL)p-ltag=1;p-lchild=pre;/当前结点前驱线索化当前结点前驱线索化pre=p;/pre指向当前结点指向当前结点InThreading(p-rchild);/右子树线索化右子树线索化 中序线索化算法线索化的过程即为在遍历过程中修改空指针的过程。167.5.1 线索二叉树的概念7.5.2 二叉树的线索化7.5.3 线索二叉树的运算7.5 线索二叉树17查找给定结点在指定次序下的前趋和后继。共有三组6个问题：先序线索二叉树中求解先序前趋和后继中序线索二叉树中求解中序前趋和后继后序线索二叉树中求解后序前趋和后继 线索二叉树的查找在线索二叉树中查找中序前驱的方法（1）当结点没有左子树时，即：当p-ltag=1 时，p-lchild 既为所求前驱结点（线索）。（2）当结点有左子树时，即：当p-ltag=0 时，p的前驱结点为p的左子树的最右下结点。如何在中序线索树找如何在中序线索树找指定结点的前趋指定结点的前趋？1.中序前驱18BiThrTree InPre(BiThrTree p)BiThrTree p;BiThrTree q;q=p-lchild;在中序线索树中找结点 p的中序前趋p的左孩子为空p的左孩子不空if(p-ltag=0)while(q-rtag=0)q=q-rchild;return(q)pqpq19分析：（1）若p无右子树，则p-rchild 指向其后继。（2）若p 有右子树，则其右子树中最左下的结点为其后继。2.中序后继（中序遍历次序中查找某结点的后继）pqABCDEFGX中序：AXEGCFBD2021BiThrTree InNext(BiThrTree p)BiThrTree q;q=p-rchild;/可能是右孩子，也可能是后继if(p-rtag=0)/*P右子树非空右子树非空while(q-ltag=0)q=q-lchild；/找右子树的“最左下”结点找右子树的“最左下”结点return(q);算法描述如下：
