《数据结构 课件 线索二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构 课件 线索二叉树.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 树与二叉树数据结构电子教案数据结构电子教案1第五章第五章 树与二叉树树与二叉树n n线索化二叉树线索化二叉树2 2线索化二叉树线索化二叉树 (Threaded Binary Tree)(Threaded Binary Tree)n又称为穿线树。又称为穿线树。n通过二叉树的遍历，可将二叉树中所有结点通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。数据在这种排列下它的前驱和后继。n希望不必每次都通过遍历找出这样的线性序希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，列。只要事先做预
2、处理，将某种遍历顺序下将某种遍历顺序下的前驱、后继关系记在树的存储结构中的前驱、后继关系记在树的存储结构中，以，以后就可以高效地找出某结点的前驱、后继。后就可以高效地找出某结点的前驱、后继。3 3线索线索 (Thread)(Thread)增加前驱增加前驱Pred指针和后继指针和后继Succ指针的二叉树指针的二叉树pred leftChild data rightChild succabcdepredpredpredsuccsuccsuccDAEBCrootpredpredpredpredsuccsuccsuccsucc4 4n这种设计的缺点是每个结点增加两个指针，这种设计的缺点是每个结点增加两
3、个指针，当结点数很大时存储消耗较大。当结点数很大时存储消耗较大。n改造树结点，将改造树结点，将 pred 指针和指针和 succ 指针压缩到指针压缩到 leftChild 和和 rightChild 的空闲指针中，并增的空闲指针中，并增设两个标志设两个标志 ltag 和和 rtag，指明指针是指示子，指明指针是指示子女还是前驱后继。后者称为线索。女还是前驱后继。后者称为线索。nltag(或或rtag)=0，表示相应指针指示左子女，表示相应指针指示左子女（或右子女结点）；当（或右子女结点）；当ltag(或或rtag)=1,表示表示相应指针为前驱（或后继）线索。相应指针为前驱（或后继）线索。lef
4、tChild ltag data rtag rightChild 5 5leftChild ltag data rtag rightChild abcdepredpredpredsuccsuccsuccDAEBCrootpredpredsuccsucc0000111111线索化二叉树及其链表表示线索化二叉树及其链表表示6 6线索化二叉树的类定义线索化二叉树的类定义template struct ThreadNode /线索二叉树的结点类 int ltag,rtag;/线索标志 ThreadNode*leftChild,*rightChild;/线索或子女指针 T data;/结点数据 Thre
5、adNode(const T item)/构造函数 :data(item),leftChild(NULL),rightChild(NULL),ltag(0),rtag(0);7 7template class ThreadTree/线索化二叉树类protected:ThreadNode*root;/树的根指针 void createInThread(ThreadNode*current,ThreadNode*&pre);/中序遍历建立线索二叉树 ThreadNode*parent(ThreadNode*t);/寻找结点t的双亲结点public:ThreadTree():root(NULL)/构
6、造函数8 8 void createInThread();/建立中序线索二叉树 ThreadNode*First(ThreadNode*current);/寻找中序下第一个结点 ThreadNode*Last(ThreadNode*current);/寻找中序下最后一个结点 ThreadNode*Next(ThreadNode*current);/寻找结点在中序下的后继结点 ThreadNode*Prior(ThreadNode*current);/寻找结点在中序下的前驱结点 ;9 9if(current-rtag=1)后继为后继为current-rightChildelse /current
7、-rtag=0 后继为当前结点右子树后继为当前结点右子树 的中序下的第一个结点的中序下的第一个结点 寻找当前结点在中序寻找当前结点在中序下的后继下的后继ABDECFHIKGJ1010寻找当前结点在中序寻找当前结点在中序下的前驱下的前驱if(current-ltag=1)前驱为前驱为current-leftChild else /current-ltag=0 前驱为当前结点左子树前驱为当前结点左子树 中序下的最后一个结点中序下的最后一个结点 ABDECFHIKGJL11 11在中序线索化二叉树中部分在中序线索化二叉树中部分成员函数的实现成员函数的实现template ThreadNode*Thr
8、eadTree :First(ThreadNode*current)/函数返回以*current为根的线索化二叉树中的中/序序列下的第一个结点 ThreadNode*p=current;while(p-ltag=0)p=p-leftChild;return p;1212template /另一个版本见面课本另一个版本见面课本198ThreadNode*ThreadTree:Next(ThreadNode*current)/函数返回在线索化二叉树中结点*current在中序/下的后继结点 ThreadNode*p=current-rightChild;if(current-rtag=0)retu
9、rn First(p);/rtag=0,表示有右子女 else return p;/rtag=1,直接返回后继线索;1313template void ThreadTree :Inorder(void(*visit)(BinTreeNode*t)/线索化二叉树的中序遍历 ThreadNode*p;for(p=First();p!=NULL;p=Next(p)visit(p);14140 A 0 0 B 0 0 C 0 0 D 0 0 E 0 rootpre=NULLcurrent如何创建中序线索?15150 A 0 1 B 0 0 C 0 0 D 0 0 E 0 rootpre=NULLcur
10、rent16160 A 0 1 B 0 0 C 0 1 D 0 0 E 0 rootprecurrent17170 A 0 1 B 0 0 C 0 1 D 1 0 E 0 rootprecurrent18180 A 0 1 B 0 0 C 0 1 D 1 1 E 0 rootprecurrent19190 A 0 1 B 0 0 C 0 1 D 1 1 E 1 rootprecurrent20200 A 0 1 B 0 0 C 1 1 D 1 1 E 1 rootpre后处理2121通过中序遍历建立中序线索化二叉树通过中序遍历建立中序线索化二叉树template void ThreadTree
11、:createInThread()ThreadNode*pre=NULL;/前驱结点指针 if(root!=NULL)/非空二叉树,线索化 createInThread(root,pre);/中序遍历线索化二叉树 pre-rightChild=NULL;pre-rtag=1;/后处理中序最后一个结点;2222template void ThreadTree:createInThread(ThreadNode*current,ThreadNode*&pre)/通过中序遍历,对二叉树进行线索化 if(current=NULL)return;createInThread(current-leftChild,pre);/递归,左子树线索化 if(current-leftChild=NULL)/建立当前结点的前驱线索 current-leftChild=pre;current-ltag=1;2323 if(pre!=NULL&pre-rightChild=NULL)/建立前驱结点的后继线索 pre-rightChild=current;pre-rtag=1;pre=current;/前驱跟上,当前指针向前遍历 createInThread(current-rightChild,pre);/递归,右子树线索化;2424在线索二叉树上插入一个结点n课本1992525