[자료구조]이진탐색트리

본문내용

함수
if(T->rchild!=NULL)//만약 오른쪽 노드가 비어 있지않다면
mirror(T->rchild);//오른쪽노드에 대한 재귀함수
}
}
int isBST(Nptr T)//이 트리가 이진탐색트리인지 알아보는 함수
{
if(T == NULL)//만약 노드가 비어 있다면
return 1;//1을 리턴
if((T->lchild != NULL) && (maxValue(T->lchild) > T->key))
//만약 왼쪽 노드가 비어 있지않고, 왼쪽노드의 가장 큰값이 루트노드의 값보다 크다면
return 0; //0을 리턴
if((T->rchild != NULL) && (minValue(T->rchild) <= T->key))
//만약 오른쪽 노드가 비어 있지않고, 오른쪽노드의 가장 큰값이 루트노드의 값보다 크다면
return 0;
}
int main()
{
int value;//값을 입력받기위한 변수
Nptr Root=(node*)malloc(sizeof(node));//Root노드를 생성
Nptr Root_=(node*)malloc(sizeof(node));//Root_노드를 생성
RootMake(Root,14);//Root노드의 값을 14로 함
RootMake(Root_,14);//Root_노드의 값을 14로 함
//이진트리를 구성하기 위한 삽입
Insert(Root,10);Insert(Root,19);Insert(Root,3);Insert(Root,12);Insert(Root,15);
Insert(Root,21);Insert(Root,1);Insert(Root,5);Insert(Root,11);Insert(Root,13);
Insert(Root,20);Insert(Root,29);Insert(Root,33);
//이진트리가 같은지 다른지에 대한 결과를 얻기위해 새로운 트리 형성
Insert(Root_,10);Insert(Root_,19);Insert(Root_,3);Insert(Root_,12);Insert(Root_,15);
Insert(Root_,21);Insert(Root_,2);Insert(Root_,5);Insert(Root_,11);Insert(Root_,13);
Insert(Root_,20);Insert(Root_,29);Insert(Root_,33);
printf("- Function No.1\n");
printf("-- SIZE 노드의 개수 : %d\n\n",size(Root));//노드의 개수를 출력
printf("- Function No.2\n");
printf("-- Tree Height의 길이는 %d 이다. \n\n",getHeight(Root));
//getHeight함수 이용해서 높이 출력
printf("- Function No.3\n");
printf("-- minValue (가장 작은 값) : %d\n\n",minValue(Root));
//minValue함수 이용 가장 작은값 출력
printf("- Function No.4\n");
printf("-- maxValue (가장 큰 값) : %d\n\n",maxValue(Root));
//maxValue함수를 이용 가장 큰값 출력
printf("- Function No.5\n");
printf("-- InOrder (중위 표기) : ");
printInorder(Root);//중위 순회 순서대로 출력
printf("\n\n");
printf("- Function No.6\n");
printf("-- PostOrder (후위 표기) : ");
printPostorder(Root);//후위 순회 순서대로 출력
printf("\n\n");
printf("- Function No.7\n");
printf("-- 값 있는지 확인...값 입력 (값이 있으면 1, 없으면 0) : ");
scanf("%d",&value);//값을 입력 받음
printf("## 값 출력 : ");
if(hasPathSum(Root,value))//리턴값이 true이면
printf("1");
else//false이면
printf("0");
printf("\n\n");
printf("- Function No.8\n");
printf("-- Inorder of the other tree : ");
printInorder(Root_);//다른 노드를 중위식을 일단 출력(값의 비교를 보여주기위해)
printf("\n");
printf("-- Compare first Tree and second Tree!!\n");
printf("-- Is same or different : ");
if(sameTree(Root,Root_))//리턴값이 true이면
printf("same\n");
else
printf("different");//리턴값이 false
printf("\n\n");
printf("- Function No.9\n");
printPaths(Root);//각 경로를 출력
printf("\n");
printf("- Function No.10\n");
mirror(Root);//각 Root를 기준으로 대칭 시켜줌 (mirror)
printf("-- Mirror of Tree");
printf("\n");
printf("-- Mirror of InOrder : ");
printInorder(Root);//대칭한 트리를 중위 순회대로 순서대로 출력
printf("\n");
printf("-- Mirror of PostOrder : ");
printPostorder(Root);//대칭한 트리를 후위 순회대로 순서대로 출력
printf("\n\n");
mirror(Root); //원래의 트리로 바꿔주기위해 mirror함수를 사용
printf("- Function No.11\n");
printf("-- isBST True? (if answer '1',then True. if '0', then False) : ");
printf(" %d\n",isBST(Root)); //이진탐색트리이면 1을 아니면 0을 리턴받아서 출력
return 0;
}
<실행화면>
교수님 수고하셨습니다!!

키워드

자료구조,   프로그래밍,   이진탐색트리,   트리