22-04-16 (데이터 구조)

스택 

큐

링크드리스트

---

트리

node : tree 에서 data를 저장하는 기본 단위 원소

root: 가장 상위의 한 개 node

branch : node 와 node간의 연결

 

level이 i 인 node는 최대 2^(i-1)개 이다.

height가 k인 binary tree의 최대 node 수는 (2^k -1) 개이다. 

 

 

binary Tree 를 이용한 inoder, preorder, postorder traverse

#include <iostream>
using namespace std;

class node{
public:
    string name;
    double score;
    node *left, *right;
};


//주어진 p를 root로 하는 binary tree를 inorder traverse
void inorder_traverse(node *p){
    if (p==NULL) return;
    inorder_traverse(p->left);
    cout<<p->name<<" : "<<p->score;
    inorder_traverse(p->right);
}
//주어진 p를 root로 하는 binary tree를 preorder traverse
void preorder_traverse(node *p){
    if (p==NULL) return;
    cout<<p->name<<" : "<<p->score;
    preorder_traverse(p->left);
    preorder_traverse(p->right);
}
//주어진 p를 root로 하는 Binary tree를 postorder traverse
void postorder_traverse(node *p){
    if (p==NULL) return;
    postorder_traverse(p->left);
    postorder_traverse(p->right);
    cout<<p->name<<" : "<<p->score;

}

--> 활용법

expression tree의 inorder , preorder, postorder traverse의 결과는 

해당 expression의 infix,prefix, postfix이다.

-출처 : 한동대학교-