《算法5线索二叉树课件》由会员分享，可在线阅读，更多相关《算法5线索二叉树课件（21页珍藏版）》请在金锄头文库上搜索。
1、6.6.4 4 线索二叉树线索二叉树 1算法5线索二叉树线索二叉树6.4.1 6.4.1 线索二叉树的定义线索二叉树的定义6.4.2 6.4.2 线索二叉树的遍历算法线索二叉树的遍历算法2算法5线索二叉树目的目的：利用二叉树的空指针保存遍历序列的前驱和：利用二叉树的空指针保存遍历序列的前驱和 后继。后继。 n n个结点的二叉树个结点的二叉树, ,有有2 2n n个指针个指针, ,只用了只用了n-1n-1个个, ,有有n+1n+1个是空指针。个是空指针。用空的用空的左指针左指针指向某一遍历序列的指向某一遍历序列的前驱前驱. .用空的用空的右指针右指针指向某一遍历序列的指向某一遍历序列的后继后继.
2、 .这这两种指针两种指针称为称为线索线索( (Thread)Thread)。为了区分线索与真实指为了区分线索与真实指针，给结点增加两个域针，给结点增加两个域LtagLtag和和RtagRtag6.4.1线索二叉树的概念3算法5线索二叉树lchildlchild LtagLtagdatadata RtagRtag rchildrchildLtag=0: lchild Ltag=0: lchild 指向结点的左子女；指向结点的左子女； Ltag=1: lchild Ltag=1: lchild 指向指向某一遍历序列某一遍历序列前驱；前驱； Rtag=0: rchild Rtag=0: rchild
3、 指向结点的右子女；指向结点的右子女； Rtag=1: rchild Rtag=1: rchild 指向指向某一遍历序列某一遍历序列后继后继；6.4.1线索二叉树的概念4算法5线索二叉树/二叉树的二叉线索存储表示typedefenumLink,ThreadPointerTag;/Link=0：指针，Thread=1：线索typedefstructBiThrNodeTElemTypedata;StructBiThrNode*lchild,*rchild; /左右孩子指针PointerTagLTag,RTag;/左右标志BiThrNode,*BiThrTree;lchildlchild LtagL
4、tag datadata RtagRtagrchildrchild6.4.1线索二叉树的概念5算法5线索二叉树加了线索的二叉树是加了线索的二叉树是线索二叉树线索二叉树；给二叉树加线索的过程是给二叉树加线索的过程是线索化（穿线）线索化（穿线）；按前序遍历序列穿线的二叉树是按前序遍历序列穿线的二叉树是前序线索二叉树前序线索二叉树；按中序遍历序列穿线的二叉树是按中序遍历序列穿线的二叉树是中序线索二叉树中序线索二叉树；按后序遍历序列穿线的二叉树是按后序遍历序列穿线的二叉树是后序线索二叉树后序线索二叉树；中序线索中序线索二叉树简称二叉树简称线索二叉树线索二叉树；6算法5线索二叉树加了线索的二叉树是加了线
5、索的二叉树是线索二叉树线索二叉树；二叉树加线索的过程是二叉树加线索的过程是线索化（穿线）线索化（穿线）；按前序遍历序列穿线的二叉树是按前序遍历序列穿线的二叉树是前序线索二叉树前序线索二叉树；按中序遍历序列穿线的二叉树是按中序遍历序列穿线的二叉树是中序线索二叉树中序线索二叉树；按后序遍历序列穿线的二叉树是按后序遍历序列穿线的二叉树是后序线索二叉树后序线索二叉树；中序线索中序线索二叉树简称二叉树简称线索二叉树线索二叉树；6.4.1线索二叉树的概念7算法5线索二叉树线索二叉树线索二叉树(ThreadedBinaryTree)ThreadedBinaryTree)A AG GD DB BF Fc cE
6、 E（a）二叉树）二叉树A A0 00 0C C0 00 0E E1 11 1F F1 11 1B B0 01 10 01 1D D1 1O OG G1 11 1（b）先序线索树）先序线索树rootABDGCEF8算法5线索二叉树线索二叉树线索二叉树(ThreadedBinaryTree)ThreadedBinaryTree)A AG GD DB BF FC CE E（a）二叉树）二叉树A A0 00 0C C0 00 0E E1 11 1F F1 11 1B B0 01 10 01 1D D1 1O OG G1 11 1（c）中序线索树）中序线索树rootDGBAECF9算法5线索二叉树线索
7、二叉树线索二叉树(ThreadedBinaryTree)ThreadedBinaryTree)A AG GD DB BF FC CE E（a）二叉树）二叉树A A0 00 0C C0 00 0E E1 11 1F F1 11 1B B0 01 10 01 1D D1 1O OG G1 11 1（d）后序线索树）后序线索树rootGDBEFCA10算法5线索二叉树D DB BF FE EA AC CNULLNULLNULLNULL中序线索二叉树中序线索二叉树线索二叉树线索二叉树(ThreadedBinaryTree)ThreadedBinaryTree)11算法5线索二叉树6.4.2线索二叉树的
8、遍历算法线索二叉树的遍历算法算法算法6.56.5：中序遍历二叉线索树：中序遍历二叉线索树T T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数VisitVisit。T T指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，可参见线索化算法。指向根结点，可参见线索化算法。StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee) p=T-lchild
9、;/pp=T-lchild;/p指向根结点指向根结点while(p!=T)while(p!=T)/空树或遍历结束时，空树或遍历结束时，p=Tp=Twhile(p-LTag=Link)p=p-lchild);while(p-LTag=Link)p=p-lchild); if(!Visit(p-data)returnERROR;if(!Visit(p-data)returnERROR;/访问其左子树为空的结点访问其左子树为空的结点while(p-RTag=Thread&p-rchild!=T)while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-da
10、ta);p=p-rchild;Visit(p-data);/访问后继结点访问后继结点p=p-rchild;p=p-rchild;returnOK;returnOK;/InOrderTraverse_Thr/InOrderTraverse_Thr12算法5线索二叉树6.4.2线索二叉树的遍历算法线索二叉树的遍历算法算法算法6.66.6：中序遍历二叉树：中序遍历二叉树T T，并将其中序线索化，并将其中序线索化，ThrtThrt指向头结点指向头结点StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)StatusInOrderThreading(BiThr
11、Tree&Thrt,BiThrTreeT) if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;/Thrt-LTag=Link;Thrt-RTag=Thread;/建头结点建头结点Thrt-rchild=Thrt;/Thrt-rchild=Thrt;/右指针回指右指针回指if(!T)Thrt-lchild=Thrt;if(!T)Thrt-lchi
12、ld=Thrt;/若二叉树空，则左指针回指若二叉树空，则左指针回指elseelseThrt-lchild=Thrt;pre=Thrt;Thrt-lchild=Thrt;pre=Thrt;InThreading(T);/InThreading(T);/中序遍历进行中序线索化中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化最后一个结点线索化Thrt-rchild=pre;Thrt-rchild=pre; returnOK;returnOK;/InOrderThreading/I
13、nOrderThreading13算法5线索二叉树6.4.2线索二叉树的遍历算法线索二叉树的遍历算法voidINThreading(BiThrTreep)voidINThreading(BiThrTreep)if(p)if(p)InThreading(p-lchild);InThreading(p-lchild); /左子树线索化左子树线索化if(!p-lchild)p-LTag=Thread;if(!p-lchild)p-LTag=Thread;p-lchild=pre;p-lchild=pre; /前驱线索前驱线索if(!pre-rchild)pre-RTag=Thread;if(!pre
14、-rchild)pre-RTag=Thread;pre-rchild=p;pre-rchild=p;/后继线索后继线索pre=p;pre=p; /保持保持prepre指向指向p p的前驱的前驱InThreading(p-rchild);InThreading(p-rchild); /右子树线索化右子树线索化 /InThreading/InThreading14算法5线索二叉树非递归中序遍历二叉树的算法非递归中序遍历二叉树的算法( (复习复习) )VoidlnorderTraverse(BiTreeBT)VoidlnorderTraverse(BiTreeBT) 采用二叉链表存储结构，中序遍历二
15、叉树采用二叉链表存储结构，中序遍历二叉树T T的非递归算法的非递归算法. .InitStack(S)InitStack(S)； p=BTp=BT； while(p|!StackEmpty(S)while(p|!StackEmpty(S)if(p)push(Sif(p)push(S，p)p)； p=p-lchildp=p-lchild； / /根指针进栈，遍历左子树根指针进栈，遍历左子树 elseelse根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树 pop(Spop(S，p)p)； visit(p);visit(p);p=p-rchildp=p-rchild；/else/
16、else InOrderTraverseInOrderTraverse6.4.2线索二叉树的遍历算法线索二叉树的遍历算法15算法5线索二叉树对以二叉链表存储的二叉树进行中序线索化(非递归的)voidInOrderThreading(BiThrTreeBT)InitStack(S);/建立栈p=BT;pre=NULL;/p指向根,pre是p的前驱结点while(p|!StackEmpty(S)if(p)push(S,p); / p入栈p=p-lchild;/ p指向左子女elsepop(S,p);/弹出栈顶元素到p中if(!p-lchild)p-lchild=pre;p.ltag=true;if
17、(pre&!pre-rchild)pre-rchild=p;pre.rtag=true;pre=p;p=p-rchild;/ p指向右子女/ end of while/ end of InOrderThreading(BT)visit(p)visit(p)16算法5线索二叉树(中序中序)线索二叉树的线索给我们提供了足够的信息线索二叉树的线索给我们提供了足够的信息, 对其进行遍历时，既不需要递归对其进行遍历时，既不需要递归 (使用了系统栈使用了系统栈), 也不需要栈也不需要栈.对对(中序中序)线索二叉树进行非递归遍历且不线索二叉树进行非递归遍历且不需要设栈时需要主要解决的两个问题需要设栈时需要主
18、要解决的两个问题:1)找到某一次序下的第一个结点找到某一次序下的第一个结点p;2) 找出给定结点找出给定结点p p在某一次序中的后继结点在某一次序中的后继结点;17算法5线索二叉树关键问题关键问题1沿着根的左链走沿着根的左链走,直到无左子女的结点直到无左子女的结点p p，即中序序列中的第一即中序序列中的第一个结点个结点;p=BT;p=BT;while(!p.ltag)p=p-lchild;while(!p.ltag)p=p-lchild;关键问题关键问题2，有如下两种情况：，有如下两种情况：P P无右子女：则无右子女：则p-rchildp-rchild是是p p的后继；的后继；P P有右子女：
19、则有右子女：则p p的右子树中最左的结点就是的右子树中最左的结点就是p p的后继，方法同的后继，方法同关键问题关键问题1。if(p.rtag)p=p-rchild;if(p.rtag)p=p-rchild;/P/P无右子女无右子女elsep=p-rchild;elsep=p-rchild;/P/P有右子女有右子女while(!p.ltag)p=p-lchild;while(!p.ltag)p=p-lchild; 中序遍历中序遍历(中序中序)线索二叉树时如何解决这两个问题线索二叉树时如何解决这两个问题:18算法5线索二叉树前序遍历线索二叉树的算法前序遍历线索二叉树的算法void PreOrder
20、Traverse(void PreOrderTraverse(BiThrTree BTBiThrTree BT) ) p=BT; p=BT; while (p) while (p) visit(p);visit(p); if (!p-ltag) if (!p-ltag) p=p-lchild; p=p-lchild; / P/ P有左子女有左子女 else else if if (!p-rtag) (!p-rtag) p=p-rchild; p=p-rchild; / P/ P有右子女有右子女 elseelse r=p-rchild; r=p-rchild; /p/p是叶是叶子子 while
21、(r & r.rtag) while (r & r.rtag) r=r-rchild; r=r-rchild; if (r) p=r-rchild; if (r) p=r-rchild; else else p=r;p=r; / PreOrderTraverse/ PreOrderTraverse19算法5线索二叉树关键问题关键问题1根就是第一个结点根就是第一个结点.关键问题关键问题2，有如下，有如下3种情况：种情况：P P有左子女：则有左子女：则p p左子女是左子女是p p的后继；否则的后继；否则P P有右子女：则有右子女：则p p的右子女是的右子女是p p的后继的后继; 否则否则P P是叶：沿着是叶：沿着p p的线索走，直到空或一个有右子女的结的线索走，直到空或一个有右子女的结点点r r为止，若空，则为止，若空，则p p无后继，否则无后继，否则r r的右子女是的右子女是pp的的 后后继。继。20算法5线索二叉树线索二叉树线索二叉树(ThreadedBinaryTree)ThreadedBinaryTree)A AD DC CB BG GE EF F（a）二叉树）二叉树A A0 00 0C C0 00 0E E1 11 1F F1 11 1B B0 01 10 01 1D D1 1O OG G1 11 1（d）后序线索树）后序线索树root21算法5线索二叉树
