자료구조] 재귀를 이용한 이진트리 순환탐색

재귀를 이용해서 이진트리 순환탐색을 해보았다.

 

 

 

책에 설명이 잘 나와있겠지만, 1년전에 처음들을땐 잘 몰랐으므로..

순회팁은, 자식노드가 NULL이 나오지 않는이상은 출력하지않고 계~속 따라 내려가면된다.

내려가다가 NULL을 만나는 순간 값을 손으로 적으면 순회대로 값을 구할 수 있다.

 

전위순회 preoder는 VLR로,

중위순회 inoder는 LVR로,

후위순회 postoder는 LRV로,

 

 

 

 

 

#include<iostream>

using namespace::std;

typedef struct treeNode{
 char data;
 treeNode* lNode;
 treeNode* rNode;
}treeNode;

typedef struct BinTree{
 treeNode* root;
}BinTree;

BinTree* createBT(treeNode* node){
 BinTree* bt=(BinTree*)malloc(sizeof(BinTree));
 if(bt!=NULL){
  bt->root=node;  
 }else{
  //bad alloc
 }
 return bt;
}

///////////////재귀를이용한 preOder VLR////////////
void preOderTraversalNode(treeNode* node){
 if(node!=NULL){
  cout<<node->data<<" ";
  preOderTraversalNode(node->lNode);
  preOderTraversalNode(node->rNode);
 }
}
void preOderTraversal(BinTree* bt){
 if(bt !=NULL){
  preOderTraversalNode(bt->root);
 }
}
//////////////////////////////////////////////////

///////////////재귀를이용한 inOder lvR////////////
void inOderTraversalNode(treeNode* node){
 if(node!=NULL){
  inOderTraversalNode(node->lNode);
  cout<<node->data<<" ";
  inOderTraversalNode(node->rNode);
 }
}
void inOderTraversal(BinTree* bt){
 if(bt !=NULL){
  inOderTraversalNode(bt->root);
 }
}
//////////////////////////////////////////////////

///////////////재귀를이용한 postOder LRV////////////
void postOderTraversalNode(treeNode* node){
 if(node!=NULL){
  postOderTraversalNode(node->lNode);
  postOderTraversalNode(node->rNode);
  cout<<node->data<<" ";
 }
}
void postOderTraversal(BinTree* bt){
 if(bt !=NULL){
  postOderTraversalNode(bt->root);
 }
}
//////////////////////////////////////////////////

 

int main(void){

 treeNode* node=(treeNode*)malloc(sizeof(treeNode));
 memset(node,0,sizeof(treeNode));
 node->data='A';
 BinTree* bt= createBT(node);
 
 treeNode* B=(treeNode*)malloc(sizeof(treeNode)); 
 memset(B,0,sizeof(treeNode));
 B->data='B';
 (bt->root)->lNode=B;
 
 treeNode* C=(treeNode*)malloc(sizeof(treeNode)); 
 memset(C,0,sizeof(treeNode));
 C->data='C';
 (bt->root)->rNode=C;

 treeNode* D=(treeNode*)malloc(sizeof(treeNode)); 
 memset(D,0,sizeof(treeNode));
 D->data='D';
 B->lNode=D;

 treeNode* E=(treeNode*)malloc(sizeof(treeNode)); 
 memset(E,0,sizeof(treeNode));
 E->data='E';
 B->rNode=E;

 treeNode* H=(treeNode*)malloc(sizeof(treeNode)); 
 memset(H,0,sizeof(treeNode));
 H->data='H';
 D->lNode=H;
 
 treeNode* I=(treeNode*)malloc(sizeof(treeNode)); 
 memset(I,0,sizeof(treeNode));
 I->data='I';
 D->rNode=I;
 
 treeNode* J=(treeNode*)malloc(sizeof(treeNode)); 
 memset(J,0,sizeof(treeNode));
 J->data='J';
 E->lNode=J;

 
 treeNode* K=(treeNode*)malloc(sizeof(treeNode)); 
 memset(K,0,sizeof(treeNode));
 K->data='K';
 E->rNode=K;
 
 treeNode* F=(treeNode*)malloc(sizeof(treeNode)); 
 memset(F,0,sizeof(treeNode));
 F->data='F';
 C->lNode=F;
 
 treeNode* G=(treeNode*)malloc(sizeof(treeNode)); 
 memset(G,0,sizeof(treeNode));
 G->data='G';
 C->rNode=G;
 
 treeNode* L=(treeNode*)malloc(sizeof(treeNode)); 
 memset(L,0,sizeof(treeNode));
 L->data='L';
 F->lNode=L;
 
 treeNode* M=(treeNode*)malloc(sizeof(treeNode)); 
 memset(M,0,sizeof(treeNode));
 M->data='M';
 F->rNode=M;
 
 treeNode* N=(treeNode*)malloc(sizeof(treeNode)); 
 memset(N,0,sizeof(treeNode));
 N->data='N';
 G->lNode=N;
 
 treeNode* O=(treeNode*)malloc(sizeof(treeNode)); 
 memset(O,0,sizeof(treeNode));
 O->data='O';
 G->rNode=O;
 
 cout<<"재귀를 이용한 preoder traversal : "<<endl;
 preOderTraversal(bt);
 cout<<endl;
 cout<<"재귀를 이용한 inoder traversal : "<<endl;
 inOderTraversal(bt);
 cout<<endl;
 cout<<"재귀를 이용한 postoder traversal : "<<endl;
 postOderTraversal(bt);
 cout<<endl;

 return 0;
}