二叉树的中序序列怎么看,前序线索二叉树

任务 建立一颗中序线索二叉树;分别从第-一个结点和最后一个结点出发输出中序遍历结果;输出某结点的前趋和后继结点 思路： 线索二叉树结构类型 typedef struct treenode{ char data; struct treenode *lchild,*rchild; int ltag,rtag; //记录指针与指向孩子结点还是后继或前驱 tag为0表示孩子，tag为1表示线索 }treenode,*tree; 先建立一个二叉树 //使用先序建立二叉树void buildtree(tree &t){ char ch; ch = getchar(); if(ch=='#') t = NULL; else{ t = (treenode *)malloc(sizeof(treenode)); t->data = ch; t->lchild = NULL; t->rchild = NULL; t->ltag = 0; t->rtag = 0; buildtree(t->lchild); buildtree(t->rchild); }} 二叉树线索化 void inThreadTree(treenode *t,treenode** pre){ if (t)//判断根节点是否存在 {//先左孩子 inThreadTree(t->lchild,pre);//操作根节点 //进行操作 if (t->lchild==NULL) { t->ltag = 1; t->lchild = *pre; } if (*pre !=NULL && (*pre)->rchild == NULL) { (*pre)->rtag = 1; (*pre)->rchild = t; } *pre = t; ///最后右孩子 inThreadTree(t->rchild,pre); } } 获得第一个结点 treenode *getFirst(treenode *t){ while (t->ltag == 0) { t = t->lchild; } return t; } 获得第最后一个结点 treenode* getLast(treenode* t){ while(t->rtag == 0){t = t->rchild;} return t;} 获得后继结点 treenode* getNext(treenode *t){ if (t->rtag == 1) { return t->rchild; }else{ return getFirst(t->rchild); } } 获得前驱 treenode* getPre(treenode *t){ if (t->ltag == 0) { return getLast(t->lchild); }else{ return t->lchild; } } 输出 输出函数（//输出当前结点及其前驱后继） void PrintNode(treenode* node){ if(node->lchild == NULL){printf("结点前驱：NULL ");}else{if(node->ltag == 1)printf("结点前驱：%c ", node->lchild->data);else{treenode *p1;p1 = getPre(node);printf("结点前驱: %c ", p1->data);}}printf("访问结点：%c ", node->data);if(NULL == node->rchild){printf("结点后继：NULLn");}else{if(node->rtag == 1)printf("结点后继：%cn", node->rchild->data);else{treenode *p;p = getNext(node);printf("结点后继: %cn", p->data);}}} 顺序输出（从第一个结点开始中序输出） //顺序输出void outOrder(treenode* t){ for (treenode* node = getFirst(t); node != NULL; node = getNext(node)) { PrintNode(node); printf("%c n",node->data); }} 最后一个结点遍历 //逆序输出(最后一个结点)void outReverse(treenode* t){ for (treenode* node = getLast(t); node != NULL; node = getPre(node)) { PrintNode(node); printf("%c n",node->data); }} 完整代码 #include <iostream>using namespace std;#define MAX 20 typedef struct treenode{ char data; struct treenode *lchild,*rchild; int ltag,rtag; }treenode,*tree; void buildtree(tree &t){ char ch; ch = getchar(); if(ch=='#') t = NULL; else{ t = (treenode *)malloc(sizeof(treenode)); t->data = ch; t->lchild = NULL; t->rchild = NULL; t->ltag = 0; t->rtag = 0; buildtree(t->lchild); buildtree(t->rchild); }}void inThreadTree(treenode *t,treenode** pre){ if (t) { inThreadTree(t->lchild,pre); //进行操作 if (t->lchild==NULL) { t->ltag = 1; t->lchild = *pre; } if (*pre !=NULL && (*pre)->rchild == NULL) { (*pre)->rtag = 1; (*pre)->rchild = t; } *pre = t; inThreadTree(t->rchild,pre); } }treenode *getFirst(treenode *t){ while (t->ltag == 0) { t = t->lchild; } return t; }treenode* getNext(treenode *t){ if (t->rtag == 1) { return t->rchild; }else{ return getFirst(t->rchild); } }treenode* getLast(treenode* t){ while(t->rtag == 0){t = t->rchild;} return t;}treenode* getPre(treenode *t){ if (t->ltag == 0) { return getLast(t->lchild); }else{ return t->lchild; } }void PrintNode(treenode* node){ if(node->lchild == NULL){printf("结点前驱：NULL ");}else{if(node->ltag == 1)printf("结点前驱：%c ", node->lchild->data);else{treenode *p1;p1 = getPre(node);printf("结点前驱: %c ", p1->data);}}printf("访问结点：%c ", node->data);if(NULL == node->rchild){printf("结点后继：NULLn");}else{if(node->rtag == 1)printf("结点后继：%cn", node->rchild->data);else{treenode *p;p = getNext(node);printf("结点后继: %cn", p->data);}}}//顺序输出void outOrder(treenode* t){ for (treenode* node = getFirst(t); node != NULL; node = getNext(node)) { PrintNode(node); printf("%c n",node->data); }}//逆序输出(最后一个结点)void outReverse(treenode* t){ for (treenode* node = getLast(t); node != NULL; node = getPre(node)) { PrintNode(node); printf("%c n",node->data); }}int main(){ tree t; treenode* pre = NULL; buildtree(t); inThreadTree(t,&pre); pre->rtag = 1; pre->rchild = NULL; // outOrder(t); outReverse(t); cout<<endl; }