Bstree.c

목차

*bstree.h

*Grade6.c

*bstree.c

*command.dat(내용 바꾼 것)

본문내용

의 수 합
{
int count;
if (p)//루트가 존재하면
count = NumNodes(p->left) + NumNodes(p->right) + 1;
//왼쪽 오른쪽 자식이 없을 때까지 내려가면서 그 수만큼 더함,
// 그리고 끝에 1을 더하는 건 루트를 더해준 것임
else
count = 0;
//루트가 없으면 아무것도 없다
return count;// 그 합 리턴
}
void BSTreeInsert(BSTree *T, BSTreeData key)//삽입 함수
{
T->root = InsBSNode(T,T->root,key);//루트에다가 이 함수의 호출값을 대입
}
BSTreeNodePtr InsBSNode(BSTree* T, BSTreeNodePtr p, BSTreeData key1)
{
if(!p){//루트가 없다면, 현재 아무것도 없으므로
p=(BSTreeNodePtr)malloc(sizeof(struct tnode));//메모리를 새로 할당받고
p->data = key1;//그 데이터 값에 입력 값 대입
p->left = p->right =NULL;// 그 자식 값에 NULL대입
}
else if(p->data.key > key1.key) p->left = InsBSNode(T,p->left,key1);
//만일 루트가 있고 입력 값이 루트보다 작으면, 왼쪽으로 가면서 계속 재귀
else if(p->data.key < key1.key) p->right = InsBSNode(T,p->right,key1);
//입력 값이 루트보다 크면 오른쪽으로 가면서 재귀 한 후
return p;//노드가 삽입 될 위치에 갔을 때 그 주소를 리턴
}
void BSTreeDelete(BSTree* T, BSTreeKey key)//제거 함수
{
T->root = DelBSNode(T->root, key);//루트에 대해 ,삭제할 노드의 정보를 보내어 함수 호출
}
BSTreeNodePtr DelBSNode(BSTreeNodePtr p, BSTreeKey key1)
{
BSTreeNodePtr q;//제거할 때 이전 것을 저장하기 위한 임의의 주소 선언
if(p) {//루트가 있고
if(key1 < p->data.key) p->left = DelBSNode(p->left,key1);
//지워야 할 값이 루트보다 작으면 그 왼쪽으로 이동하며 삭제할 노드 위치로 이동
else if(key1 > p->data.key) p->right = DelBSNode(p->right,key1);
//지워야 할 값이 루트보다 크면 그 오른쪽으로 가면서 삭제할 노드 위치로 이동
else if((p->right == NULL) && (p->left ==NULL)) p = NULL;
//그 위치에서 자식들이 둘 다 없으면 지워야할 노드는 그 노드 가 된다.
else if(p->left == NULL) { q = p; p = p->right; free(q);}
//그게 아니라 왼쪽만 자식이 없으면, 그 노드의 주소를 Q에 대입한 후 ,그 노드 자식의 오른쪽 자식을
// 자신의 위치로 옮기고 , 저장한 자신의 주소 반환
else if(p->right == NULL) { q = p; p = p->left; free(q);}
//오른쪽도 같은 방식으로 메모리 반환
else { //위의 경우에서 아무것도 안 걸리면
q=FindMax(p->left); p->data = q->data ;//왼쪽 자식의 최대 값을 찾아 그 값을 지운 자리에 대입
p->left = DelBSNode(p->left,p->data.key);//왼쪽 노드는 왼쪽으로 이동하며 계속 재귀 호출한다.
}
}
else printf("not found\n");//루트가 없으면 못 찾는다.
return p;//그리고 지우고 난 뒤 새로 채워진 주소를 리턴
}
int BSTreeFind(BSTree* T, BSTreeKey key)//검색 함수
{
if(T->root) return (FindBSNode(T,T->root,key));//루트가 존재하면 호출 함수 불리안 리턴
}
int FindBSNode(BSTree* T, BSTreeNodePtr p, BSTreeKey newkey)//호출된 검색 함수
{
if(p){//루트가 존재하고
if(p->data.key > newkey) return FindBSNode(T,p->left,newkey);
//검색할 값이 루트 데이터보다 작으면 오른쪽으로 가며 크기 비교
else if(p->data.key < newkey) return FindBSNode(T,p->right,newkey);
//크면 왼쪽으로 가며 비교
else if(p->data.key==newkey) { T->current = p ; return True; }
//그래서 그 값이 같으면 그것을 커런트로 해서 TRUE리턴,
//만일 위의 두 조건에 안 걸리면, 루트가 검색하는 노드
else return False; }//아님 트리에 없는 것이므로 FALSE
else return False;//루트가 없으면 FALSE
}
void BSTreeWrite(BSTree* T)//트리 값을 오름차순 출력
{
NodeWrite(T->root); printf("\n\n");//루트 값을 보내어 호출
}
void NodeWrite(BSTreeNodePtr p)//루트가 P가 되고
{
if(p != NULL)//루트가 비어있지 않으면
{
NodeWrite(p->left);//오름차순이므로 작은 쪽인 왼쪽으로 계속 이동한다.
//그러면 최소 값이 있는 노드에 갈 것이고
printf("%2d",p->data.key);//그 값을 출력하고 올라오면서
NodeWrite(p->right);//오른쪽 노드의 값을 확인하면 부모보단 작고 왼쪽보다는 큰 값이 있다
//그리고 다시 그 왼쪽 노드가 있는지 확인하게 되고 ,처음에 왼쪽으로 가지 않으면 오른쪽에
//대해서도 이와 같이 호출하게 되므로 오름차순의 정렬이 끝난다.
}
}
*command.dat(내용 바꾼 것)
+51
+32
+73
+24
+40
+65
+87
+10
+50
f 40
f 90
-30
w
n
q

키워드

노드,   Grade6.c,   bstree.h,   system,   변수,   BST