09.线索二叉树与哈夫曼树.ppt

4.【 2000年计算机系考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 28 25 40 55 60 33 08 54 解:因为中序遍历序列是：55 40 25 60 28 08 33 54 对应线索树应当按此规律连线，即在原二叉树中添加虚线。 NIL NIL 线索二叉树的操作 下面以中序线索二叉树为例，讨论线索二叉树的建立、线索二叉树的遍历以及在线索二叉树上查找前驱结点、查找后继结点、插入结点和删除结点等操作的实现算法 1．建立一棵中序线索二叉树 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。 另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。 目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。 注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针→当前结点之指针； pre指针→前驱结点之指针。 技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针p应当送到前驱结点的空右域中。 若p-lchild＝NULL,则{p-Ltag=1;p-lchild＝pre;} //p的前驱结点指针pre存入左空域 若pre-rchild＝NULL, 则{pre-Rtag＝1;pre-rchild=p;} //p存入其前驱结点pre的右空域 下面是建立中序线索二叉树的递归算法，其中pre为全局变量 int InOrderThr(BiThrTree *head,BiThrTree T) {/*中序遍历二叉树T，并将其中序线索化，*head指向头结点。*/ if (!(*head =(BiThrNodeType*)malloc(sizeof(BiThrNodeType)))) return 0; (*head)-ltag=0; (*head)-rtag=1; /*建立头结点*/ (*head)-rchild=*head; /*右指针回指*/ if (!T) (*head)-lchild =*head; /*若二叉树为空，则左指针回指*/ else { (*head)-lchild=T; pre= head; InThreading(T); /*中序遍历进行中序线索化*/ pre-rchild=*head; pre-rtag=1; /*最后一个结点线索化*/ (*head)-rchild=pre; } return 1; } 中序遍历进行中序线索化 函数 void InTreading(BiThrTree p) {/*中序遍历进行中序线索化*/ if (p) { InThreading(p-lchild); /*左子树线索化*/ if (!p-lchild) /*前驱线索*/ { p-ltag=1; p-lchild=pre; } if (!pre-rchild) /*后继线索*/ { pre-rtag=1; pre-rchild=p; } pre=p; InThreading(p-rchild); /*右子树线索化*/ } } 2．在中序线索二叉树上查找任意结点的中序前驱结点 对于中序线索二叉树上的任一结点，寻找其中序的前驱结点，有以下两种情况： （1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点； （2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点 在中序线索二叉树上寻找结点p的中序前驱结点的算法如下 BiThrTree InPreNode（BiThrTree p） {/*在中序