트리 순회법
- 트리 순회 방법에는 3가지가 있다.
- 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)


전위 순회법(Preorder Traversal)

1. 루트 노드부터 시작해서 아래로 내려 오면서
2. 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면
3. 오른쪽 하위 트리를 방문하는 방식



중위 순회법(Inorder Traversal)

- 트리는 하위 트리의 집합이라고 할 수 있고 하위 트리 역시 또 다른 하위 트리의 집합이라고 할 수 있다.
- 따라서 아래와 같은 방법으로 탐색할 수 있다.
1. 왼쪽 하위 트리부터 시작해서
2. 루트를 거쳐
3. 오른쪽 하위 트리를 방문하는 방법

 - 응용 사례 : 수식 트리(Expression Tree), 중위 표기식
- (1 * 2) + (7 - 8)을 수식 트리로 표현하면 다음 그림과 같이 나타낼 수 있다.



후위 순회법(Postorder Traversal)

- 전위 순회의 반대
1. 왼쪽 하위 트리부터 시작해서
2. 오른쪽 형제 노드를 방문 후
3. 루트 노드를 방문하는 방법.

 - 응용 사례 : 후위 표기식. 후위 순회법을 통해 출력되는 노드를 살펴보면 후위 표기식으로 나타난다.
- 1 2 * 7 8 - +


출처 : http://warmz.tistory.com/619


다음은 순회를 적용한 간단 이진 트리 예제입니다.

가장 핵심은 void DeleteTree(BTreeNode * bt)함수인데 이 함수는 모든 트리 노드를 삭제하는 역할을 합니다.

이때 후위 순회를 이용한다는 점이 가장 중요합니다.


BinaryTree.h


#ifndef __BINARY_TREE_H__

#define __BINARY_TREE_H__


typedef int BTData

typedef struct _bTreeNode{

        BTData data

        struct _bTreeNode *left

        struct _bTreeNode *right


}BTreeNode


BTreeNode * MakeBTreeNode(void);//빈노드생성함수

BTData GetData(BTreeNode * bt);//bt의data 반환함수

void SetData(BTreeNode * bt, BTData data);//bt의data에입력받은data로세팅


BTreeNode * GetLeftSubTree(BTreeNode * bt);//왼쪽서브트리를가져옴

BTreeNode * GetRightSubTree(BTreeNode * bt);//오른쪽서브트리를가져옴


void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub);//왼쪽서브트리를만듬

void MakeRightSubTree(BTreeNode * main,BTreeNode * sub);//오른쪽서브트리를만듬


void DeleteTree(BTreeNode * bt);


typedef void (*VisitFuncPtr)(BTData data);//함수포인터를쉽게쓰기위해서typedef를함


void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action);//전위순회함수

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action);//중위순회함수

void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action);//후위순회함수


#endif


BinaryTree.c


#include <stdio.h>

#include <stdlib.h>

#include "BinaryTree.h"


BTreeNode * MakeBTreeNode(void){

        BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

        nd->left = NULL

        nd->right = NULL

        return nd

}

BTData GetData(BTreeNode * bt){

        return bt->data

}

void SetData(BTreeNode * bt, BTData data){

        bt->data = data

}


BTreeNode * GetLeftSubTree(BTreeNode * bt){

        return bt->left

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

        return bt->right

}


void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub){

        if(main->left != NULL)

                free(main->left);

        

        main->left = sub

}

void MakeRightSubTree(BTreeNode * main,BTreeNode * sub){

        if(main->right != NULL)

                free(main->right);

        

        main->right = sub     

}

//전위순회

void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action){

        if(bt== NULL)

                return


        action(bt->data);//부모먼저출력하고

        PreorderTraverse(bt->left, action);//왼쪽출력

        PreorderTraverse(bt->right, action);//오른쪽출력


}

//중위순회

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action){

        if(bt == NULL)

                return


        InorderTraverse(bt->left, action);//왼쪽먼저출력하고

        action(bt->data);//부모를중간에출력해서중위임

        InorderTraverse(bt->right, action);//오른쪽출력


}

//후위순회

void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action){

        if(bt == NULL)

                return


        PostorderTraverse(bt->left, action);//왼쪽부터출력

        PostorderTraverse(bt->right, action);//오른쪽출력

        action(bt->data);//마지막에부모를출력해서후위임


}


void DeleteTree(BTreeNode * bt){

        if(bt == NULL)

                return

        

        DeleteTree(bt->left);

        DeleteTree(bt->right);

        printf("del data : %d \n",bt->data);

        free(bt);


}


main.c


#include <stdio.h>

#include "BinaryTree.h"


void ShowIntData(int data);


int main(){

        BTreeNode * bt1 = MakeBTreeNode();//노드bt1 생성

        BTreeNode * bt2 = MakeBTreeNode();

        BTreeNode * bt3 = MakeBTreeNode();

        BTreeNode * bt4 = MakeBTreeNode();

        

        SetData(bt1, 1);//bt1에데이터저장

        SetData(bt2, 2);//bt2에데이터저장

        SetData(bt3, 3);//bt3에데이터저장

        SetData(bt4, 4);//bt4에데이터저장


        MakeLeftSubTree(bt1, bt2);//bt2를bt1의왼쪽자식으로

        MakeRightSubTree(bt1, bt3);//bt3를bt1의오른쪽자식노드로

        MakeLeftSubTree(bt2, bt4);//bt4를bt2의왼쪽자식노드로


        PreorderTraverse(bt1, ShowIntData);

        printf("\n");

        InorderTraverse(bt1, ShowIntData);

        printf("\n");

        PostorderTraverse(bt1, ShowIntData);

        printf("\n");


        DeleteTree(bt1);

        printf("\n");

        //PostorderTraverse(bt1, ShowIntData);


        return 0;

}


void ShowIntData(int data){


        printf("%d ", data);

}


출력 화면


블로그 이미지

가카리

소프트웨어와 하드웨어 프로그래밍, 취업 및 직장생활 전문 블로그

오늘은 함수포인터에 대해서 포스팅을 하도록 하겠습니다.


포인터가 무엇인지는 다들 아실텐데요, 특정 변수에 대한 메모리 주소를 담을 수 있는 변수를 포인터 변수라고 합니다. 그렇다면 함수포인터란, 특정 함수에 대한 메모리 주소를 담을 수 있는 것 이라고 정의할 수 있겠습니다.


함수포인터를 쓰는 이유는 무엇일까요?

 1. 프로그램 코드가 간결해집니다.

 2. 함수포인터를 배열에 담아서도 사용할 수 있으므로 중복되는 코드를 줄일 수 있습니다.

 3. 상황에 따라 해당되는 함수를 호출할 수 있으므로 굉장히 유용합니다.

그 외에도 함수 포인터를 이용하여 콜백함수를 구현할 수 있게 되는 등 편리하고 유용한 코드를 작성할 수 있게 됩니다.



우선 함수포인터의 모양에 대해 알아보도록 하겠습니다.

int (*FuncPtr) (int, int)


함수포인터는 위와 같은 모양을 띕니다. 함수의 프로토타입 선언과 모양이 비슷하죠?

함수의 프로토타입과 다른점이 있다면 함수 이름앞에 포인터를 가르키는 *이 붙는 다는 것인데요. 이렇게 선언이 되게 되면 FuncPtr 이라는 함수의 주소를 담을수 있는 '변수'가 생기는 것입니다.

이 FuncPtr 함수포인터가 담을 수 있는 함수는 위와 같은 모양을 띄어야 합니다. 즉, 함수의 리턴형은 int 여야하고, int형 파라미터 2개를 받는 함수여야 하는 것입니다.


예를 들어,

1:int add (int first, int second)

2: doublediv (double first, double second)

위의 보이는 두 함수가 있다고 가정할 때, 함수포인터의 선언 모양과 똑같이 생긴 add 라는 함수의 주소만을 담을 수 있는 것입니다.


아래의 사용 예제를 한 번 더 보시겠습니다.

?

1

2

3

4

FuncPtr = add (o)

FuncPtr = &add (o)

FuncPtr = div(x)

FuncPtr = add() (x)


1, 2 : 2가지 방법 모두 괜찮은 사용 방법입니다. 어떤 것을 쓰셔도 무관합니다.
3 : div는 FuncPtr의 선언 모양과 프로토타입이 달라서 사용할 수 없습니다. 에러가 발생합니다.
4 :add() 처럼 함수를 호출할 때 처럼 쓰는 것은 결과값이 함수의 호출 이후 리턴 값이 되는 것입니다. 따라서 add() 는 int형을 가리키게 되는 것이므로 사용방법 자체가 잘 못 되었습니다. 에러가 발생합니다.



이렇듯 함수포인터는 담고 싶은 함수의 프로토타입을 따라 선언하여 사용하시면 됩니다. 하지만, 이 모양이 복잡하기 때문에 typedef를 이용하여 타입의 모양을 단순화 시키는 작업을 해 줄수도 있습니다.

typedef int (*FuncPtr)(int, int)


프로그램 상단에 위와 같이 선언한 후, 실제 사용을 하실 때에는 FuncPtr 이라는 Type으로 새로운 변수를 사용하실 수 있습니다.


?

1

2

FuncPtr testFP = NULL;

testFP = add;


이렇게 말이죠. 아, 참고로 모든 변수 특히 포인터 변수를 선언해 주실 때, 초기화 해주는 습관은 정말 좋은 습관이십니다 :) 크리티컬 에러를 미리 예방할 수 있는 방법 중 하나입니다.



자 이제 마지막으로, 함수포인터를 이용해서 만든 실제 예제를 한 번 보여드리도록 하겠습니다.


?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

#include <stdio.h>

// 함수포인터 타입 정의

typedefint(*calcFuncPtr)(int, int);

// 덧셈 함수

intplus (intfirst, intsecond)

{

returnfirst + second;

}

// 뺄셈 함수

intminus (intfirst, intsecond)

{

returnfirst - second;

}

// 곱셈 함수

intmultiple (intfirst, intsecond)

{

returnfirst * second;

}

// 나눗셈 함수

intdivision (intfirst, intsecond)

{

returnfirst / second;

}

// 매개변수로 함수포인터를 갖는 calculator 함수

intcalculator (intfirst, intsecond, calcFuncPtr func)

{

returnfunc (first, second); // 함수포인터의 사용

}

intmain(intargc, char** argv)

{

calcFuncPtr calc = NULL;

inta = 0, b = 0;

charop = 0;

intresult = 0;

scanf("%d %c %d", &a, &op, &b);

switch(op) // 함수포인터 calc에 op에 맞는 함수들의 주소를 담음

{

case'+':

calc = plus;

break;

case'-':

calc = minus;

break;

case'*':

calc = multiple;

break;

case'/':

calc = division;

break;

}

result = calculator (a, b, calc);

printf("result : %d", result);

return0;

}


실행결과는 다음과 같습니다.


간단한 소스코드라 어려운 점은 없을 겁니다. 혹시 코드에 이해 안가는 부분이 있다면 댓글 남겨주시면 바로 답변 드립니다


출처 : http://norus.tistory.com/8

블로그 이미지

가카리

소프트웨어와 하드웨어 프로그래밍, 취업 및 직장생활 전문 블로그

다음은 간단한 이진트리의 예제이며 단순히 공간을 만들고 메인 함수에서 수동적으로 왼쪽과 오른쪽으로 나누고 값을 넣어주는 예제입니다.


BinaryTree.h


#ifndef __BINARY_TREE_H__

#define __BINARY_TREE_H__


typedef int BTData

typedef struct _bTreeNode{

        BTData data

        struct _bTreeNode *left

        struct _bTreeNode *right


}BTreeNode


BTreeNode * MakeBTreeNode(void);//빈노드생성함수

BTData GetData(BTreeNode * bt);//bt의data 반환함수

void SetData(BTreeNode * bt, BTData data);//bt의data에입력받은data로세팅


BTreeNode * GetLeftSubTree(BTreeNode * bt);//왼쪽서브트리를가져옴

BTreeNode * GetRightSubTree(BTreeNode * bt);//오른쪽서브트리를가져옴


void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub);//왼쪽서브트리를만듬

void MakeRightSubTree(BTreeNode * main,BTreeNode * sub);//오른쪽서브트리를만듬


#endif


BinaryTree.c


#include <stdio.h>

#include <stdlib.h>

#include "BinaryTree.h"


BTreeNode * MakeBTreeNode(void){

        BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

        nd->left = NULL

        nd->right = NULL

        return nd

}

BTData GetData(BTreeNode * bt){

        return bt->data

}

void SetData(BTreeNode * bt, BTData data){

        bt->data = data

}


BTreeNode * GetLeftSubTree(BTreeNode * bt){

        return bt->left

}

BTreeNode * GetRightSubTree(BTreeNode * bt){

        return bt->right

}


void MakeLeftSubTree(BTreeNode * main,BTreeNode * sub){

        if(main->left != NULL)

                free(main->left);

        

        main->left = sub

}

void MakeRightSubTree(BTreeNode * main,BTreeNode * sub){

        if(main->right != NULL)

                free(main->right);

        

        main->right = sub     

}


main.c


#include <stdio.h>

#include "BinaryTree.h"


int main(){

        BTreeNode * bt1 = MakeBTreeNode();//노드bt1 생성

        BTreeNode * bt2 = MakeBTreeNode();

        BTreeNode * bt3 = MakeBTreeNode();

        BTreeNode * bt4 = MakeBTreeNode();

        

        SetData(bt1, 1);//bt1에데이터저장

        SetData(bt2, 2);//bt2에데이터저장

        SetData(bt3, 3);//bt3에데이터저장

        SetData(bt4, 4);//bt4에데이터저장


        MakeLeftSubTree(bt1, bt2);//bt2를bt1의왼쪽자식으로

        MakeRightSubTree(bt1, bt3);//bt3를bt1의오른쪽자식노드로

        MakeLeftSubTree(bt2, bt4);//bt4를bt2의왼쪽자식노드로

        

        printf("%d \n", GetData(GetLeftSubTree(bt1)));


        printf("%d \n", GetData(GetLeftSubTree(GetLeftSubTree(bt1))));

        

        return 0;

}



출력화면



블로그 이미지

가카리

소프트웨어와 하드웨어 프로그래밍, 취업 및 직장생활 전문 블로그

 

 

#include <string>

#include <iostream>

using namespace std;

int main()

{

         // 생성및 초기화

         string str1 = "ABCDE";

         string str2("FGH");

 

         string str3 = str2;

         string str4 = str1 + str2;

 

         cout << "str1= " << str1 << endl;

         cout << "str2= " << str2 << endl;

         cout << "str3= " << str3 << endl;

         cout << "str4= " << str4 << endl;

 

         //string 객체생성시, 인자로 문자를 지정할수는 없다.

         // char ch = 'A';

         // string str6 = ch;  //에러발생

         // string str7 = 'A'; //에러발생

         // string str8('A');  //에러발생

 

         string str8(1, 'A');  //한문자 대입은 이렇게합니다.

         string str9(str1, 2, 3);// 2번째 인덱스에서 시작하여, 3개의 단어를 대입

         cout << "str8= " << str8 << endl;

         cout << "str9= " << str9 << endl;

 

         // 길이

         string str10 = "Hello";

         string::size_type len;

         len = str10.length();

         cout << "length()= " << len << endl;

         len = str10.size();

         cout << "size()= " << len << endl;

 

         // c_str

         string str11 = "Good Job";

         char arr[15];

         strcpy(arr, str11.c_str()); // string객체에서, char 문자열 포인터로 변환은 c_str()함수로..

         cout << "arr= " << arr << endl;

 

         // insert

         string str12 = "abcdefghi";

         string str13 = "0123";

         str12.insert (3,str13); //3번째 인덱스에 str13 문자열을 삽입

         cout << "str12= " << str12 << endl; // "abc0123defghi"

 

         // erase

         string str14 = "123456";

         str14.erase (2, 3); //2번째 인덱스부터, 3개의 문자를 삭제

         cout << "str14= " + str14 << endl;

 

         // replace

         string str15 = "abcdefghi";

         string str16 = "123";

         str15.replace (4,2,str16);//4번째 인덱스부터, 2개의 문자를 str16문자열로 대체..

         cout << "str15= " + str15 << endl;

 

         // find, rfind

         string str17 = "abcdefghi";

         string str18 = "cde";

         string::size_type pos = str17.find (str18, 0); //0번째 인덱스부터, "cde" 일치하는 시작위치를 리턴

         cout << "Position of find is " << pos << endl; // 2  

         pos = str17.find ("123",0);

         if (pos == string::npos)

                  cout << "Not found" << endl;

 

         pos = str17.rfind (str18, str17.length()-1); //str17 마지막 인덱스부터, 뒤에서 검색하며, 맨처음 일치하는 위치를 리턴

         cout << "Position of rfind is " << pos << endl; // 2

 

         // find_first_of, find_last_of

         string str20 = "Hello Codein";

         string str21 = "abcde";

         pos = str20.find_first_of (str21, 0); //0번째 인덱스부터, str21 문자열중 하나의 문자라도 일치하는 위치를 리턴

         cout <<  "Position of find_first_of is " << pos << endl; // 1

         pos = str20.find_last_of ("abcde"); // str20 마지막 인덱스부터, 뒤에서 검색하며, 맨처음 일치하는 위치를 리턴

         cout << "Position of find_last_not_of is " << pos << endl; // 11

 

 

         // substr

         string str22 = "123456789";

         string str23 = str22.substr (6,2); //6번째 인덱스부터, 2개의 문자를 취해서 리턴

         cout << "substr()= " << str23 << endl; // "78"

 

         // 연산자(=, +, +=, ==, <<, >>, [])

         // "=" (= 연산자를 사용하여, 다른 string 객체의 문자열을 대입가능)

         string s1 = "Hello";

         string s2;

         s2 = s1;

         cout << "s1= " << s1 << ", s2= " << s2 << endl;

 

         string s3;

         s3 = "Codein!!"; // 직접 문자열을 대입가능

         cout << "s3= " << s3 << endl;

 

         string s4;

         char ch2 = 'C';

         s4 = ch2; //문자 대입가능 (생성시, 대입은 허용되지 않음, string s4 = 'C': 잘못됨)

         s4 = 'A';

 

         // "+" 연산자

         // 두개의 string 객체에 "+" 연산자를 사용하여 연결가능

         string s5 = "Hello ";

         string s6 = "Korea";

         string s7 = s5 + s6; // "Hello Korea"

         cout << "s7= " << s7 << endl;

 

         // 하나의 string 객체와 직접문자열을 "+" 연산자를 사용하여 연결가능

         string s8 = "Hello ";

         string s9 = s8 + "Mr Chin";

         cout << "s9= " << s9 << endl;

 

         // 하나의 string 객체와 문자를 "+" 연산자를 사용하여 연결가능

         string s10 = "Hello ";

         string s11 = s10  + '!';

         cout << "s11= " << s11 << endl;

 

         // "+=" 연산자

         string s12 = "Hello ";

         s12 += "*^^*";

         cout << "s12= " << s12 << endl;

 

         // "<<" 연산자

         // string 객체를 출력스트림으로 전송

         string s13 = "How are you?";

         cout << s13 << endl;

 

         // ">>" 연산자

         // 입력스트림으로 부터 문자열을 읽어서 string 객체에 저장

         string s14;

         cout << "입력후 엔터키를 눌러주세요" <<endl;

         cin >> s14;

 

         // [] 연산자

         // [] string 객체내 하나의 문자에 접근할수 있도록 해줌

         string s15 = "abcdef";

         char ch3 = s15[3];

         cout << "ch3= " << ch3 << endl;

         s15[2] = 'Z';

         cout << "s15= " << s15 << endl;

 

         return 1;

}

 

실행결과:

 

 

 

 

 

 

블로그 이미지

가카리

소프트웨어와 하드웨어 프로그래밍, 취업 및 직장생활 전문 블로그

Tag c, c++