<![CDATA[아래의 소스는 이진탐색 트리에서 삽입,삭제 소스구요..]]><![CDATA[제가 궁금해 하는건 시간 복잡도를 어떻게 구하며,어떻게 해야 알수 있는건가요..]]><![CDATA[ ]]><![CDATA[#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <Malloc.h>
//define tree node
typedef struct tree_node *tree_pointer;
struct tree_node{
tree_pointer lchild;
int data;
tree_pointer rchild;
};
tree_pointer root = NULL;
//define queue
#define queue_size 30
tree_pointer queue[queue_size];
int front = 0;
int rear = 0;
int Isfull()
{
if(rear+1==front)return 1;
else return 0;
}
int Isempty()
{
if(front==rear)return 1;
else return 0;
}
void queue_full(int *rear)
{
if(*rear==0)*rear=queue_size-1;
else *rear-=1;
cout << endl << " ** err : queue full **" << endl;
}
void queue_add(int *rear, tree_pointer item)
{
*rear = (*rear+1) % queue_size;
if(front == *rear){
queue_full(rear);
return;
}
queue[*rear] = item;
}
tree_pointer queue_delete(int *front)
{
if(*front == rear)
return NULL;
*front = (*front+1) % queue_size;
return queue[*front];
}
// binary search tree program
void key_add();
void key_delete();
tree_pointer node_add(tree_pointer p, int key);
tree_pointer node_create();
void tree_output();
void main()
{
char job;
cout << "Key 추가는 'a', 삭제는 'd', 작업끝은 'e'를 입력하시오 : ";
cin >> job;
while(job=='a' || job=='d'){
if(job=='a')key_add();
if(job=='d')key_delete();
tree_output();
cout << endl;
cout << "Key 추가는 'a', 삭제는 'd', 작업끝은 'e'를 입력하시오 : ";
cin >> job;
}
}
void key_add()
{
tree_pointer father, temp;
int key;
cout << " * Enter add data : ";
cin >> key;
if(root){
father=node_add(root, key);
if(father->data==key){
cout << " * " << key << " is Duplicated \n";
return;
}
temp = node_create();
temp->data = key;
if(father->data > key)father->lchild=temp;
else father->rchild=temp;
}
else{
temp = node_create();
temp->data = key;
root=temp;
}
}
tree_pointer node_add(tree_pointer p, int key)
{
if(p->data==key){
return p;
}
if(p->data > key){
if(p->lchild)return node_add(p->lchild, key);
else return p;
}
else{
if(p->rchild)return node_add(p->rchild, key);
else return p;
}
}
tree_pointer node_create()
{
tree_pointer temp;
temp = (tree_pointer)malloc(sizeof(tree_node));
if(!temp){
fprintf(stderr, "* The memory is full\n");
exit(1);
}
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}
void key_delete()
{
return;
}
void tree_output()
{
tree_pointer temp;
if(!root){
cout << "* tree is empty *\n";
return;
}
cout << "* 현재 이진 탐색 트리 상태 *\n";
cout << " * root is : " << root->data << endl;
queue_add(&rear, root);
while(!Isempty()){
temp = queue_delete(&front);
if(temp->lchild){
cout << " * " << temp->data;
cout << "의 왼쪽 자노드는 : " << temp->lchild->data << endl;
queue_add(&rear, temp->lchild);
}
if(temp->rchild){
cout << " * " << temp->data;
cout << "의 오른쪽자노드는 : " << temp->rchild->data << endl;
queue_add(&rear, temp->rchild);
}
}
}
]]>
|
