中序线索二叉树的遍历（线索二叉树的遍历）

本文目录

• 线索二叉树的遍历
• 线索化后二叉树的遍历算法
• 在遍历中序线索二叉树时,某结点既有左子树又有右子树,那么它的前驱是其
• 已知某二叉树的后序遍历和中序遍历的序列分别为
• 数据结构 线索二叉树 中序遍历 高手们帮忙看看哪错了啊
• 建立中序线索二叉树，并且中序遍历； 2. 求中序线索二叉树上已知结点中序的前驱和后继
• 简述中序线索二叉树的构造方法
• 给定如图所示二叉树T，请画出与其对应的中序线索二叉树

线索二叉树的遍历

/ BiTree.cpp: implementation of the BiTree class.////////////////////////////////////////////////////////////////////////#include "BiTree.h"#include "iostream.h"#include"Queue.h"#include"stdio.h"//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////BiTree::BiTree(){ root=new BiTNode;}BiTree::~BiTree(){}void BiTree::createbitree(BiTNode *&root){ char ch; cin》》ch; if(ch==’#’) root=NULL; else { root=new BiTNode; root-》data=ch; createbitree(root-》lchild); createbitree(root-》rchild); }}void BiTree::PreTraver(BiTNode *root){ BiTNode *p; p=root; if(p!=NULL) { cout《《p-》data; PreTraver(p-》lchild); PreTraver(p-》rchild); }}void BiTree::InTraver(BiTNode *root){ BiTNode *p; p=root; if(p!=NULL) { PreTraver(p-》lchild); cout《《p-》data; PreTraver(p-》rchild); } }void BiTree::LaTraver(BiTNode *root){ BiTNode *p; p=root; if(p!=NULL) { PreTraver(p-》lchild); PreTraver(p-》rchild); cout《《p-》data; }}void BiTree::getroot(BiTNode *root){ cout《《root-》data;}int BiTree::BitTreeDepth(BiTNode *root){ int h1=0,h3=0,h=0; if(root==NULL) h=0; else { h1=BitTreeDepth(root-》lchild); h3=BitTreeDepth(root-》rchild); if (h1》h3) h=h1+1; else h=h3+1; } return h; }void BiTree::getparent(char ch,BiTNode *root){ BiTNode *a; a=root; if(root!=NULL) { if((a-》lchild!=NULL&&a-》lchild-》data==ch)||(a-》rchild&&a-》rchild-》data==ch)) { cout《《a-》data; } else { getparent(ch,root-》lchild); getparent(ch,root-》rchild); } }}int BiTree::getleaf(BiTNode *root,int #){ BiTNode *p; p=root; if(p!=NULL) { if(p-》lchild==NULL&&p-》rchild==NULL) { num++; cout《《p-》data; } else { getleaf(p-》lchild,num); getleaf(p-》rchild,num); } } return num;}int BiTree::getnum(BiTNode *root,int #){ BiTNode *p; p=root; if(p!=NULL) { num++; getnum(p-》lchild,num); getnum(p-》rchild,num); } return num;}int BiTree::getdu1(BiTNode *root, int& num){ BiTNode *p; p=root; if(p!=NULL) { if((p-》lchild!=NULL&&p-》rchild==NULL)||(p-》lchild==NULL&&p-》rchild!=NULL)) { cout《《p-》data; num++; } else { getdu1(p-》lchild,num); getdu1(p-》rchild,num); } } return num;}int BiTree::getdu2(BiTNode *root,int#){ BiTNode *p; p=root; if(p!=NULL) { if(p-》lchild!=NULL&&p-》rchild!=NULL) { cout《《p-》data; num++; } else { getdu2(p-》lchild,num); getdu2(p-》rchild,num); } }return num;}void BiTree::guangdu(BiTNode *root,Queue &Q){ //Q.InitQueue(Q); if(root!=NULL) Q.EnQueue(root-》data); while(!Q.QueueEmpty()) { Q.DeQueue(root-》data); cout《《root-》data; if(root-》lchild!=NULL) Q.EnQueue(root-》lchild-》data); if(root-》rchild!=NULL) Q.EnQueue(root-》rchild-》data); }}struct BiTNode{ char data; BiTNode *lchild,*rchild,*parent;};class BiTree { BiTNode *root; public: BiTree(); virtual ~BiTree(); void createbitree(BiTNode *&t);//要加引用修改根因为根是变化的 void getroot(BiTNode *t); void getparent(char ch,BiTNode *t); void getlchild(char t,char x); void getrchild(char t,char x); void TraverTree(char t); int BitTreeDepth(BiTNode *t); //void insertChild(BiTree& T,char t,char); void PreTraver(BiTNode *r); void InTraver(BiTNode *r); void LaTraver(BiTNode *r); int getleaf(BiTNode *r,int &t); int getnum(BiTNode *r,int &t); void guangdu(BiTNode *r,Queue &Q); int getdu1(BiTNode*r,int &t); int getdu2(BiTNode*r,int &t); bool IserTree();};#include"iostream.h"#include"BiTree.h"#include"stdio.h"void main(){ BiTree choose; Queue qe; int select=10; while(select!=0) { cout《《"****************请按数字键操作********************"《《endl; cout《《"1---前序创建二叉树."《《endl; cout《《"2---前序遍历输出二叉树."《《endl; cout《《"3---中序遍历输出二叉树."《《endl; cout《《"4---后序遍历输出二叉树."《《endl; cout《《"5---求树的根结点。"《《endl; cout《《"6---求二叉树的高度"《《endl; cout《《"7---求结点的双亲"《《endl; cout《《"8---求二叉树的叶子及叶子数"《《endl; cout《《"9---求结点的个数"《《endl; cout《《"10---求度为1的结点"《《endl; cout《《"11---求度为2的结点 "《《endl; cout《《"12---判断是否为完全二叉树 "《《endl; cout《《"13---广度优先遍历输出"《《endl; cout《《"**************************************************"《《endl; cin》》select; switch(select) { case 1: cout《《"请输入一个二叉树#为空"《《endl; BiTNode *root; choose.createbitree(root); break; case 2: cout《《"该树是:"; choose.PreTraver(root); cout《《endl; break; case 3: cout《《"该树是:"; choose.InTraver(root); cout《《endl; break; case 4: cout《《"该树是:"; choose.LaTraver(root); cout《《endl; break; case 5: cout《《"根结点是:"; choose.getroot(root); cout《《endl; break; case 6: cout《《"该二叉树的深度是:"; int h; h=choose.BitTreeDepth(root); cout《《h; cout《《endl; break; case 7: char ch; cout《《"请输入所要求的结点："; cin》》ch; cout《《"根结点是:"; choose.getparent(ch,root); cout《《endl; break; case 8: int number; number=0; int num; cout《《"该二叉树的叶子是："; num=choose.getleaf(root,number); cout《《"该二叉树的叶子个数是:"; cout《《num; cout《《endl; break; case 9: int k; k=0; int m; m=choose.getnum(root,k); cout《《"该二叉树的结点数是:"; cout《《m; cout《《endl; break; case 10: int n,i; i=0; //cout《《"度为1的结点是："; n=choose.getdu1(root,i); if(n!=0) cout《《"输出的值就是度为1的结点"; else cout《《"度为1的结点没有"; cout《《endl; break; case 11: //cout《《"度为2的结点是："; n=choose.getdu2(root,i); if(n!=0) { cout《《endl; cout《《"输出的数值就是度为2的结点"; } else cout《《"度为二的结点没有"; cout《《endl; break; case 13: choose.guangdu(root,qe); cout《《endl; break; } }}#include "Queue.h"#include"stdio.h"#include"iostream.h"//////////////////////////////////////////////////////////////////////// Construction/Destruction//////////////////////////////////////////////////////////////////////Queue::Queue(){ rear=NULL; front=new QNode;}Queue::~Queue(){}void Queue::InitQueue(){ QNode *front,*rear; front=new QNode; //rear=new QNode; if(!front)//生成头结点失败 cout《《"失败"; front-》next=NULL;}bool Queue::QueueEmpty() { //判断队列是否为空 if(front-》next==NULL) return true; else return false; }void Queue::EnQueue(char &e) { //插入元素e为队列Q的新的队尾元素 QNode *p; p=new QNode; rear=new QNode; //动态生成新结点 //if(!p) //exit(OVERFLOW); p-》data=e;//将e的值赋给新结点 p-》next=NULL;//新结点的指针为空 rear-》next=p;//原队尾结点的指针域为指向新结点 rear=p;//尾指针指向新结点 }char Queue::DeQueue(char &e) { //若队列不为空，删除Q的队头元素，用e返回其值 QNode *p; if(front==rear)//队列为空 cout《《"队列为空"; else {p=front-》next; rear-》next=p;//p指向队头结点 e=rear-》next-》data;//队头元素赋给e front-》next=p-》next; rear-》next=p-》next; }//头结点指向下一个结点 if(rear==p)//如果删除的队尾结点 rear=front;//修改队尾指针指向头结点 delete p; return e; }struct QNode{ char data; QNode *next;};class Queue { //QNode *rear,*front; public: QNode *rear,*front; Queue(); bool QueueEmpty(); virtual ~Queue(); void InitQueue(); void EnQueue(char &e); char DeQueue(char &e);};顺序有点乱你自己看看把除了你说的还有其他的功能，做一下参考吧

线索化后二叉树的遍历算法

兄弟,你哪的人?我也在做这个课程设计.(题完全一样哈)目前把中序遍历线索化二叉树做出来了,加我QQ:450104299代码如下:#include 《stdio.h》 #include 《iostream.h》 #include 《malloc.h》 #include《stdlib.h》 typedef char DataType;//定义DataType类型 typedef enum PointerTag{Link,Thread}; typedef struct BiThrNode{ DataType data; struct BiThrNode *lchild, *rchild;//左右孩子子树 PointerTag LTag,RTag; }BiThrNode; //结点类型typedef BiThrNode *BiThrTree ;//二叉树类型void CreatBinTree(BiThrTree &T) //构造二叉链表,注意:输入序列是先序序列 { char ch;scanf("%c",&ch);if (ch==’#’) T=NULL; else //读入非空格{ T=(BiThrTree )malloc(sizeof(BiThrNode));//生成结点T-》data=ch;T-》LTag=Link;T-》RTag=Link; CreatBinTree(T-》lchild); //构造左子树 CreatBinTree(T-》rchild); //构造右子树}} BiThrTree pre;//全局变量void InThreading(BiThrTree p) { if(p) { InThreading(p-》lchild);//左子树线索化 if(!p-》lchild) {p-》LTag=Thread;p-》lchild=pre;}//前驱线索if(!pre-》rchild) {pre-》RTag=Thread;pre-》rchild=p;}//后继线索pre=p;//保持pre指向p InThreading(p-》rchild);//右子树线索化} } void InOrderThreading(BiThrTree &Thrt,BiThrTree T) //中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点{ if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0); Thrt-》LTag=Link; Thrt-》RTag=Thread;//建头结点Thrt-》rchild=Thrt;//右指针回指 if(!T) Thrt-》lchild=Thrt; else { Thrt-》lchild=T; pre=Thrt; InThreading(T);//中序遍历进行中序线索化pre-》rchild=Thrt;pre-》RTag=Thread;//最后一个结点线索化Thrt-》rchild=pre; } } void print(BiThrTree e) {printf("%d%c%d\n",e-》LTag,e-》data,e-》RTag);} void InOrderTraverse(BiThrTree T,void (* visit)(BiThrTree e)) //T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树{BiThrTree p; p=T-》lchild;//p指向根结点while(p!=T)//空树或遍厉结束时，p==T{while(p-》LTag==Link) p=p-》lchild; printf("%c ",p-》data); //打印 while(p-》RTag==Thread&&p-》rchild!=T) {p=p-》rchild;printf("%c ",p-》data);}//访问后继结点 p=p-》rchild; }printf("\n"); } void main() //测试程序 { printf("按先序序列输入二叉树各结点:\n");BiThrTree T,Thrt; CreatBinTree(T); InOrderThreading(Thrt,T); printf("中序法遍历线索化二叉树：\n");InOrderTraverse(Thrt,print); }

在遍历中序线索二叉树时,某结点既有左子树又有右子树,那么它的前驱是其

D，中序即左中右的顺序，显然在访问时先访问结点N的左子树，而对于结点N的左子树，仍然按照左中右的顺序访问，故对该左子树，最后访问其最右下的结点，然后就会访问N，所以，对于结点N，其中序前驱是其左子树最右下的结点。

已知某二叉树的后序遍历和中序遍历的序列分别为

您好，你的问题，我之前好像也遇到过，以下是我原来的解决思路和方法，希望能帮助到你，若有错误，还望见谅！已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历是DGEBHFCA。前序遍历的第一个节点为根节点，由前序遍历可知，A为根节点。中序遍历的根节点前面的节点均为左子树的节点，所以左子树上的节点为DBGE。去掉根节点和左子树节点，右子数节点为CHF。前序遍历的第二个节点为B，由2知B为左子树节点，所以B为左子树的根节点。由前序遍历，DEG在B节点下面，由中序遍历，D是B的左节点，GE是B的右节点。由前序遍历，E是G的根节点，由中序遍历，G是E的左子节点。由前序遍历，C是二叉树的右根节点，由中序遍历，C不含左子节点，HF为C的右子节点。由前序遍历，F为H的根节点，由中序遍历，H为F的左子节点。在二叉树中，求后序遍历，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。则该二叉树的后序遍历是DGEBHFCA。扩展资料：非常感谢您的耐心观看，如有帮助请采纳，祝生活愉快！谢谢！

数据结构 线索二叉树 中序遍历 高手们帮忙看看哪错了啊

你的那个线索化二叉树中的pre参数应该是全局的，想想是吗？下面是用c++写的代码，希望对你有用：树结点文件：#ifndef THREADTREENODE_H#define THREADTREENODE_Htemplate《class T》class ThreadTreeNode{public:T data;int lTag;int rTag;ThreadTreeNode《T》 * L_child;ThreadTreeNode《T》 * R_child;ThreadTreeNode(){lTag=0;rTag=0;L_child=NULL;R_child=NULL;}};#endif穿线二叉树的文件：#ifndef THREADTREE_H#define THREADTREE_H#include《iostream》#include《stack》#include《fstream》#include"ThreadTreeNode.h"#include"node_infor.h"using namespace std;template《class T》class ThreadTree{public:ThreadTree();~ThreadTree();void InThread();void InThread(ThreadTreeNode《T》 * root,ThreadTreeNode《T》 * & pre);void In_order();void InThread_test();ThreadTreeNode《T》 * FindNext_pre(ThreadTreeNode《T》 * pointer);ThreadTreeNode《T》 * Find_Node(const T & ele);void Find_Test();void Insert_Node(ThreadTreeNode《T》 * pointer,ThreadTreeNode《T》 * newpointer);void Insert_Test();ThreadTreeNode《T》 * FindPre_post(ThreadTreeNode《T》 * pointer);void Pre_order();//void Post_order();ThreadTreeNode《T》 * FindIn_pre(ThreadTreeNode《T》 * pointer);private:void creat_tree();void dele_tree(ThreadTreeNode《T》 * root);void visit(ThreadTreeNode《T》* pointer);ThreadTreeNode《T》 * root;node_infor《T》 store_infor;int count;};template《class T》ThreadTree《T》::ThreadTree(){cout《《"前序构造二叉树！"《《endl;count=0;ifstream in("store_infor.txt");while(!in.eof()){in》》store_infor.data;in》》store_infor.ltag;in》》store_infor.rtag;count++;}in.close();creat_tree();}template《class T》void ThreadTree《T》::creat_tree(){ThreadTreeNode《T》 * pointer;ThreadTreeNode《T》 * temp_pointer;stack《ThreadTreeNode《T》*》 creat_help;root=new ThreadTreeNode《T》;pointer=root;for(int i=0;i《count-1;i++){pointer-》data=store_infor.data;if(store_infor.rtag==1){creat_help.push(pointer);}temp_pointer=new ThreadTreeNode《T》;if(store_infor.ltag==1){pointer-》L_child=temp_pointer;}else{pointer=creat_help.top();creat_help.pop();pointer-》R_child=temp_pointer;}pointer=temp_pointer;}pointer-》data=store_infor.data;}template《class T》void ThreadTree《T》::visit(ThreadTreeNode《T》* pointer){cout《《pointer-》data《《" ";}template《class T》void ThreadTree《T》::InThread(ThreadTreeNode《T》 * root,ThreadTreeNode《T》 * & pre){if(root!=NULL){InThread(root-》L_child,pre);}else{return;}if(root-》L_child==NULL && pre){root-》lTag=1;root-》L_child=pre;}if(pre && pre-》R_child==NULL){pre-》rTag=1;pre-》R_child=root;}pre=root;InThread(root-》R_child,pre);}template《class T》void ThreadTree《T》::InThread(){ThreadTreeNode《T》 * pointer=root;ThreadTreeNode《T》 * pre_pointer=NULL;stack《ThreadTreeNode《T》*》 InThread_help;while(true){while(pointer) { InThread_help.push(pointer); pointer=pointer-》L_child; }if(InThread_help.empty())return;pointer=InThread_help.top();InThread_help.pop();if(pointer-》L_child==NULL && pre_pointer){pointer-》lTag=1;pointer-》L_child=pre_pointer;}if(pre_pointer && pre_pointer-》R_child==NULL){pre_pointer-》rTag=1;pre_pointer-》R_child=pointer;}pre_pointer=pointer;pointer=pointer-》R_child;} }template《class T》void ThreadTree《T》::InThread_test(){ThreadTreeNode《T》 * pre=NULL;InThread(root,pre);//InThread();}template《class T》ThreadTreeNode《T》 * ThreadTree《T》::FindNext_pre(ThreadTreeNode《T》 * pointer){if(pointer-》lTag==0 && pointer-》L_child!=NULL){return pointer-》L_child;}while(pointer-》rTag==1){pointer=pointer-》R_child;}return pointer-》R_child;}template《class T》ThreadTreeNode《T》 * ThreadTree《T》::Find_Node(const T & ele){ThreadTreeNode《T》 * pointer=root;while(pointer-》L_child){pointer=pointer-》L_child;}while(true){if(pointer-》data==ele){return pointer;}else if(pointer-》R_child==NULL){return NULL;}else if(pointer-》rTag==1){pointer=pointer-》R_child;}else{pointer=pointer-》R_child;while(pointer-》lTag==0){pointer=pointer-》L_child;}}}}template《class T》ThreadTreeNode《T》 * ThreadTree《T》::FindPre_post(ThreadTreeNode《T》 * pointer){if(pointer-》rTag==0 && pointer-》R_child!=NULL){return pointer-》R_child;}else if(pointer-》lTag==0){return pointer-》L_child;}else{pointer=pointer-》L_child;while(pointer-》lTag==1){pointer=pointer-》L_child;}return pointer;}}template《class T》ThreadTreeNode《T》 * ThreadTree《T》::FindIn_pre(ThreadTreeNode《T》 * pointer){if(pointer-》lTag==1){return pointer-》L_child;}if(pointer-》L_child==NULL){return NULL;}pointer=pointer-》L_child;while(pointer-》rTag==0){pointer=pointer-》R_child;}return pointer;}template《class T》void ThreadTree《T》::Find_Test(){cout《《"查找前序的后继！"《《endl;cout《《"请输入元素："《《endl;T ele;cin》》ele;if(ThreadTreeNode《T》 * pointer=FindNext_pre(Find_Node(ele))){visit(pointer);cout《《endl;}else{cout《《"无此相关项！"《《endl;}cout《《"查找后序下的前继"《《endl;cout《《"请输入元素："《《endl;cin》》ele;if(ThreadTreeNode《T》 * pointer=FindPre_post(Find_Node(ele))){visit(pointer);cout《《endl;}else{cout《《"无此相关项！"《《endl;}cout《《"查找中序下的前继！"《《endl;cout《《"请输入元素："《《endl;cin》》ele;if(ThreadTreeNode《T》 * pointer=FindIn_pre(Find_Node(ele))){visit(pointer);cout《《endl;}else{cout《《"无此相关项！"《《endl;}}template《class T》void ThreadTree《T》::Pre_order(){if(root==NULL){return;}cout《《"前序周游："《《endl;ThreadTreeNode《T》 * pointer=root;while(true){while(pointer-》lTag==0){visit(pointer);if(pointer-》L_child==NULL){break;}pointer=pointer-》L_child;}if(pointer-》lTag==1) visit(pointer);if(pointer-》R_child==NULL){cout《《endl;return;}while(pointer-》rTag==1){pointer=pointer-》R_child;}pointer=pointer-》R_child;}}//template《class T》/*void ThreadTree《T》::Post_order(){if(root==NULL)return;cout《《"后序周游："《《endl;ThreadTreeNode《T》 * pointer=root;while(true){while(pointer-》lTag==0){if(pointer-》L_child==NULL)break;pointer=pointer-》L_child;}if(pointer-》rTag==1 || pointer-》R_child==NULL){visit(pointer);if(pointer-》rTag==1)pointer=pointer-》R_child;}pointer}}*/template《class T》void ThreadTree《T》::In_order(){if(root==NULL)return;cout《《"中序周游："《《endl;ThreadTreeNode《T》 * pointer=root;while(pointer-》L_child!=NULL){pointer=pointer-》L_child;}while(true){visit(pointer);if(pointer-》R_child==NULL){cout《《endl;return;}if(pointer-》rTag==1){pointer=pointer-》R_child;}else{pointer=pointer-》R_child;while(pointer-》lTag==0){pointer=pointer-》L_child;}}}}template《class T》void ThreadTree《T》::Insert_Node(ThreadTreeNode《T》 * pointer,ThreadTreeNode《T》 * newpointer){ThreadTreeNode《T》 * temp_pointer;if(pointer-》R_child==NULL){temp_pointer=NULL;}else if(pointer-》rTag==1){temp_pointer=pointer-》R_child;}else{temp_pointer=pointer-》R_child;while(temp_pointer-》lTag==0){temp_pointer=temp_pointer-》L_child;}}/*pointer-》R_child=newpointer;newpointer-》R_child=pointer-》R_child;newpointer-》lTag=1;newpointer-》L_child=pointer;newpointer-》rTag=pointer-》rTag;pointer-》rTag=0;*/if(temp_pointer!=NULL && temp_pointer-》lTag==1){temp_pointer-》L_child=newpointer;}newpointer-》lTag=1;newpointer-》L_child=pointer;newpointer-》R_child=pointer-》R_child;newpointer-》rTag=pointer-》rTag;pointer-》R_child=newpointer;pointer-》rTag=0;}template《class T》void ThreadTree《T》::Insert_Test(){cout《《"结点插入，位置是指定结点在中序下的后继！"《《endl;cout《《"请输入指定结点的元素："《《endl;T ele;cin》》ele;cout《《"请输入新结点的元素："《《endl;T new_ele;cin》》new_ele;ThreadTreeNode《T》 * newpointer=new ThreadTreeNode《T》;newpointer-》data=new_ele;Insert_Node(Find_Node(ele),newpointer);}template《class T》void ThreadTree《T》::dele_tree(ThreadTreeNode《T》 * root){if(root!=NULL && root-》lTag==0 && root-》rTag==0){dele_tree(root-》L_child);dele_tree(root-》R_child);delete root;}}template《class T》ThreadTree《T》::~ThreadTree(){dele_tree(root);}#endif

建立中序线索二叉树，并且中序遍历； 2. 求中序线索二叉树上已知结点中序的前驱和后继

．在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。bithrtreeinpostpre(bithrtreet,p)//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q{bithrtreeq;if(p-》rtag==0)q=p-》rchild;//若p有右子女，则右子女是其后序前驱elseif(p-》ltag==0)q=p-》lchild;//若p无右子女而有左子女，左子女是其后序前驱。elseif(p-》lchild==null)q=null;//p是中序序列第一结点，无后序前驱else//顺左线索向上找p的祖先，若存在，再找祖先的左子女{while(p-》ltag==1&&p-》lchild!=null)p=p-》lchild;if(p-》ltag==0)q=p-》lchild;//p结点的祖先的左子女是其后序前驱elseq=null;//仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱}return(q);}//结束inpostpre

简述中序线索二叉树的构造方法

直接利用递归的中序遍历算法来完成，中间需要一个指向前驱结点的指针，初值为空1、递归中序遍历左子树2、访问某个结点时，同时修改前驱指向自己（如果有）和自己指向前驱（如果有）的线索与标志完了后，前驱移动指向当前结点3、递归中序遍历右子树

给定如图所示二叉树T，请画出与其对应的中序线索二叉树

根据中顺遍历方法  先范访问左子树  结点  右子树   ：

中序遍历： 55 40 25  60 28  08  33 54

如图：

  满意的话  记得给分哦~