线索二叉树

biThrTree.h

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<malloc.h>
  4 
  5 typedef int TElemType;
  6 typedef enum PointerTag{Link,Thread};
  7 //线索二叉树
  8 typedef struct BiThrNode
  9 {
 10     TElemType data;
 11     struct BiThrNode *lchild,*rchild;
 12     PointerTag LTag,RTag;
 13 }BiThrNode, *BiThrTree;
 14 
 15 BiThrTree pre;//辅助线索化二叉树的变量
 16 
 17 typedef enum Status{ERROR,OK};
 18 
 19 Status visit(TElemType data)
 20 {
 21     printf("%d ",data);
 22     return OK;
 23 }
 24 
 25 Status InOrderTraverseThr(BiThrTree T,Status (*visit)(TElemType e))//中序遍历中序线索二叉树
 26 {
 27     BiThrTree p = T->lchild;
 28     while(p != T)
 29     {
 30         while(p->LTag == Link)
 31         {
 32             p = p->lchild;
 33         }
 34         if(!visit(p->data))
 35         {
 36             return ERROR;
 37         }
 38         while(p->RTag == Thread && p->rchild != T)
 39         {
 40             p = p->rchild;
 41             visit(p->data);
 42         }
 43         p = p->rchild;
 44     }
 45     return OK;
 46 }
 47 
 48 void InThreading(BiThrTree p)//中序遍历线索化过程
 49 {
 50     if(p)
 51     {
 52         InThreading(p->lchild);
 53         if(!pre->rchild)
 54         {
 55             pre->RTag = Thread;
 56             pre->rchild = p;
 57         }
 58         if(!p->lchild)
 59         {
 60             p->LTag = Thread;
 61             p->lchild = pre;
 62         }
 63         pre  = p;
 64         InThreading(p->rchild);
 65     }
 66 }
 67 
 68 Status InOrderThreading(BiThrTree &thrt,BiThrTree t)
 69 {
 70     if(!(thrt = (BiThrNode *)malloc(sizeof(BiThrNode))))
 71     {
 72         return ERROR;
 73     }
 74     thrt->LTag = Link;
 75     thrt->RTag = Thread;
 76     thrt->rchild = thrt;
 77     if(!t) 
 78     {
 79         thrt->lchild = thrt;
 80     }
 81     else
 82     {
 83         pre = thrt;
 84         thrt->lchild = t;
 85         InThreading(t);
 86         thrt->rchild = pre;
 87         pre->RTag = Thread;
 88         pre->rchild = thrt;
 89     }
 90     return OK;
 91 }
 92 
 93 Status CreateBiThrTree(BiThrTree &t)//一开始默认LTag和RTag全部定义成Link，在线索化时可以进行更改
 94 {
 95     TElemType ch;
 96     scanf("%d",&ch);
 97     if(ch == 0)
 98     {
 99         t = NULL;
100     }
101     else
102     {
103         t = (BiThrTree)malloc(sizeof(BiThrNode));
104         if(!t)
105         {
106             return ERROR;
107         }
108         t->data = ch;
109         t->LTag = Link;
110         t->RTag = Link;
111         CreateBiThrTree(t->lchild);
112         CreateBiThrTree(t->rchild);
113     }
114     return OK;
115 }

main.cpp

 1 #include "biThrTree.h"
 2 
 3 int main()
 4 {
 5     BiThrTree root;
 6     BiThrTree thr;
 7     printf("please input the value of the bithrtree:\n");
 8     CreateBiThrTree(root);
 9     InOrderThreading(thr,root);
10     InOrderTraverseThr(thr,visit);
11 
12     system("pause");
13     return 0;
14 }