c++线索二叉树源代码

#include<iostream.h> #include <malloc.h> #include <stdio.h> typedef char TElemType; typedef enum PointerTag{Link, Thread};//link==0指针，thread==1线索 typedef struct BiThNode { TElemType data; struct BiThNode *lchild,*rchild;//左右孩子 PointerTag LTag, RTag;//左右标志 }BiThNode,*BitTree; char*a=new char[]; int i=0; BiThNode *pre;//定义指针始终指向刚刚遍历的节点 int CreateBiTree(BitTree &T)//先序建立二叉树 { TElemType a; if ((a=getchar())==' ')//当输入的字符为空的时候 T=NULL;//指针指空 else { if (!(T=(BiThNode *)malloc(sizeof(BiThNode))))//否则为其分配空间 return 0; T->data=a;//将字符赋值到数据域 CreateBiTree(T->lchild);//创建左子树 CreateBiTree(T->rchild);//创建右子树 } return 0; } void InThreading(BitTree p) { if (p) { InThreading(p->lchild); if (!p->lchild) { p->LTag=Thread; p->lchild=pre; cout<<p->data<<'\t'; a[i]=p->data; i++; } if(!pre->rchild) { pre->RTag=Thread; pre->rchild=p; cout<<p->data<<'\t'; a[i]=p->data; i++; } pre=p; InThreading(p->rchild); } } int InOrderTheading(BitTree &head,BitTree T)//中序遍历并线索化 { if(!(head=(BiThNode*)malloc(sizeof(BiThNode))))//分配指向头结点的节点 return 0; head->LTag=Link;//左标志指0 head->RTag=Thread;//右标志指1 head->rchild=head;//右指针指向 head->data='#'; if(!T)//如果树空 head->lchild=head;//指向头节点左针指向它本身 else//不空 { pre=head;//则将头结点的前驱保存在指针pre中 InThreading(T);//将以T为根的树线索化 head->lchild=T;//做指针指向头节点 pre->rchild=head;//pre指向他的前驱 pre->RTag=Thread;//pre指针的右标志为1 head->rchild=pre; } return 0; } void main() { char a1,a0; int j; BitTree T,head; cout<<"建立二叉树"<<endl; CreateBiTree(T); InOrderTheading(head, T); cout<<endl; while(a1!=0) { cout<<"请输入要查找的元素"<<endl; cin>>a0; for (j=0;j<=i&&a0!=a[j];j++); if (j>i) cout<<"没有此元素"<<endl; else { if (j==i) cout<<a0<<"的前驱为："<<a[j-1]<<'\t'<<a0<<"的后继为："<<a[0]<<endl; if (j<i) cout<<a0<<"的前驱为："<<a[j-1]<<'\t'<<a0<<"的后继为："<<a[j+1]<<endl; } cout<<"输入'0'结束,继续请按任意键"<<endl; } cout<<endl; }