//哎。。发现 写一段代码 需要的时间都要好久啊 #include<stdio.h> #include<stdlib.h> #define ERROR 0 #define OK 1 typedef int Status; typedef struct BiTree{ int id; //二叉树节点的标识符 用来查找用的 int data; int LTag,RTag; //标志 左子树 右子树 0代表线索 1代表指针 struct BiTree *LChild; //left child struct BiTree *RChild; //right child } BiTree,*PBiTree; Status InitBiTree(PBiTree *PBT,int data) { if(!((*PBT)=(PBiTree)malloc(sizeof(BiTree)))) return ERROR; (*PBT)->id=1; (*PBT)->data=data; (*PBT)->LChild=NULL; (*PBT)->RChild=NULL; //初始化 return OK; } Status GetBiTreeNodeById(PBiTree BTO,PBiTree *PBTR,int id) //receive { int stat1=ERROR,stat2=ERROR; if(BTO->id==id) { *PBTR=BTO; return OK;} //注意:BTR=BTO 这是没有意义的事情 如果用 *BTR=*BTO; 报告内存不可写 else{ if(BTO->LChild) {stat1=GetBiTreeNodeById(BTO->LChild,PBTR,id);} if(BTO->RChild) {stat2=GetBiTreeNodeById(BTO->RChild,PBTR,id);} return stat1 || stat2; //就算有一个有找到 也算成功 } } Status InsertBiTree(PBiTree BT,int fid,char lr,int sid,int data) {//要被插入的树 该树下的节点id下插入 成为它的左孩子或者右孩子 l左 r右 插入者的id 数据 //如果在该位置上已经存在 节点 则把原来的 替换 PBiTree BTR,BTT; if(GetBiTreeNodeById(BT,&BTR,fid)) //找到父树 { switch(lr) { case 'l': //left if(BTR->LChild) { BTR->LChild->id=sid; BTR->LChild->data=data; }else{ if(!(BTT=(PBiTree)malloc(sizeof(BiTree)))) return ERROR; BTR->LChild=BTT; BTT->id=sid; BTT->data=data; BTT->LChild=NULL; BTT->RChild=NULL; } break; case 'r': //right if(BTR->RChild) { BTR->RChild->id=sid; BTR->RChild->data=data; }else{ if(!(BTT=(PBiTree)malloc(sizeof(BiTree)))) return ERROR; BTR->RChild=BTT; BTT->id=sid; BTT->data=data; BTT->LChild=NULL; BTT->RChild=NULL; } break; } }else{ return ERROR;} return OK; } Status PrintBiTree(const BiTree *PB) //做好之后 做一下扩充 给它传一个 函数 来调用 打印 { if(!PB) return ERROR; //printf(" id:%d data:%d ",PB->id,PB->data); //先序 从根节点起 先左完 再右 if(PB->LChild) {PrintBiTree(PB->LChild);} printf(" id:%d data:%d ",PB->id,PB->data); if(PB->RChild) {PrintBiTree(PB->RChild);} // printf(" id:%d data:%d ",PB->id,PB->data); return OK; } Status DestoryBiTree(BiTree *PB) { if(PB->LChild) {DestoryBiTree(PB->LChild);} if(PB->RChild) {DestoryBiTree(PB->RChild);} free(PB); return OK; } //======================栈操作 typedef struct StackNode{ //栈遍历 BiTree *TreeNode; struct StackNode *next; }NStack,*PStack; Status InitStack(PStack *P) { if(!((*P)=(PStack)malloc(sizeof(NStack)))) return ERROR; (*P)->TreeNode=NULL; (*P)->next=NULL; return OK; } Status Push(PStack S,BiTree *PB) { PStack st; if(!((st)=(PStack)malloc(sizeof(NStack)))) return ERROR; st->TreeNode=PB; st->next=S->next; S->next=st; return OK; } Status Pop(PStack S,PStack *P) { (*P)=S->next; if(*P) {S->next=(*P)->next;} return OK; } Status GetHead(PStack S,PStack *H) { (*H)=S->next; return OK; } int StackEmpty(const PStack S) { if(S->next==NULL) return 1; return 0; } Status TraverseByStack(const BiTree *PB) //栈遍历 中序 遍历 { PStack S=(PStack)malloc(sizeof(NStack)); PStack H,St=S; InitStack(S); Push(S,PB); while(!StackEmpty(S)) { while(GetHead(S,&H) && H->TreeNode) //一路向左 {Push(S,H->TreeNode->LChild);} Pop(S,&H); if(!StackEmpty(S)) { free(H); //释放Pop所带来的 残余 Pop(S,&H); //要Pop两次 因为 使它上上节点 指向它上节点的下节点 故抛弃上节点 Push(S,H->TreeNode->RChild); printf(" id:%d data:%d ",H->TreeNode->id,H->TreeNode->data); //打印上节点 } }//关键 就是退两步 让它退的第二步栈的下一个节点 指向它退第一步的栈的树节点的右节点所构成的栈节点 free(St); } //=================== 栈操作 end //===================线索二叉树 PBiTree pre; //前一个指针 Status Threading(PBiTree B); Status ToThread(PBiTree B,PBiTree *P) // 进行线索化 中序 { if(!((*P)=(PBiTree)malloc(sizeof(BiTree)))) return ERROR; //头节点 (*P)->RChild=(*P); if(!B) { (*P)->LChild=(*P); } //树空 则另 (*P)的左子树 回指 else{ (*P)->LChild=B; pre=(*P); //pre是为前一个节点 Threading(B); //把 头节点的右子树 指向二叉树 中序遍历 的最后一个节点 (*P)->RChild=pre; //此时的 pre指向的是 树的最后一个节点 pre->RChild=(*P); } return OK; } Status Threading(PBiTree B) //中序 遍历 线索二叉 { if(B->LChild) { B->LTag=1; Threading(B->LChild);// 一直走到左边的底部 }else{ B->LTag=0; // 在左边的底部时 就为线索 B->LChild=pre; } if(! pre->RChild) //这一步 需要多看 在上面递归退出的时候 全局变量pre的值被改变 { pre->RTag=0; pre->RChild=B; } pre=B; //递归退出时 发挥功用 if(B->RChild) { B->RTag=1; Threading(B->RChild); //线索 右子树 }else{ B->RTag=0; //如果树就只有一个节点 的情况 } return OK; } Status TraverseByThread(const BiTree *PB) //线索二叉遍历 中序 { BiTree *Pa,*Pb=NULL; Pa=PB->LChild; while(1) { for(Pb=Pa;Pb->LTag;Pb=Pb->LChild); printf(" id:%d data:%d ",Pb->id,Pb->data); if(! Pb->RTag) //线索 { Pb=Pb->RChild; if(Pb == PB) break; //回到 表头 则退出 printf(" id:%d data:%d ",Pb->id,Pb->data); } Pa=Pb->RChild; } return OK; } int main() { PBiTree PBT,PBA; InitBiTree(&PBT,11); InsertBiTree(PBT,1,'l',2,22); InsertBiTree(PBT,1,'r',3,23); InsertBiTree(PBT,2,'l',4,32); InsertBiTree(PBT,2,'r',5,33); InsertBiTree(PBT,3,'l',6,33); InsertBiTree(PBT,3,'r',7,34); InsertBiTree(PBT,4,'l',8,44); InsertBiTree(PBT,4,'r',9,45); InsertBiTree(PBT,5,'l',10,55); InsertBiTree(PBT,5,'r',11,56); printf("print by 递归:\n"); PrintBiTree(PBT); printf("\n\n"); printf("print by Stack:\n"); TraverseByStack(PBT); printf("\n\n"); printf("print by Thread:\n"); ToThread(PBT,&PBA); TraverseByThread(PBA); DestoryBiTree(PBT); }