第12讲线索二叉树VIP免费

1一、线索二叉树定义：线索、线索化、线索二叉树在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。第一页，共二十页。2遍历二叉树的结果是，求得结点的一个线性序列ABCDEFGHK先序序列ABCDEFGHK中序序列BDCAHGKFE后序序列DCBHKGFEA第二页，共二十页。3指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”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+1Dn第九页，共二十页。10（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)由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。一、线索二叉树第十五页，共二十页。16templatevoidInThreadBinTree::InOrder(void(*Visit)(constElemType&))...