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; 
}