线索二叉树

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<malloc.h>
  6 using namespace std;
  7 
  8 typedef char ElemType; 
  9 
 10 //线索存储标志位
 11 //Link(0)表示指向左右孩子的指针
 12 //Thread(1)表示指向前驱后继的线索 
 13 typedef enum {
 14     Link,Thread
 15 }PointerTag;
 16 
 17 typedef struct BiThrNode{
 18     char data;
 19     struct BiThrNode *lchild,*rchild;
 20     PointerTag ltag;
 21     PointerTag rtag;
 22 }BiThrNode,*BiThrTree;
 23 
 24 //全局变零，始终指向刚刚访问过的结点
 25 BiThrTree pre;
 26 
 27 //创建一颗二叉树，用户遵照前序遍历输入数据
 28 void CreateBiThrTree(BiThrTree &T){
 29     char c;
 30     scanf("%c",&c);
 31     if(' ' == c)
 32         T = NULL;
 33     else{
 34         T = (BiThrNode *)malloc(sizeof(BiThrNode));
 35         T->data = c;
 36         T->ltag = Link;
 37         T->rtag = Link;
 38         CreateBiThrTree(T->lchild);
 39         CreateBiThrTree(T->rchild);
 40     }
 41 } 
 42 
 43 //中序遍历线索化
 44 void InThreading(BiThrTree &T){
 45     if(T){
 46         InThreading(T->lchild);//递归左孩子线索化
 47         if(!T->lchild){//如果该结点没有左孩子，设置ltag为Thread，并把lchid指向上一个刚刚访问的结点 
 48             T->ltag = Thread;
 49             T->lchild = pre;
 50         }
 51         if(!pre->rchild){
 52             pre->rtag = Thread;
 53             pre->rchild = T; 
 54         } 
 55         pre = T;
 56         InThreading(T->rchild);//递归右孩子线索化 
 57     }
 58 } 
 59 
 60 void InOrderThreading(BiThrTree &p,BiThrTree &T){
 61     p = (BiThrNode *)malloc(sizeof(BiThrNode));
 62     p->ltag = Link;
 63     p->rtag = Thread;
 64     p->rchild = p;
 65     if(!T)
 66         p->lchild = p;
 67     else{
 68         p->lchild = T;
 69         pre = p;
 70         InThreading(T);
 71         pre->rchild = p;
 72         pre->rtag = Thread;
 73         p->rchild = pre;
 74     }
 75 }
 76 
 77 void visit(char c){
 78     printf("%c",c);
 79 }
 80 
 81 //中序遍历，非递归
 82 void InOrderTraverse(BiThrTree T){
 83     BiThrTree p;
 84     p = T->lchild;
 85     while(p!=T){
 86         while(p->ltag==Link)
 87             p = p->lchild;
 88         visit(p->data);
 89         while(p->rtag==Thread&&p->rchild!=T){
 90             p = p->rchild;
 91             visit(p->data);
 92         }
 93         p = p->rchild;
 94     }
 95 } 
 96 
 97 int main(){
 98     BiThrTree p,T = NULL;
 99     CreateBiThrTree(T);
100     InOrderThreading(p,T);
101     printf("中序遍历输出结果为：");
102     InOrderTraverse(p); 
103     printf("
");
104     return 0;
105 }