C 언어 데이터 구조의 단서 이 진 트 리 와 그 옮 겨 다 니 기

C 언어 데이터 구조의 단서 이 진 트 리 와 그 옮 겨 다 니 기
이 진 트 리 를 옮 겨 다 니 는 것 은 일정한 규칙 으로 이 진 트 리 의 노드 를 하나의 선형 서열 로 배열 하여 이 진 트 리 노드 의 각종 옮 겨 다 니 는 서열 을 얻 는 것 이다.그 실질 은 비 선형 구 조 를 선형 화 하 는 것 이다.이 접근 시퀀스 에서 모든 노드 에 직접 전구 와 직접 후계 가 있 도록 합 니 다.전통 적 인 체인 구 조 는 부자 관 계 를 나 타 낼 수 밖 에 없다.즉,65509℃는 노드 가 옮 겨 다 니 는 전구 와 후계 의 65509℃를 직접 얻 을 수 없다.우 리 는 이 진 링크 가 나타 내 는 이 진 트 리 에 대량의 빈 지침 이 있다 는 것 을 알 고 있다.이런 빈 지침 으로 노드 를 가리 키 는 전구 와 후계 의 지침 을 저장 할 때 이 진 트 리 의 일부 조작 을 더욱 편리 하 게 활용 할 수 있다.단서 이 진 트 리 를 도입 하 는 목적 은 노드 의 전구 와 후계 찾기 를 가속 화하 기 위 한 것 이다.이 진 트 리 에 대한 단서 화 는 이 진 트 리 를 한 번 옮 겨 다 니 는 것 입 니 다.옮 겨 다 니 는 과정 에서 노드 의 좌우 포인터 가 비어 있 는 지 확인 하고 비어 있 으 면 전구 와 후계 노드 를 가리 키 는 단서 로 바 꿉 니 다.
이 진 트 리 가 단서 화 되 지 않 았 다 면<<비 재 귀적>>코드 로 옮 겨 다 닐 수 있 습 니 다.하지만<<스 택>>의 도움 을 받 아야 합 니 다.하지만 온라인 으로 삭 화 된 이 진 트 리 를<비 재 귀적>>으로 옮 겨 다 니 면 스 택 의 보조 가 필요 하지 않 습 니 다.
구현 코드:

#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("
%c
",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
",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); 
  printf("%d %d
",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
  "); 
  ThreadBinaryTree_PreOrderInput(&T); 
 
  printf("  InOrder Traverse before Thread with Recursion
"); 
  InOrderTraverse(T); 
  printf("
"); 
 
  CreateInOrderThreadBinaryTree(T,&Head); 
  printf("  InOrder Traverse after Thread with no-Recursion
"); 
  InOrderTeaverse_NoRecursion(T,Head); 
  printf("
"); 
 
  printf("The root is %c 
", 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
", firstOfInOrder->data); 
  } 
  secondOfInOrder = GetNextNode(firstOfInOrder); 
  printf("the value of Node after D is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after B is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after E is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after A is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after C is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after G is: %c 
", secondOfInOrder->data); 
  secondOfInOrder = GetNextNode(secondOfInOrder); 
  printf("the value of Node after root is: %c 
", secondOfInOrder->data); 
 
  printf("  InOrder Traverse after Thread with no-Recursion Method_2
"); 
  InOrderTraverse_NoRecursion_Method(T,Head); 
 
  return 0; 
} 

이상 은 단서 이 진 트 리 와 옮 겨 다 니 는 실례 입 니 다.궁금 한 점 이 있 으 시 면 메 시 지 를 남기 거나 본 사이트 지역사회 에 가서 토론 을 하 십시오.읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 지지 에 감 사 드 립 니 다!