第12讲线索二叉树

1一、线索二叉树定义：线索、线索化、线索二叉树在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。2遍历二叉树的结果是，求得结点的一个线性序列ABCDEFGHK先序序列ABCDEFGHK中序序列BDCAHGKFE后序序列DCBHKGFEA3指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^C^^BE^4定义：线索、线索化、线索二叉树把某结点原来空的左（右）指针域用于存放指向其前趋（后继）结点的指针，也叫左（右）线索。对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。一、线索二叉树5增加两个标志域：0leftChild域指示结点的左孩子1leftChild域指示结点的前驱0rightChild域指示结点的右孩子1rightChild域指示结点的后继leftTag=rightTag=leftChildleftTagdatarightTagrchildChild一、线索二叉树6○A○C○F○G○B○D○E○H○I中序线索二叉树：图中的虚线箭头即为新加上的线索。一、线索二叉树7后序序列DBECA前序序列ABDCE一、线索二叉树8带表头结点的中序线索二叉树一、线索二叉树9实战：1、对于下图二叉树，画出其前序线索二叉树、中序线索二叉树和后序线索二叉树。AEDCBFGH2、n个结点的线索二叉树上含有线索数为（）A2nBn-1Cn+1Dn10（1）中序线索化对一个二叉树进行中序线索化的算法基本思想是：一边中序遍历一边建立线索。a)若访问结点的左孩子结点为空，则建立前趋线索；b)若右孩子结点为空，则建立后继线索。为此附设一个指针pre始终指向刚刚访问过的结点，而用指针cur指示当前正在访问的结点。pre的初始值为NULL。一、线索二叉树11中序线索化算法一、线索二叉树voidInThreadHelp(ThreadBinTreeNode*cur,ThreadBinTreeNode*&pre){if(cur!=NULL){if(cur-leftTag==CHILD_PTR)InThreadHelp(cur-leftChild,pre);if(cur-leftChild==NULL){cur-leftChild=pre;cur-leftTag=THREAD_PTR;}else{cur-leftTag=CHILD_PTR;}12中序线索化算法一、线索二叉树if(pre!=NULL&&pre-rightChild==NULL){pre-rightChild=cur;pre-rightTag=THREAD_PTR;}elseif(pre!=NULL){pre-rightTag=CHILD_PTR;}pre=cur;if(cur-rightTag==CHILD_PTR)InThreadHelp(cur-rightChild,pre);}}13（2）中序线索树求后继结点在中序遍历线索树过程中，按下述两条原则即可找到后继结点：a)如果某结点的右线索标志域为1，说明其右指针域是线索，这个线索所指的即是该结点的后继结点；b)如果某结点的右线索标志为0，则其右指针域是指向右儿子结点的指针，由此结点的右儿子结点起按左指针域指针逐结点向左查找，一直找到左线索标志域为1的结点，即是该结点的后继结点。一、线索二叉树14（3）中序线索树求前趋结点找前趋结点相应的原则如下：a)如果某结点的左线索标志域为1，说明其左指针域是线索，这个线索所指的即是该结点的前趋结点；b)如果某结点的左线索标志为0，则其左指针域是指向左儿子结点的指针，由此结点的左儿子结点起按右指针域指针逐结点向右查找，一直找到右线索标志域为1的结点，即是该结点的前趋结点。一、线索二叉树15（4）中序遍历线索树P217a)先由根结点指针找到根结点，从根结点起沿左指针逐结点一直向左查找，找到左线索标志为1的结点(“最左”的结点)即为遍历中需首先访问的结点。b)由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。一、线索二叉树16templateclassElemTypevoidInThreadBinTreeElemType::InOrder(void(*Visit)(constElemType&)){if(r!=NULL){ThreadBinTreeNodeclassElemType*cur=root;while(cur-leftTag==CHILD_PTR)cur=cur-leftChild;中序线索二叉树的遍历算法17while(cur!=NULL){(*visit)(cur-data);if(cur-rightTag==THREAD_PTR)cur=cur-rightChild;else{cur=cur-rightChild;while(cur-leftChild==CHILD_PTR)cur=cur-leftChild;}}}}中序线索二叉树的遍历算法18本讲小结重点：1、线索二叉树难点：1、线索二叉树的应用19Homework:1、写算法求中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。（请编程实现）