这个是用链式队列辅助建立的二叉树和中序递归遍历
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define Max_Size 25
#define Null 0
#define Link 0
#define Thread 1
typedef int Tree_Data;
struct Tree {
Tree *LChild,*RChild;
int LTag ,RTag;
Tree_Data Value;
};//二叉树结点
typedef Tree Data;
struct Q_Data
{
Data *e;
Q_Data *Next;
};//定义链队列节点数据
typedef struct
{
struct Q_Data *Head,*Tail;
int Lengh;
}Chain_Q;//定义链队列指针
int Create_Chain_Q(Chain_Q &List)
{
List.Head = (Q_Data *)malloc(sizeof(Q_Data));
List.Tail = List.Head;
List.Head->Next = Null;
List.Lengh = 0;
return 1;
}//建立队列
int In_Chain_Q(Chain_Q &List, Data **Q_Value)
{
struct Q_Data *Data_1;
for (Data_1=List.Head;Data_1->Next!=Null;Data_1=Data_1->Next);
Data_1->Next = (Q_Data *)malloc(sizeof(Q_Data));
Data_1->Next->Next= Null;
List.Tail = Data_1->Next;
List.Tail->e = *Q_Value;
return 1;
}//入队
int Out_Chain_Q(Chain_Q &List, Data **Q_Value)
{
struct Q_Data *Data_1;
if (List.Head->Next == Null)return 0;
Data_1=List.Head->Next;
List.Head->Next=List.Head->Next->Next;
*Q_Value = Data_1->e;
free(Data_1);
return 1;
}//出队
int Opera(Tree &Tree_Data)
{
printf("Data=%d,",Tree_Data.Value);
printf("O=%d,",&Tree_Data);
printf("LChild=%d,",Tree_Data.LChild);
if (Tree_Data.LTag== 1)printf("LTag=%d,",Tree_Data.LTag);
printf("RChild=%d,",Tree_Data.RChild);
if (Tree_Data.RTag== 1)printf("RTag=%d,",Tree_Data.RTag);
printf("\n");
return 1;}//操作节点
int Pre_Order(Tree *List , int T)
{
if (List!=Null && T!=Thread)
{
Opera(*List);
if (Pre_Order(List->LChild,List->LTag)==1)if (Pre_Order(List->RChild,List->RTag)==1)return 1;
}
else return 1;
}//先序遍历二叉树
int Mid_Order(Tree *List,int T)
{
if (List!=Null && T!=Thread)
{ if (Mid_Order(List->LChild,List->LTag)==1)
{
Opera(*List);
Mid_Order(List->RChild,List->RTag);
return 1;
}
}
else return 1;
}//中序遍历二叉树
int Back_Order(Tree *List,int T)
{
if (List!=Null && T!=Thread)
{
{ if (Back_Order(List->LChild,List->LTag)==1)
if (Back_Order(List->RChild,List->RTag)==1)
{
Opera(*List);
return 1;
}
}
}else return 1;
} //后序遍历二叉树
int Mid_Thread( Tree *List,Tree **Top)
{ int In_Mid_Thread(Tree *T,Tree **Pre_1);
Tree *Pre;
Pre = *Top;
(*Top)->LTag = Thread;(*Top)->LChild = List;
In_Mid_Thread(List,&Pre);
Pre->RChild=*Top;
((*Top)->RTag) = Thread;(*Top)->RChild = Pre;
return 1;}//中序线索遍历二叉树
int In_Mid_Thread(Tree *T,Tree **Pre_1)
{
if (T!=Null && T->LTag!=Link && T->RTag !=Link)
{if (In_Mid_Thread(T->LChild, &(*Pre_1))==1)
{int a;
if ((T->LChild == Null) || (T->LTag == Thread))
{
T->LChild = *Pre_1;
T->LTag = Thread;
}else T->LTag = Link;//如果当前点的LChild为空或标志域为Thread，将上一遍历节点值赴给当前点LChild，
//并将当前点赴值给Pre，备用作下一叶子节点的前驱
if ((*Pre_1)->RChild == Null || (*Pre_1)->RTag == Thread)
{
(*Pre_1)->RChild = T;
(*Pre_1)->RTag = Thread;
}else (*Pre_1)->RTag = Link;
(*Pre_1) = T;
In_Mid_Thread(T->RChild, &(*Pre_1));
} return 1;
}else return 1;
}//为中序加线索
/*根据数组转化成二叉树，
设立辅助队列，建立结点并入队，出队一结点，建左右节结并入队*/
int main ()
{
int Create_Chain_Q(Chain_Q &List);
int In_Chain_Q(Chain_Q &List, Data &Q_Value);
int Out_Chain_Q(Chain_Q &List, Data &Q_Value);
int Pre_Order(Tree *List,int T),Mid_Order(Tree *List,int T),Back_Order(Tree *List,int T);
int Mid_Thread( Tree *List,Tree **Top);
Tree_Data Array[Max_Size]={32,54,20,89,92,14,24,85,24,58,52,27,9,21,4,55,28,19,7,25,19,23,65,2,14};
int Count=0;
char Add[12],Add_1[12];
struct Tree O,O_1,*Now_O,*Order,*Head_O;
Chain_Q User;
int a=1;
//函数声明与变量定义
O.Value = Array[Count];
Order = &O;
Now_O = &O;
Create_Chain_Q(User);
In_Chain_Q(User,&Now_O);
//按照数组利用辅助链接点建立二叉树
while (1)
{
if (++Count==Max_Size)break;
Out_Chain_Q(User,&Now_O);
Now_O->LChild = (Data *)malloc(sizeof(Data));
Now_O->LChild->Value = Array[Count];
In_Chain_Q(User,&(Now_O->LChild));
if (++Count==Max_Size)break;
Now_O->RChild = (Data *)malloc(sizeof(Data));
Now_O->RChild->Value = Array[Count];
In_Chain_Q(User,&(Now_O->RChild));
}
Head_O = (Data *)malloc(sizeof(Data));
//将无孩子节点的左右Child指针设为空
while (Out_Chain_Q(User,&Now_O)!= 0)
{
Now_O->LChild = Null;
Now_O->RChild = Null;
}
printf("\n");printf("先序遍历:");
Pre_Order(Order,Link);
Mid_Thread(Order,&Head_O);
printf("\n");printf("中序遍历:");
Mid_Order(Order,Order->LTag);
printf("\n");
printf("后序遍历:");
Back_Order(Order,Order->LTag);
scanf("%s",Add);
return 1;
}
