建立中序线索二叉树

  1 #include <iostream>
  2 #include <stdio.h>
  3 
  4 using namespace std;
  5 
  6 typedef char TElemType;
  7 enum PointerTag{ Link,Thread };//Link == 0 :指针，Thread == 1 :线索
  8 typedef struct BiThrNode
  9 {
 10     TElemType data;
 11     struct BiThrNode *lchild,*rchild;
 12     PointerTag LTag,RTag;
 13 }BiThrNode,*BiThrPtr;
 14 
 15 BiThrPtr pre=NULL;//定义全局变量
 16 
 17 //默认按前序遍历的顺序输入，尾结点用#表示
 18 int Create_BiThrTree(BiThrPtr& T)
 19 {
 20     TElemType c;
 21     //cout << "请输入当前节点元素值：" << endl;
 22     cin>>c;
 23     if(c == '#') T=NULL;
 24     else
 25     {
 26         T = new BiThrNode;
 27         T->data=c;
 28         T->LTag=Link;
 29         T->RTag=Link;
 30         Create_BiThrTree(T->lchild);
 31         Create_BiThrTree(T->rchild);
 32     }
 33     return 0;
 34 }
 35 
 36 //中序遍历输入各节点
 37 int InOrderDisplay(BiThrPtr& T)
 38 {
 39     if(T)
 40     {
 41         InOrderDisplay(T->lchild);
 42         cout << T->data <<"  ";
 43         InOrderDisplay(T->rchild);
 44     }
 45     return 0;
 46 }
 47 
 48 
 49 int InOrderTraverse(BiThrPtr& T)
 50 {
 51     extern BiThrPtr pre;//声明全局变量
 52     if(T)
 53     {
 54         InOrderTraverse(T->lchild);
 55         if(!T->lchild)
 56         {
 57             T->LTag = Thread;
 58             T->lchild = pre;
 59         }
 60         if(!pre->rchild)
 61         {
 62             pre->RTag = Thread;
 63             pre->rchild = T;
 64         }
 65         pre = T;
 66         InOrderTraverse(T->rchild);
 67     }
 68     return 0;
 69 }
 70 
 71 int InOrderThreading(BiThrPtr p,BiThrPtr& T)
 72 {
 73     p = new BiThrNode;//额外添加的头结点
 74     p->data = '#';
 75     p->LTag = Link;
 76     p->RTag = Thread;
 77     p->rchild = p;
 78     if(!T)
 79     {
 80         p->lchild = p;
 81     }
 82     else
 83     {
 84         p->lchild = T;
 85         pre = p;
 86         InOrderTraverse(T);
 87         pre->RTag = Thread;
 88         pre->rchild = p;
 89         p->rchild = pre;
 90     }
 91     return 0;
 92 }
 93 
 94 int main()
 95 {
 96     freopen( "input.txt", "r", stdin );//从input.txt中读取输入数据
 97     BiThrPtr T=NULL,p=NULL;
 98     Create_BiThrTree(T);//前序遍历创建二叉树
 99     InOrderDisplay(T);
100     InOrderThreading(p,T);
101     fclose(stdin);
102     return 0;
103 }
测试数据如下（从txt中读取）：ABC##D##E#F##
思路借鉴小甲鱼视频：http://pan.baidu.com/s/1nv187e5
最上面那个节点是额外添加的头结点
只有0和1的世界是简单的