[개념] 3.이진트리와 순회

이진트리(Binary Tree)란?

가장 많이 사용되는 *비선형 자료구조로, 데이터의 탐색 속도 빠르게 하기 위한 구조

*선형 자료구조의 경우: 배열, 스택, 큐가 해당

 

이진트리에서 데이터 탐색하는 방법 3가지

*가운데 노드가 어디에 위치하느냐로 구분하기

1. 전위순회 (가운데 노드가 맨앞)

2. 중위순회 (가운데 노드가 중간)

3. 후위순회 (가운데 노드가 맨뒤)

 

*Class와 Struct 차이

-구조체에서 함수 추가한게 클래스 =>구조체가 클래스보다 하위계층

 

#include<iostream>
using namespace std;
int number = 15;
typedef struct node *treePointer;
typedef struct node{
    int data;
    treePointer leftChild, rightChild;
}Node;
//전위순회
void preorder(treePointer ptr){
    if(ptr){
        cout<<ptr->data<<" ";
        preorder(ptr->leftChild);
        preorder(ptr->rightChild);
    }
}
//중위순회
void inorder(treePointer ptr){
    if(ptr){
        inorder(ptr->leftChild);
        cout<<ptr->data<<" ";
        inorder(ptr->rightChild);
    }
}
//후위순회
void postorder(treePointer ptr){
    if(ptr){
        postorder(ptr->leftChild);
        postorder(ptr->rightChild);
        cout<<ptr->data<<" ";
    }
}
int main(){
    Node nodes[number+1];
    for(int i=1; i<=number;i++){
        nodes[i].data = i;
        nodes[i].leftChild = NULL;
        nodes[i].rightChild = NULL;
    }
 
    for(int i=1; i<=number;i++){
        if(i%2==0){
            nodes[i/2].leftChild = &nodes[i];
        }else
        {
            nodes[i/2].rightChild = &nodes[i];
        }
        
    }
    preorder(&nodes[1]);
    cout<<"\n";
    postorder(&nodes[3]);
    cout<<"\n";
    inorder(&nodes[2]);
}

 

**나동빈님 강의 정리하면서 공부한 내용입니다.

https://youtu.be/z_tzHoPfllA

 

|본 포스팅은 쿠팡 파트너스의 일환으로 소정의 수수료를 제공받을 수 있음을 알립니다 |