inorder트래버스: 2개의 글

알고리즘(Algorithm) 실습6

Posted by Patchman
2010.02.15 15:07 Univ Study/알고리즘과 실습

 

6-1. 다음에 주어진 프로그램을 참고해서 N(>100) 개의 자료를 rand()로 발생하고 이진 탐색트리에 BSTinsert()해서 이진 탐색트리(Binary search tree) T1을 만들고, 입력된 자료를 각각 탐색하는데 소요된 키의 평균비교회수를 출력하시오. (단, 평균비교회수는 각 자료 탐색을 위한 키의 비교회수 합계를 구한 다음에 전체 자료수 N으로 나누어서 계산함)

 

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0 // 더미노드 이자 마지막 노드인 z의값

#define itemMIN -1 // Binary search tree의 head 값,

head의 오른쪽부터 노드가 오게 하기 위하여

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

 

class BST

{

private:

struct node

{

itemType key;

infoType info;

struct node *l, *r;

// 구조체 초기화를 위해

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

void BSTresult();

};

 

infoType BST::BSTsearch(itemType v) // Binary search tree 를 탐색하는 함수

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){ // tree를 순회하며 v의 값을 탐색한다

comparision++; // 비교연산회수 카운터 증가

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

void BST::BSTinsert(itemType v, infoType info) // Binary search tree 를 구현하는 함수

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z) // 전달받은 킷값이 들어갈 노드의 위치를 탐색한다

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z); // 위치를 탐색한 x에 새로운 노드를 생성한다

if(v < p->key) p->l = x; // 부모 노드인 p와비교하여 l,r 위치를 결정한다.

else p->r = x;

}

 

void result() // 결과출력함수

{

cout << " 총 비교연산회수는: " << comparision << "\n"

cout << " 평균비교연산회수는: " << (comparision/MAX) << "\n\n"

}

 

void main()

{

BST T1(MAX);

 

itemType a[MAX];

itemType info = 0;

 

int i;

 

cout << "\n----------- Rand(" << MAX << ") ---------------\n\n"

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

printf("%5d ; ", a[i]);

T1.BSTinsert(a[i], info++); // Rand() 함수를 통한 임의의 수 발생과 동시에 BSTinsert를 이용하여 Binary search tree 를 구현한다.

}

cout << "\n------------------------------------------------\n"

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]); // Binary search tree 에 입력된 모든 자료를 탐색한다

 

cout << "----------- Tree T1 -----------\n\n"

result(); // 총 비교회수와, 평균 비교회수를 출력한다.

cout << "-------------------------------\n\n"

 

}

 

▣ 결과 출력

 








6-2. 6-1에서 만들어진 트리 T1의 자료들을 INORDER로 트래버설(출력)하면서 각 자료를 새로운 이진탐색트리 T2에 BSTinsert()해서 이지탐색트리를 생성한 다음에, T2의 각 자료를 탐색하는데 소요된 키의 평균비교회수를 출력하고, 6-1의 결과와 비교하시오.(참고, T2는 skewed binary search tree가 됨)

 

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0

#define itemMIN -1

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

 

class BST

{

private:

 

struct node

{

itemType key;

infoType info;

struct node *l, *r;

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

 

void BSTInorderTraverse(BST *t2);

void BSTInorderTraverse(node *t, BST *t2);

 

};

 

infoType BST::BSTsearch(itemType v)

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){

comparision++;

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

 

void BST::BSTinsert(itemType v, infoType info)

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z)

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z);

if(v < p->key) p->l = x;

else p->r = x;

}

 

// overloading을 이용해 첫 노드인 head->r을 class T2와 함께 다시 BSTInorderTraverse로 보낸다.

void BST::BSTInorderTraverse(BST *t2)

{

BSTInorderTraverse(head->r, t2);

}

 

// 전달받은 노드와 class T2를 inorder traverse 하며 BSTinsert로 보내 tree T2를 생성한다.

void BST::BSTInorderTraverse(node *t, BST *t2)

{

if(t != z)

{

BSTInorderTraverse(t->l, t2);

t2->BSTinsert(t->key,t->key);

BSTInorderTraverse(t->r, t2);

}

}

 

void result() // 결과출력함수

{

cout << " 총 비교연산회수는: " << comparision << "\n"

cout << " 평균비교연산회수는: " << (comparision/MAX) << "\n\n"

comparision = 0; // T1의비교연산회수출력후초기화

}

 

void main()

{

BST T1(MAX), T2(MAX); // T1, T2 클래스생성

 

itemType a[MAX];

itemType info = 0;

int i;

 

cout << "\n------------- Rand(" << MAX << ") -------------\n\n"

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

printf("%5d ; ", a[i]);

T1.BSTinsert(a[i],info++);

}

cout << "\n------------------------------------------------\n"

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]);

 

cout << "----------- Tree T1 -----------\n\n"

result();

cout << "-------------------------------\n\n"

 

T1.BSTInorderTraverse(&T2); // T1의자료를Inorder traverse 하면서

// T2에BSTinsert 하기위해T2 Class를전달한다

for(int i=0; i < MAX; i++) T2.BSTsearch(a[i]);

 

cout << "----------- Tree T2 -----------\n\n"

result();

cout << "-------------------------------\n\n"

}

 

▣ 결과 출력

 

 

 


 

6-3. 정수 a와 b를 입력하여 6-1에서 만들어진 Binary search tree T1에서 a<x<b에 해당하는 x를 모두 찾는 알고리즘 BstRange(T1, a, b)를 기술하고, 구현하여 범위 (a, b)에 속하는 원소의 값과 총 개수를 출력하시오. 단, 출력할 원소수가 10개 이상이면 10개 까지만 출력함.

 

#include <iostream>

#include<stdlib.h>

using namespace std;

 

#define MAX 150

#define infoLILk 0

#define itemMIN -1

 

typedef int itemType;

typedef int infoType;

 

int comparision = 0;

int rangecount = 0; // 범위에 속하는 원소의 총 개수를 구하기 위한 변수

 

class BST

{

private:

struct node

{

itemType key;

infoType info;

struct node *l, *r;

node(itemType k, infoType i, struct node *ll, struct node *rr)

{ key = k; info = i; l = ll; r = rr; }

};

struct node *head, *z;

 

public:

BST(int max)

{

z = new node(0, infoLILk, 0, 0);

head = new node(itemMIN, 0, z, z);

}

 

~BST()

{

delete(z);

delete(head);

}

 

infoType BSTsearch(itemType v);

void BSTinsert(itemType v, infoType info);

void BSTresult();

 

void BST::BstRange(int a, int b); // 범위의 원소를 찾기 위한 함수 - Overloading

void BST::BstRange(node *x, int a, int b);

};

 

infoType BST::BSTsearch(itemType v)

{

struct node *x = head->r;

z->key = v;

 

while(v != x->key){

comparision++;

x = (v < x->key) ? x->l : x->r;

}

return x->info;

}

 

void BST::BSTinsert(itemType v, infoType info)

{

struct node *p, *x;

p = head;

x = head->r;

 

while(x != z)

{

p = x;

x = (v < x->key) ? x->l : x->r;

}

 

x = new node(v, info, z, z);

if(v < p->key) p->l = x;

else p->r = x;

}

 

// overloading을 이용해 전달받은 Range값 a,b와 첫 노드인 head->r를 다시 BstRange로 보낸다.

void BST::BstRange(int a, int b)

{

BstRange(head->r, a, b);

}

 

// Range값 a,b 범위에 있는 원소의 값을 출력하고, 카운터한다.

void BST::BstRange(node *x, int a, int b)

{

if(x != z){ // 마지막 노드까지a,b 두 범위에 속하는 원소 값을 찾는다

if(x->key >= a && x->key <= b){

// 범위에 속하는 값은 10개 까지만 출력한다.

if(rangecount < 10) printf("%3d", x->key);

rangecount++; // 총 개수는 계속 카운터 한다

if(x->key == a){

BstRange(x->r, a, b);

}else{

BstRange(x->l, a, b);

BstRange(x->r, a, b);

}

}else if(x->key < a){

// 노드의 값이 a 보다 작다면 노드의 r로 다시 recursion한다

BstRange(x->r, a, b);

}else if(x->key > b){

// 노드의 값이 b 보다 크다면 노드의 l로 다시 recursion한다

BstRange(x->l, a, b);

}

}

}

 

void main()

{

BST T1(MAX);

 

itemType a[MAX];

itemType info = 0;

 

int x,y,i;

 

for(i=0; i < MAX; i++){

a[i] = (rand() % MAX) + 1;

T1.BSTinsert(a[i], info++);

}

 

for(i=0; i < MAX; i++) T1.BSTsearch(a[i]);

 

cout << "Input Range : "

cin >> x >> y; // 찾고자하는범위의두수를입력받는다

cout << "\n\nRange " << x << " " << y << " 에속하는원소의값: "

T1.BstRange(x, y); // 입력받은두수를BstRange로보낸다

cout << "\n\nRange " << x << " " << y_

_ << " 에속하는원소의개수: " << rangecount << "\n\n\n"

 

}

 

▣ 결과 출력

 

 

 

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습8  (0) 2010.02.15
알고리즘(Algorithm) 실습7  (0) 2010.02.15
알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15
알고리즘(Algorithm) 실습4  (0) 2010.02.15
알고리즘(Algorithm) 실습3  (0) 2010.02.15

알고리즘(Algorithm) 실습3

Posted by Patchman
2010.02.15 14:34 Univ Study/알고리즘과 실습

3-1. 다음에 주어진 postfix 표기의 수식을 입력하여 스택을 사용해서 이진 parse 트리로 표현하고, 이 트리를 INORDER 트래버설한 결과를 출력하시오.

 

#include<iostream>

using namespace std;

 

typedef struct node* itemType; // node 구조체 선언

 

void traverse(struct node *t); // inorder traverse 함수 선언

void visit(struct node *t); // 출력 함수

 

class Stack // 트리 자료의 저장을 위한 스택 Class

{

private:

itemType *stack;

int p;

 

public:

 

Stack(int max=100) // Stack Class의 생성자

{stack = new itemType[max]; p=0;}

 

~Stack() // Stack Class의 소멸자

{delete stack;}

 

inline void push(itemType v) // 스택에 Data를 Push 한다

{stack[p++] = v;}

 

inline itemType pop() // 가장 최근에 Push된 Data를 Pup한다.

{return stack[--p];}

 

inline int empty() // 스택의 empty 체크

{return !p;}

 

};

 

struct node // node 구조체 함수 (Data가 저장될 info와, 트리의 left, right 노드)

{

char info; struct node *l, *r;

};struct node *x, *z;

void main()

{

char c; // Data가 입력된 문자형 변수 선언

 

Stack stack(50); // Stack Class 선언

 

z = new node; // x노드 출력시 하위노드 유무 상태파악을 위한 z노드 생성

z->l = z;

z->r = z;

 

while((c = cin.get()) != '\n') // 사용자의 엔터(next line)키가 입력되기 전까지

반복문 실행

{

while(c == ' ') cin.get(c); // 공백(스페이스)으로 다음input을 구분

 

x = new node; // 스택에 저장될 x 노드 생성

x->info = c; // x노드에 입력된 값을 넣는다

x->l = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

x->r = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

 

if(c=='+' || c=='*') // ‘+’,‘*’연산자의 경우 스택에 저장된 값을 꺼내

{ 오른쪽과, 왼쪽노드에 위치 시킨다(트리)

x->r = stack.pop();

x->l = stack.pop();

}

stack.push(x); // 스택에 x노드를 push한다.

}

traverse(x); // 스택에 저장이 완료된 x노드 트리를 traverse함수로 보낸다

}

 

void traverse(struct node *t)

{

if(t != z) // z노드와 비교하여 하위노드 유무를 확인한다

{

traverse(t->l); // left노드를 다시 taverse() 재귀호출한다.

visit(t); // 출력을 위하여 visit() 함수 호출

traverse(t->r); // right노드를 다시 taverse() 재귀호출한다.

}

}

void visit(struct node *t)

{

cout << t->info << " " // 전달받은 노드의 값(info)을 출력

}

 

 

▣ 결과 출력


- Input Data : A B C + D E * * F + *

- Output Data : A * B + C * D * E + F

 

 

 

 

 

 

3-2. 3-1에서 만들어진 트리에 대해서 큐를 사용하여 lever order로 트래버설한 결과를 출력하는 프로그램을 완성하고 실습하시오.

 

#include<iostream>

using namespace std;

 

typedef struct node* itemType; // node 구조체 선언

 

void levelOrderTraverse(struct node *t) // leverOrderTraverse 함수 선언

void visit(struct node *t); // 출력 함수

 

class Stack // 트리 자료의 저장을 위한 스택 Class

{

private:

itemType *stack;

int p;

 

public:

 

Stack(int max=100) // Stack Class의 생성자

{stack = new itemType[max]; p=0;}

 

~Stack() // Stack Class의 소멸자

{delete stack;}

 

inline void push(itemType v) // 스택에 Data를 Push 한다

{stack[p++] = v;}

 

inline itemType pop() // 가장 최근에 Push된 Data를 Pup한다.

{return stack[--p];}

 

inline int empty() // 스택의 empty 체크

{return !p;}

 

};

class Queue // leverOrderTraverse 출력을 위한 Queue Class

{

private:

 

itemType *queue;

int head; // Queue의 위치를 위한 head, tail 변수와, 원형구조를 위한 size 변수선언

int tail;

int size;

 

public:

 

Queue::Queue(int max=100) // Queue Class의 생성자

{

size = max; // 원형 구조를 위한 size변수에 max값 대입

queue = new itemType[size];

head = 0;

tail = 0;

}

 

Queue::~Queue() // Queue Class의 소멸자

{delete queue;}

 

void Queue::put(itemType v) // Queue에 데이터 입력

{

queue[tail++] = v;

if(tail > size) tail = 0;

}

 

itemType Queue::get() // Queue에 저장된 데이터 출력

{

itemType t = queue[head++];

if(head > size) head = 0;

return t;

}

 

int Queue::empty()

{return head == tail;}

 

};

struct node // node 구조체 함수 (Data가 저장될 info와, 트리의 left, right 노드)

{

char info; struct node *l, *r;

};struct node *x, *z;

void main()

{

char c; // Data가 입력된 문자형 변수 선언

 

Stack stack(50); // Stack Class 선언

 

z = new node; // x노드 출력시 하위노드 유무 상태파악을 위한 z노드 생성

z->l = z;

z->r = z;

 

while((c = cin.get()) != '\n') // 사용자의 엔터(next line)키가 입력되기 전까지

반복문 실행

{

while(c == ' ') cin.get(c); // 공백(스페이스)으로 다음input을 구분

 

x = new node; // 스택에 저장될 x 노드 생성

x->info = c; // x노드에 입력된 값을 넣는다

x->l = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

x->r = z; // 하위노드 유무 확인를 위하여 z노드를 가르키게 한다

 

if(c=='+' || c=='*') // ‘+’,‘*’연산자의 경우 스택에 저장된 값을 꺼내

{ 오른쪽과, 왼쪽노드에 위치 시킨다(트리)

x->r = stack.pop();

x->l = stack.pop();

}

stack.push(x); // 스택에 x노드를 push한다.

}

 

levelOrderTraverse(x); // 스택에 저장이 완료된 x노드 트리를

} leverOrderTraverse함수로 보낸다

 

void levelOrderTraverse(struct node *t)

{

Queue queue(50); // Queue Class 선언

queue.put(t); // 스택에 저장된 노드를 큐에 다시 입력한다.

while(!queue.empty()) // Queue의 empty 체크

{

t = queue.get(); // Queue의 노드를 꺼내 t에 저장

visit(t); // 출력을 위하여 visit() 함수 호출

if(t->l != z) queue.put(t->l); //하위노드(l)가 있다면 큐에 다시 입력

if(t->r != z) queue.put(t->r); //하위노드(r)가 있다면 큐에 다시 입력

}

}

void visit(struct node *t)

{

cout << t->info << " " // 전달받은 노드의 값(info)을 출력

}

 

 

▣ 결과 출력


- Input Data : A B C + D E * * F + *

- Output Data : * A + * F + * B C D E

'Univ Study > 알고리즘과 실습' 카테고리의 다른 글

알고리즘(Algorithm) 실습6  (0) 2010.02.15
알고리즘(Algorithm) 실습5  (0) 2010.02.15
알고리즘(Algorithm) 실습4  (0) 2010.02.15
알고리즘(Algorithm) 실습3  (0) 2010.02.15
알고리즘(Algorithm) 실습2  (0) 2010.02.15
알고리즘(Algorithm) 실습1  (0) 2009.05.05