第12讲线索二叉树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,一、线索二叉树,定义：线索、线索化、线索二叉树,在一个,n,结点的链式存储二叉树中，有,n+1,个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。,在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。,第12讲 线索二叉树,2,遍历二叉树的结果是，,求得结点的一个线性序列,A,B,C,D,E,F,G,H,K,先序序列,A B C D E F G H K,中序序列,B D C A H G K F E,后序序列,D C B H K G F E A,3,指向该线性序列中的“前驱”和,“后继”的指针，称作“线索”,与其相应的二叉树，,称作,“,线索二叉树,”,包含,“,线索,”,的存储结构，称作,“,线索链表,”,A B C D E F G H K,D,C,B,E,4,定义：线索、线索化、线索二叉树,把某结点原来空的左（右）指针域用于存放指向其前趋（后继）结点的指针，也叫左（右）线索。,对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。,一、线索二叉树,5,增加两个标志域：,0 leftChild,域指示结点的左孩子,1 leftChild,域指示结点的前驱,0 rightChild,域指示结点的右孩子,1 rightChild,域指示结点的后继,leftTag =,rightTag=,leftChild leftTag data rightTag rchildChild,一、线索二叉树,6,中序线索二叉树：,图中的虚线箭头即为新加上的线索。,一、线索二叉树,7,后序序列,D B E C A,前序序列,A B D C E,一、线索二叉树,8,带表头结点的中序线索二叉树,一、线索二叉树,9,实战：,1,、对于下图二叉树，画出其前序线索二叉树、中序线索二叉树和后序线索二叉树。,A,E,D,C,B,F,G,H,2,、,n,个结点的线索二叉树上含有线索数为（）,A 2n B n-1 C n+1 D n,10,（,1,）中序线索化,对一个二叉树进行中序线索化的算法基本思想是：一边中序遍历一边建立线索。,a),若访问结点的左孩子结点为空，则建立前趋线索；,b),若右孩子结点为空，则建立后继线索。,为此附设一个指针,pre,始终指向刚刚访问过的结点，而用指针,cur,指示当前正在访问的结点。,pre,的初始值为,NULL,。,一、线索二叉树,11,中序线索化算法,一、线索二叉树,void InThreadHelp(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;,else if(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,）中序遍历线索树,P217,a),先由根结点指针找到根结点，从根结点起沿左指针逐结点一直向左查找，找到左线索标志为,1,的结点,(“,最左”的结点,),即为遍历中需首先访问的结点。,b),由此结点开始，反复进行寻找后继结点的过程，并陆续访问这些结点，直至结束。,一、线索二叉树,16,template,void InThreadBinTree:InOrder(,void(*Visit)(const ElemType&),if(r!=NULL),ThreadBinTreeNode *cur=root;,while(cur-leftTag=CHILD_PTR),cur=cur-leftChild;,中序线索二叉树的遍历算法,17,while(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,、线索二叉树的应用,19,see you later!,Homework:,1,、,写,算法,求中序线索二叉树中给定值为,x,的结点之后继结点，返回该后继结点的指针,。（请编程实现）,