资源描述：
《数据结构第五章-21.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、5.5线索树对二叉树进行某种遍历，可以得到一个线性有序的序列。例如对某二叉树的中序遍历结果:K,D,H,B,G,E,A,X,M,C,F该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。图5.5.1二叉树ABCEFGHDKXMY想得到一个结点的前驱或后继结点，每次总是从根开始遍历。无论是采用递归方式，还是非递归方式，遍历算法中一定包含着堆栈空间。2.线索的方法存储结构中序遍历:A的前驱是————，B的前驱是————;E的前驱是————；D的前驱是————；图5.5.1二叉树ABCEFGHDKXM
2、Y一个结点N如果有左子树，则该结点的前驱就是其左子树中最右的子孙P。这个子孙结点的右链接域一定为空。EHGK中序遍历:H的前驱是D，G的前驱是B;X的前驱是A图5.5.1二叉树ABCEFGHDKXMY一个结点N如果没有左子树，则该结点的前驱就是其所有祖先中,最接近它的“右倾”祖先P。这个结点N的左链接域本身就是空。思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？——我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。用二叉链表法存储包含n个结点的二叉树，结点的指
3、针区域中会有n+1个空指针。这就是线索二叉树（ThreadedBinaryTree）线索二叉树的实现规定：1）若结点有左子树，则Lchild指向其左孩子；否则，Lchild指向其直接前驱(即线索)；2）若结点有右子树，则Rchild指向其右孩子；否则，Rchild指向其直接后继(即线索)。如何区别？约定:当flag域为0时,表示正常情况;当flag域为1时,表示线索情况.前驱(后继)左(右)孩子为区别两种不同情况，特增加两个标志域：各1bitLflagLChilddataRChildRflag图5
4、.5.5中序线索树A00B00C10∧D11E11F1∧1D,B,E,A,C,FNULLNULL图5.5.6二叉树ABEFHKNMDC图5.5.7二叉树前序遍历线索树ABMCKDNFHE图5.5.8二叉树中序遍历线索树ABMFNHKECD图5.5.9二叉树后序遍历线索树ABMDKHNFCE有关线索二叉树的几个术语：线索链表：线索：线索二叉树：线索化：用含flag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程线索化过程就是在遍历过程中
5、修改空指针的过程：将空的Lchild改为结点的直接前驱；将空的Rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）例：【考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825405560330854解:因为中序遍历序列是：5540256028083354对应线索树应当按此规律连线，即在原二叉树中添加虚线。NullNull二叉线索树的结点结构定义typedefstruct{ETypedata;BinaryTreeNode*LChild;boolLflag;
6、BinaryTreeNode*RChild;boolRflag;}BinaryTreeNode；二叉线索树的遍历二叉线索树的各种遍历规则仍是原来的规则，不同的是，由于有了线索，所以在遍历时，将利用线索去追踪后继结点，而不再利用堆栈方式或递归方式使用额外的栈空间。在遍历时，只需要后继线索就可以了，所以，右线索相对更重要。后序线索树不同与前序和中序线索树前序二叉线索树的遍历voidThreadPreOrder(BinaryTreeNode*BT){//前序二叉线索树的遍历BinaryTreeNode*
7、p=BT;while(p){cout<data<<"";if(!p->Lflag)p=p->LChild;elsep=p->RChild;}}中序二叉线索树的遍历InOrderThread中序二叉线索树的遍历思想是：从当前结点指针开始，查找以该结点为根的子孙中最左子孙（向左查找）；访问该结点；将指针指向被访问结点的右链接域所指的结点。如果被访问结点的右链接域是后继（Rflag为true），则转B步骤；否则，是一个右子树的根，则转A步骤；BinaryTreeNode*p=BT;boolfla
8、g;while(!p){while(!p->Lflag)//查找一棵子树的最左子孙p=p->LChild;flag=true;while(flag&&!p){cout<data<<"";//访问结点p=p->RChild;//查找p的右子树的根或后继结点if(!p->Rflag)//p结点存在右子树时，为强制退出作准备flag=p->Rflag;}}二叉树转化为二叉线索树二叉树转化为中序二叉线索树P:当前访问结点，q:指向其前驱结点。另设一个堆栈，以非递归方式遍历二叉树。算
