이 진 트 리 의 옮 겨 다 니 기 (재 귀 법, 스 택 법)

9257 단어 데이터 구조
/* 
            
*/  
  
#include   
#include   
#define Ele char  
  
typedef struct BinTree  
{  
    Ele data;  
    struct BinTree * leftChild;  
    struct BinTree * rightChild;  
 }BinTree;  
  
#include "Stack.c"  
#include "LinkQueue.c"  
  
BinTree * NewTree(int level, int nowLevel);  
void TraversalByRecursion(BinTree * T, LinkQueue *LQ, int order) ; //     (   )   
void TraversalByStack(BinTree * T, int order) ;  
int main ()  
{  
    BinTree * T = NewTree(10, 1);  
      
    LinkQueue *LQ = NewQueue();   
    printf("
( ) "); TraversalByRecursion(T,LQ , 0); printf("
( ) "); TraversalByRecursion(T,LQ , 1); printf("
( ) "); TraversalByRecursion(T,LQ , 2); printf("
( ) "); TraversalByRecursion(T,LQ , 3); printf("
( ) "); TraversalByStack(T, 0); printf("
( ) "); TraversalByStack(T, 1); printf("
( ) "); TraversalByStack(T, 3); return 0; } // BinTree * NewTree(int level, int nowLevel) { if(nowLevel > level) { return NULL; } BinTree * T = (BinTree*)malloc(sizeof(BinTree)); T->data = nowLevel + 'A'; T->leftChild = NewTree(10, nowLevel * 2); T->rightChild = NewTree(10, nowLevel * 2 + 1); return T; } // ( ) order = 0 ; order = 1 ; order = 2 ; oeder = 3 void TraversalByRecursion(BinTree * T, LinkQueue *LQ,int order) { if(order == 0) { printf("%c ", T->data); if(T->leftChild != NULL) TraversalByRecursion(T->leftChild, LQ, order); if(T->rightChild != NULL) TraversalByRecursion(T->rightChild, LQ, order); } if(order == 1) { if(T->leftChild != NULL) TraversalByRecursion(T->leftChild, LQ, order); printf("%c ", T->data); if(T->rightChild != NULL) TraversalByRecursion(T->rightChild, LQ, order); } if(order == 2) { if(T->leftChild != NULL) TraversalByRecursion(T->leftChild, LQ, order); if(T->rightChild != NULL) TraversalByRecursion(T->rightChild, LQ, order); printf("%c ", T->data); } if(order == 3) { // :1 ;2 ;3 printf("%c ", T->data);//1 ; if(T->leftChild != NULL) PushQueue(LQ, T->leftChild);// 2 ; if(T->rightChild != NULL) PushQueue(LQ, T->rightChild);// 2 ; if(!IsEmptyQueue(LQ)) TraversalByRecursion(PopQueue(LQ), LQ, order);//3 } } // ( ) order = 0 ; order = 1 ; order = 2 ; oeder = 3 void TraversalByStack(BinTree * T, int order) { BinTree *temp; int rightChild = 0; Stack* S = NewStack(); /* 1 ; 2 , 3 */ if(order == 1) { while(T != NULL) { //1 ; while(T != NULL) { Push(S,T); T = T->leftChild; } //2 , do { T = Pop(S); printf("%c ", T->data);/ T = T->rightChild; } while(T == NULL && !IsEmpty(S)); } } /* 1 2 ; 3 */ if(order == 0) { while(T != NULL) { //1 ; while(T != NULL) { if(T->leftChild == NULL && T->rightChild == NULL) { printf("%c ", T->data);/ } Push(S,T); T = T->leftChild; } //2 , do { T = Pop(S); T = T->rightChild; } while(T == NULL && !IsEmpty(S)); } } /* : while( ) ; ; ; */ LinkQueue *LQ = NewQueue(); if(order == 3) { PushQueue(LQ, T);// while(!IsEmptyQueue(LQ)) { T = PopQueue(LQ);//1 printf("%c ", T->data);//2 if(T->leftChild != NULL) PushQueue(LQ, T->leftChild);//3 if(T->rightChild != NULL) PushQueue(LQ, T->rightChild);//3 } } }




Stack.c

/* 
        - (C  )  
      :  、  、  、       、  
*/  
  
#include    
#include   
#define Element BinTree*  
  
  
  
typedef struct _Stack  
{  
    Element data;  
    struct _Stack* next;  
} Stack;  
  
Stack * NewStack();//       
int Push(Stack * S, Element value) ;//     
Element Pop(Stack * S);//     
void Traserval(Stack *S);//     
int IsEmpty(Stack * S);//       
  
//int main()  
//{  
//  int i = 0;  
//  Stack* S = NewStack();  
//  for(i = 0; i < 20; i++)  
//  {  
//      Push(S, i * 3);//     
//  }  
//  Traserval(S);  
//  for(i = 0; i < 25;i++)  
//  {  
//      printf("     :%d    ", IsEmpty(S));   
//      printf("  : %d
", Pop(S)); // } // // return 0; //} // Stack * NewStack() { Stack* S = (Stack*)malloc(sizeof(Stack)); S->next = NULL; S->data = 0; return S; } // int Push(Stack * S, Element value) { Stack* temp = NewStack(); if(temp == NULL) { return -1; } temp->data = value; temp->next = S->next; S->next = temp; return 1; } // Element Pop(Stack * S) { Stack * temp; Element data; if(S->next == NULL) { return data; } temp = S->next; data = temp->data; S->next = temp->next; free(temp); return data; } // int IsEmpty(Stack * S) { if(S->next == NULL) { return 1; } return 0; } // void Traserval(Stack *S) { printf("
"); while(S->next != NULL) { printf("%d
", S->next->data); S = S->next; } }

LinkQueue.c

/* 
      (         ) 
      :   、  、  、  、      
*/  
#include   
#include    
#define Ele_3 BinTree*  
  
typedef struct LinkQueue  
{  
    Ele_3 data;  
    struct LinkQueue* next;  
}LinkQueue;  
  
  
LinkQueue* NewQueue();   
void PushQueue(LinkQueue* LQ, Ele_3 data);   
Ele_3 PopQueue(LinkQueue * LQ);  
void TraservalQueue(LinkQueue* LQ);  
int IsEmptyQueue(LinkQueue * LQ);   
//  
//int main()  
//{  
//  int i;  
//  LinkQueue *LQ = NewQueue();   
//  for(i = 0; i < 20; i ++)  
//  {  
//      Push(LQ, i * 4);  
//  }  
//  for(i = 0; i < 25; i ++)  
//  {  
//      printf("      %d
",IsEmpty(LQ)); // Pop(LQ); // Traserval(LQ); // } // return 0; //} // LinkQueue* NewQueue() { LinkQueue* LQ = (LinkQueue*)malloc(sizeof(LinkQueue)); LQ->data = 0; LQ->next = NULL; } // void PushQueue(LinkQueue* LQ, Ele_3 data) { int i; LinkQueue* temp = NewQueue(); temp->data = data; while(LQ->next != NULL) { LQ = LQ->next; } LQ->next = temp; } // Ele_3 PopQueue(LinkQueue * LQ) { LinkQueue * temp; Ele_3 data; if(LQ->next == NULL) { return data; } temp = LQ->next; data = temp->data; LQ->next = temp->next; free(temp); return data; } // int IsEmptyQueue(LinkQueue * LQ) { if(LQ->next == NULL) { return 1; } else { return 0; } } // void TraservalQueue(LinkQueue* LQ) { printf("
"); while(LQ->next != NULL) { printf("%d
", LQ->next->data); LQ = LQ->next; } }

좋은 웹페이지 즐겨찾기