5)二叉树[2]二叉树中序线索化

  1 #include "iostream"
  2 #include "stdlib.h"
  3 using namespace std;
  4 
  5 typedef char type;
  6 struct bnode{
  7     type data;
  8     bnode *lchild,*rchild;
  9     int rtag,ltag;
 10 };
 11 
 12 const int lrtag = 0;
 13 class thbtree{
 14 public:
 15     thbtree();//初始化
 16     ~thbtree();
 17     void create_thbtree(bnode *&T);//建立二叉树
 18     void inorder(bnode *T);//先序遍历
 19     bnode *in_thread(bnode *&T);
 20     void inthread(bnode *p,bnode *&pre);
 21 
 22 private:
 23     int count;//元素个数统计
 24 };
 25 
 26 thbtree::thbtree()//初始化
 27 {
 28     count = 0;
 29 }
 30 
 31 void thbtree::create_thbtree(bnode *&T)//建立二叉树
 32 {
 33     type ch;
 34     cin>>ch;
 35     if(ch=='.')T=NULL;
 36     else {
 37         T = new bnode;
 38         T->data = ch;
 39         T->ltag = lrtag;
 40         T->rtag = lrtag;
 41         count++;
 42         create_thbtree(T->lchild);
 43         create_thbtree(T->rchild);
 44     }
 45 }
 46 
 47 void thbtree::inthread(bnode *p,bnode *&pre)
 48 {
 49     if(p)
 50     {
 51         inthread(p->lchild,pre);//左子树线索化
 52         if(!p->lchild)//如果p的左子树为空，给P点加前驱线索
 53         {
 54             p->ltag = 1;
 55             p->lchild = pre;
 56         }else{
 57             p->ltag = 0;
 58         }
 59         if(pre && !pre->rchild)
 60         {
 61             pre->rtag = 1;
 62             pre->rchild = p;
 63         }
 64         pre = p;
 65         inthread(p->rchild,pre);//右子树线索化
 66     }
 67 }
 68 bnode *thbtree::in_thread(bnode *&T)
 69 {
 70     bnode *pre = NULL;
 71     bnode *head;
 72     head =  new bnode;
 73     head->ltag = 0;
 74     head->rtag = 1;
 75     head->lchild = head;
 76     if(!T)
 77     {
 78         head->lchild = head;
 79     }else{
 80         head->lchild = T;
 81         pre = head;
 82         inthread(T,pre);
 83         pre->rchild = head;
 84         pre->rtag=1;
 85         head->rchild = pre;
 86     }
 87     T =head;
 88     return head;
 89 }
 90 
 91 
 92 void thbtree::inorder(bnode*T)//中序遍历
 93 {
 94     bnode *p;
 95     p = T->lchild;
 96     while(p!=T)
 97     {
 98         while(p->ltag==0)
 99         {
100             p=p->lchild;
101         }
102         cout<<p->data<<" ";
103         while(p->rtag==1&&p->rchild!=T)
104         {
105             p = p->rchild;
106             cout<<p->data<<" ";
107         }
108         p = p->rchild;
109     }
110 }
111 
112 thbtree::~thbtree(){}
113 
114 int main()
115 {
116     thbtree Tree;
117     bnode *T;
118     cout<<"Create Tree:";
119     Tree.create_thbtree(T);
120     cout<<"Tree finished!"<<endl;
121     Tree.in_thread(T);
122     cout<<"INorder Tree:";
123     Tree.inorder(T);
124     cout<<endl;
125     return 0;
126 }