C语言数据结构之线索二叉树及其遍历

#include<stdio.h> #include<stdlib.h>  #define OK 1 #define ERROR 0  typedef char ElemType; typedef int Status;  /* 定义枚举类型，其值只能是Link和Thread  * Link表示的该指针指示的是孩子  * Thread表示的是还指针指示的是前驱或者是后缀  * */ typedef enum {   Link,Thread }PointerTag;  typedef struct ThrBiTrNode{   ElemType data;   struct ThrBiTrNode *lchild, *rchild;   PointerTag rTag, lTag; }ThrBiTrNode, *ThrBiTree;  ThrBiTree Pre;  Status InitThreadBinaryTree(ThrBiTree* T){   *T = NULL;   return OK; } //先序建立二叉树,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag为Link Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){   ElemType c;   scanf("%c", &c);   if( ' ' == c ){     *T = NULL;   }   else{     *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode));     if( !*T ){       return ERROR;     }     (*T)->data = c;     (*T)->lTag = Link;     (*T)->rTag = Link;     ThreadBinaryTree_PreOrderInput(&(*T)->lchild);     ThreadBinaryTree_PreOrderInput(&(*T)->rchild);   }   return OK; } //<<中序遍历>>对二叉树进行<<线索化>>，但是没有提供Pre的初始值，只是给出了 //中间的过程，递归的思想和思考方式。 //1 线索化左子树 //2 对双亲节点处理//递归中的base //3 线索化右子树 Status InOrderThread(ThrBiTree T){   if( T != NULL ){     InOrderThread(T->lchild);    //线索化左子树          //对双亲节点进行线索化处理     if( T->lchild == NULL ){ //如果左孩子为空，则将lchild作为索引             //Pre指向刚刚访问的节点       T->lTag = Thread;       T->lchild = Pre;     }     if( Pre->rchild == NULL ){  //直到现在才知道Pre的后缀是T，所以             //要对Pre进行设置,如果Pre的rchild为空             //则将Pre的rchild设置为后缀，指向T       Pre->rTag = Thread;       Pre->rchild = T;     }      Pre = T;      //标记当前的节点称为刚刚访问过的节点             //Pre最后会指向树的中序遍历的最后的             //一个节点      InOrderThread(T->rchild);  //线索化右子树   }   return OK; } //创建中序线索二叉树,为上个函数提供Pre Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){   *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode));   if( !headOfTree )     return ERROR;   (*headOfTree)->lTag = Link;   //将要指向T   (*headOfTree)->rTag = Thread;    //将头节点的rchild用于索引   (*headOfTree)->rchild = *headOfTree;   //指向自身   if( T == NULL ){     (*headOfTree)->lchild = *headOfTree; //若T为空树，则头节点的lchild               //指向自身   }   else{     (*headOfTree)->lchild = T;     Pre = *headOfTree;     //赋值了全局变量Pre     InOrderThread(T);        //中序线索化     //printf("/n%c/n",Pre->data);             //执行完InOrderThread之后Pre指向最后             //一个节点     Pre->rTag = Thread;        Pre->rchild = *headOfTree;     //(*headOfTree)->rchild = Pre;   }   return OK; } //对中序线索化后的线索二叉树使用<<非递归>>的代码进行中序遍历 //并且原来的递归形式的代码在这里是不再可以进行遍历。 //  如果二叉树没有被线索化，也可以使用<<非递归>>的代码进行遍 //  历的，但是那就需要借助于<<栈>>,但是在线索化之后，对线索 //  化的二叉树进行<<非递归>>的遍历就不再需要栈的辅助。 Status visit(ElemType c){   printf("%c ", c);   return OK; } Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ //headOfTree是T的头节点的指针，headOfTree->lchild = T;   while( T != headOfTree ){     while( T->lTag == Link ){  //找到树(子树)的最左节点             //用while接替if//             //用if理解while//       T = T->lchild;     }             visit(T->data);      while( T->rTag == Thread && T->rchild != headOfTree){             //这个while和下面的T=T->rchild             //可用ifelse语句理解。             //if(rchild是线索 && 不是最后一个节点)              //else(rchild不是线索)-->走到右孩子             //也就是代码T=T->rchild       T = T->rchild;       visit(T->data);     }     T = T->rchild;   }   return OK; } //求中序线索二叉树中中序序列下的第一个节点 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){   if( T != NULL ){     while( T->lTag == Link ){       T = T->lchild;     }     return T;   }   return ERROR; } //求中序线索二叉树中节点P在中序序列下的下一个节点 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){   if( CurrentP->rTag == Link ){  //有右孩子的时候，那么下一个就是以           //右孩子为root的树的最左下角元素。           //即seekFirstNode的返回值。     return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild);   }   else{        //没有右孩子，则rchild指向后缀     return CurrentP->rchild;   } } //使用上面两个函数，SeekFirstNode_InOrderThrBiTree和GetNextNode来实现对 //中序先做二叉树的遍历 Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){   for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) )     visit(T->data);   return OK; }  //test /* ShowThread函数的目的是想在将T中序线索化之后，使用函数InOrderTraverse  * 函数中序遍历，输出一下节点中的信息以检验线索化，但是失败。原因是：在  * 线索化之后，空指针域都被应用，所有InOrderTraverse函数中的if( T )是满  * 足不了的，故失败。 Status ShowThread(ThrBiTree C){   printf("%d %d %d %d/n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag);   printf("%d %d/n",C->lTag,C->rTag);   return OK;  * */  //中序遍历二叉树 Status InOrderTraverse(ThrBiTree T){   if( T ){     InOrderTraverse(T->lchild);     visit(T->data);     InOrderTraverse(T->rchild);   }   return OK; } int main(){   ThrBiTree T,R,Head = NULL;   InitThreadBinaryTree(&T);    printf("Please Input Binary Tree By PreOrder/n  ");   ThreadBinaryTree_PreOrderInput(&T);    printf("  InOrder Traverse before Thread with Recursion/n");   InOrderTraverse(T);   printf("/n");    CreateInOrderThreadBinaryTree(T,&Head);   printf("  InOrder Traverse after Thread with no-Recursion/n");   InOrderTeaverse_NoRecursion(T,Head);   printf("/n");    printf("The root is %c /n", T->data);  //不能够通过指针形参的值改变指针实参的值             //或者说，对指针形参的改变不会作用到指针             //实参上。    ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL;   if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){     firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T);     printf("the value of First Node of InOrderThreadBinaryTree is %c/n", firstOfInOrder->data);   }   secondOfInOrder = GetNextNode(firstOfInOrder);   printf("the value of Node after D is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after B is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after E is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after A is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after C is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after G is: %c /n", secondOfInOrder->data);   secondOfInOrder = GetNextNode(secondOfInOrder);   printf("the value of Node after root is: %c /n", secondOfInOrder->data);    printf("  InOrder Traverse after Thread with no-Recursion Method_2/n");   InOrderTraverse_NoRecursion_Method(T,Head);    return 0; }