[DataStruct 09.16] 3. 정리 셋째날-트리!!ㅋㅋ

1. Tree
 비선형 구조로서 다차원적인 구조
    정의 1. 루트(root)라는 특별한 노드를 가지는 사이클이 존재치 않는 그래(acyclic graph)
    정의 2. 하나 이상의 노드로 구성된 유한 집한

트리란 말그대로 나무를 비유해서 나타낸 것이고 거기서 나오는 용어들은 나무에 비교해보면 쉽게 알수 있다.
먼저 루뜨 가장 위에 본체를 나타내며 근본이 되는 부분이고 가지 트리구조에서는 간선이라고 불리우며 그냥 상위에서 하위로 가는 길을 나타낸다. 마지막으로 leaf 하위노드를 leaf라고 한다. 다시 자세히 용어들을 알아 보면

루트(Root) : 트리의 노드중 하나, 가장 상위레벨 노드(NODE) : 정보가 저장되는 곳, 자료구조의 원소 단말 노드(Leaf Node) : 차수가 0인 노드 or 하부에 가지가 없는 노드 비단말 노드(Non Terminal Node) : 차수가 0이 아닌 노드 부트리(Subtree) : 루트와 루트에 연결된 가지들을 제거한다ㅕㄴ 한개의 큰 트리구조는 몇개의 작은 트리구조로 나뉨 이런 트리들을 부트리라고 한다. 차수 (Degree) : 각 노드를 루트노드로 하는 부트리의 수 or 각 노드가 지닌 아래쪽 가지의 숫자 (차수= 노드수 ) 트리의 차수 각 노드의 차수중 최대치 자식노드(Child Node) : 임의의 노드에 연결된 바로 밑 레벨의 노드 이 임의의 노드는 자식 노드쪽에서 본다면 부모노드 형제노드(Sibling Node) : 동일한 부모노드를 갖는 노드 조상노드(Ancestor Node) : 루트노드에서부터 임의노드까지 path(경로)를 형성하는 노드들의 집합 후손노드(Descendant Node) : 임의의 노드를 루트로하는 부트리의 모든 노드의 집합 레벨(Level) : 루트를 최상위 레벨인 1로 하고 레벨 L인 노드의 자식노드 레벨은 L+1 부모노드(Parent Node) : 임의 노드가 연결된 레벨의 높은 노드, 자신을 파생시킨 노드 숲(Forest) : 분리된 트리들의 집합 Tree T에서 루트를 삭제한다면 3개의 부트리로 이루어진 forest

2. 링크드 리스트로 구현

struct tnode{         char data;         struct tnode *left, *right; } typedef struct tnode NODE;

3. 삽입코드

void insert(NODE *p,char ch) {         NODE *temp1,*temp2;         if(p==NULL){                p=(NODE*)malloc(sizeof(NODE));                if(p==NULL){                       //메모리 에러                 }                p->data=ch;               p->left=NULL;               p->right=NULL;        }        else{              temp1=p;             while(temp1!=NULL)             {                  temp2=temp1;                  if(temp1->data>data)                            temp1=temp1->left;                  else                           temp1=temp1->right;             }                           if(temp2->data> data){                      temp2->left=(NODE*)malloc(sizeof(NODE));                      temp2=temp2->left;                      if(temp2==NULL)                      {                               메모리 에러                               exit(0);                      }                      temp2->data=ch;                      temp->left=NULL;                      temp2->right=NULL;              }             else{                    temp2->right=(NODE*)malloc(sizeof(NODE));                    temp2=temp2->right;                    if(temp2==NULL){                                메모리에러                                           exit(0);                    }                    temp2->data=data;                    temp2->left=NULL;                    temp2->right=NULL;           }      } }

4. 삭제 코드
4.1 자식노드의 개수가 0인 경우

if(current->left==NULL&&current->right==NULL){             if(parent->left==current)                   parent->left=NULL;             else                   parent->right=NULL;            free(current); }

4.2 비 단말노드의 삭제

if(current->left!=NULL && current->right==NULL){            if(parent->left==current)                     parent->left==current->left;            else                     parent->right==current->left;            current->left=NULL;            free(current); }

4.3 오른쪽 자식 1개만 있는 경우

if(current->left == NULL &&current->right!=NULL) {        if(parent->left==current)                parent->left=current->right;        else               parent->right=current->right;        current->right=NULL;        free(current); }