『서 론』■ 이번 과제는 이진탐색트리를 구현해서 그에 맞는 함수를 만들어서 조건에 맞는 프로그램을 만드는 목적으로 주어진 과제이다. 일단, 이진탐색트리는 Root노드를 기준으로 왼쪽노드, 오른쪽 노드를 가르키는 일반 이진트리의 구조를 가지고 있으며, 다만, 오른쪽노드는 Root노드의 값보다 크며 왼쪽노드는 더 작은 값을 가지는 구조이다. 각 밑에 노드들은 이와 같은 성질을 다 가지고 있다. 기본적인 지식은 충분히 가지고 있어서 이번과제는 충분히 도전해 볼만한 것이며, 앞에 내용을 충분히 복습하였기 때문에 흥미를 가지고 할 수 있겠다.구현하게 될 함수는 다음과 같다.■ 구현하게 될 함수1. int size(Nptr)- 트리의 노드의 개수를 구하게 될 함수2. int getHeight(Nptr T);- 트리의 높이를 구하게 될 함수3. int minValue(Nptr T);- 트리 중에 가장 작은 값을 구하는 함수4. int maxValue(Nptr T);- 트리 중에 가장 큰 값을 구하는 함수5. void printInorder(Nptr T);- 중위 순위로 출력 시켜주는 함수6. void printPostorder(Nptr T);- 후위 순위로 출력 시켜주는 함수7. int hasPathSum(Nptr T, int sum);- 어떤 값이, 트리의 각 경로의 합 중에 일치하는 것이 있는지 알아보는 함수8. int sameTree(Nptr T1,Nptr T2);- 두개의 트리가 구조가 같고, 값이 같은지 알아보는 함수9. void printPaths(Nptr T);- 트리의 경로(Root 노드 -> 각 leaf노드)를 출력해주는 함수10. void mirror(Nptr T);- 트리를 Root를 기준으로 대칭시켜서 마치 거울과 같은 역할을 하게 하는 함수11. int isBST(Nptr T);- 주어진 트리가 이진탐색트리가 맞는지 안맞는지 알아보는 함수『본 론』#include #include typedef struct treenode//node의 구성을 위한 구조면count+=size(T->lchild);//변수에다가 왼쪽노드에 대한 size함수를 재귀한다if(T->rchild!=NULL)//오른쪽 노드가 비어있지 않다면count+=size(T->rchild);//변수에다가 오른쪽노드에 대한 size함수를 재귀한다return count;//변수를 리턴한다}Nptr RootMake(Nptr T,int key)//Root node를 만들기 위한 함수{T->key=key;//값을 집어 넣고T->lchild=NULL;//왼쪽노드를 비어 있다고 함T->rchild=NULL;//오른쪽 노드를 비어 있다고 함return T;//노드를 리턴해줌}Nptr Insert(Nptr T,int key)//노드의 추가를 위한 함수{if(T==NULL)//만약 비어있다면{T=(node*)malloc(sizeof(node));//동적할당 시켜준다T->key=key;//값을 넣어준다T->lchild=NULL;//왼쪽 오른쪽 노드를 비어 있다고 함T->rchild=NULL;}else if(T->key>key)//비어 있지않고, 노드의 값이 입력할 값보다 클 경우T->lchild=Insert(T->lchild,key);//왼쪽 노드에 대해 Insert 재귀 함수else//입력할 값이 더 크다면T->rchild=Insert(T->rchild,key);//오른쪽 노드에 대해 Insert 재귀 함수return T;//노드를 리턴}int getHeight(Nptr T)//높이를 구하는 함수{int height1 = 0;//왼쪽 노드에 대한 높이int height2 = 0;//오른쪽 노드에 대한 높이if(T==NULL)//만약 노드가 비어있다면return 0;//0을 리턴else//비어 있지 않다면{height1=getHeight(T->lchild);//왼쪽 노드에 재귀함수에 대한 리턴값을 height1에 저장height2=getHeight(T->rchild);//오른쪽 노드에 재귀함수에 대한 리턴값을 height2에 저장}return height1>heigh값을 리턴}void printInorder(Nptr T)//중위 순회를 위한 함수{if(T!=NULL)//노드가 비어 있지 않다면{printInorder(T->lchild);//왼쪽 노드에 대해 재귀 함수printf("%d ",T->key);//값을 출력printInorder(T->rchild);//오른쪽 노드에 대해 재귀 함수}}void printPostorder(Nptr T)//후위 순회를 위한 함수{if(T!=NULL)//노드가 비어 있지 않다면{printPostorder(T->lchild);//왼쪽 노드에 대해 재귀 함수printPostorder(T->rchild);//오른쪽 노드에 대해 재귀 함수printf("%d ",T->key);//값을 출력}}int hasPathSum(Nptr T,int sum)//각 트리경로에 있는 합이 입력한 값과 일치하는지 알아내는 함수{if(T==NULL)//노드가 비어 있다면{return sum==0;//false를 리턴함. false리턴위해 sum==0 사용}else{sum-=T->key;//sum값을 노드의 값으로 줄여나감return (hasPathSum(T->lchild,sum)||hasPathSum(T->rchild,sum));//왼쪽 부터 계산해서 오른쪽 노드까지 계산 있으면 1을 리턴}}int sameTree(Nptr T1,Nptr T2)//트리가 같은지 아닌지 판별하는 함수{if(T1==NULL&&T2==NULL)//두 트리가 비어 있다면return 1;//1을 리턴else if(T1!=NULL && T2!=NULL)//두 트리가 비어 있지 않다면return (sameTree(T1->lchild,T2->lchild) && sameTree(T1->rchild,T2->rchild) && T1->key==T2->key); //세가지 사항을 모두 만족하면 리턴 1 아니면 0을 리턴elsereturn 0;}void printPaths(Nptr T)//각 경로를 출력{int path[100];//경로의 값을 저장하기위L)//만약 왼쪽 노드 오른쪽 노드가 모두 비어 있다면{printf("- ");for(i=0;ilchild,path,pathLen);//printPathsRecur함수를 왼쪽노드에 대해 재귀함수printPathsRecur(T->rchild,path,pathLen);//printPathsRecur함수를 오른쪽노드에 대해 재귀함수}}}void mirror(Nptr T)//각자 Root노드에 대해 대칭시켜주는 함수{Nptr temp=(node*)malloc(sizeof(node)); //임시 저장하기위한 노드생성if(T!=NULL)//노드가 비어 있지 않다면{temp=T->lchild;//왼쪽노드를 임시노드에 저장T->lchild=T->rchild;//왼쪽노드에 오른쪽 노드T->rchild=temp;//오른쪽 노드는 임시노드if(T->lchild!=NULL) //만약 왼쪽노드가 비어 있지않다면mirror(T->lchild);//왼쪽노드에 대한 재귀함수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) key))//만약 오른쪽 노드가 비어 있지않고, 오른쪽노드의 가장 큰값이 루트노드의 값보다 크다면return 0;}int main(){int value;//값을 입력받기위한 변수Nptr Root=(node*)malloc(sizeof(node));//Root노드를 생성Nptr Root_=(node*)malloc(sizeof(node));//Rt,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.1n");printf("-- SIZE 노드의 개수 : %dnn",size(Root));//노드의 개수를 출력printf("- Function No.2n");printf("-- Tree Height의 길이는 %d 이다. nn",getHeight(Root));//getHeight함수 이용해서 높이 출력printf("- Function No.3n");printf("-- minValue (가장 작은 값) : %dnn",minValue(Root));//minValue함수 이용 가장 작은값 출력printf("- Function No.4n");printf("-- maxValue (가장 큰 값) : %dnn",maxValue(Root));//maxValue함수를 이용 가장 큰값 출력printf("- Function No.5n");printf("-- InOrder (중위 표기) : ");printInorder(Root);//중위 순회 순서대로 출력printf("nn");printf("- Function No.6n");printf("-- PostOrder (후위 표기) : ");printPostorder(Root);//후위 순회 순서대로 출력printf("nn");printf("- Function No.7n");printf("-- 값 있는지 확인...값 입력 (값이 있으면 1, 없으면 0) : ");scanf("%d",&value);//값을 입력");