数据结构 二叉树 索引链表 及其索引话 输出
#include <iostream>#include <string.h>using namespace std;class tree{public:char c;tree *lchild,*rchild;int ltag,rtag;};char c;tree *pre;int main(){void build(tree * &p);void inthread(tree* p,tree* &list);void Inorder(tree* p,tree* list);tree *head,*list;build(head);inthread(head,list);Inorder(head,list);cout<<endl;return 0;}void build(tree* &p){cin>>c;if(c=='$'){p=NULL;}else{p=new(tree);p->c=c;p->ltag=0;p->rtag=0;build(p->lchild);build(p->rchild);}}void inorderthread(tree *p){if(p){inorderthread(p->lchild);if(!p->lchild){p->ltag=1; p->lchild=pre;}if(!pre->rchild){pre->rtag=1;pre->rchild=p;}pre=p;inorderthread(p->rchild);}}void inthread(tree* p,tree* &list){list=new(tree);list->ltag=0; list->rtag=1;list->rchild=list;if(p==NULL){list->lchild=list;}else{list->lchild=p; pre=list;inorderthread(p);pre->rchild=list; pre->rtag=1;list->rchild=pre;}}void Inorder(tree* p,tree *list){while(p!=list){while(p->ltag==0){p=p->lchild;}cout<<p->c;while(p->rtag&&p->rchild!=list){p=p->rchild;cout<<p->c;}p=p->rchild;}}