第12讲索二叉树.pptVIP

* 一、线索二叉树 定义：线索、线索化、线索二叉树 在一个n结点的链式存储二叉树中，有n+1个指针域是空指针域，可以把每个空指针域用于存放分别指向某种遍历次序的前趋和后继结点的指针。 在结点的空指针域中存放的该结点在某遍历次序下的前趋结点和后继结点的指针叫做线索。 * 遍历二叉树的结果是， 求得结点的一个线性序列 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 * 指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索” 与其相应的二叉树， 称作 “线索二叉树” 包含 “线索” 的存储结构，称作 “线索链表” A B C D E F G H K ^ D ^ C ^ ^ B E ^ * 定义：线索、线索化、线索二叉树 把某结点原来空的左（右）指针域用于存放指向其前趋（后继）结点的指针，也叫左（右）线索。 对一个二叉树中的所有结点的空指针域按照某种遍历次序加线索的过程叫作线索化，被线索化了的二叉树称作线索二叉树。 一、线索二叉树 * 增加两个标志域： 0 leftChild域指示结点的左孩子 1 leftChild域指示结点的前驱 0 rightChild域指示结点的右孩子 1 rightChild域指示结点的后继 leftTag = rightTag = leftChild leftTag data rightTag rchildChild 一、线索二叉树 * 中序线索二叉树： 图中的虚线箭头即为新加上的线索。 一、线索二叉树 * 后序序列 D B E C A 前序序列 A B D C E 一、线索二叉树 * 带表头结点的中序线索二叉树 一、线索二叉树 * 实战： 1、对于下图二叉树，画出其前序线索二叉树、中序线索二叉树和后序线索二叉树。 A E D C B F G H 2、n个结点的线索二叉树上含有线索数为（） A 2n B n-1 C n+1 D n * （1） 中序线索化 对一个二叉树进行中序线索化的算法基本思想是：一边中序遍历一边建立线索。 a) 若访问结点的左孩子结点为空，则建立前趋线索； b) 若右孩子结点为空，则建立后继线索。 为此附设一个指针pre始终指向刚刚访问过的结点，而用指针cur指示当前正在访问的结点。pre的初始值为NULL。 一、线索二叉树 * 中序线索化算法 一、线索二叉树 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; } * 中序线索化算法 一、线索二叉树 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); } } * （2） 中序线索树求后继结点 在中序遍历线索树过程中，按下述两条原则即可找到后继结点： a) 如果某结点的右线索标志域为1，说明其右指针域是线索，这个线索所指的即是该结点的后继结点； b) 如果某结点的右线索标志为0，则其右指针域是指向右儿子结点的指针，由此结点的右儿子结点起按左指针域指针逐结点向左查找，一直找到左线索标志域为1的结点，即是该结点的后继结点。 一、线索二叉树 * （3） 中序线索树求前趋结点 找前趋结点相应的原则如下： a)