1. Tree ��
2. Binary Tree
3. Binray Tree �� 표��
4. Binary Tree Traversal
5. Binary Search Trees (�� 탐�� 트��)
6. Insert x
7. Delete x(�� 함)
8. Tree�� (Cross Reference 할�� 했�� 형��. C++�� -.-)

1. Tree �� ¶

Node : ��
Root : ��
Edge : ��
Degree : �� Edge��
Parent : ��
Child : ��
Level : ��?
Sibling : 형��(�� ) ��
Height : Maximum Level

2. Binary Tree ¶

�� 0 - 2��
�� , ��
�� k�� = 2^k - 1
�� i�� = 2^(i-1)
n0�� , n2�� Degree�� 2�� 하�� n0 = n2 + 1 �� 한��.

3. Binray Tree �� 표�� ¶

��
- �� . ��트, �� , �� .. �� .
- �� 할��
  - Left Child : �� * 2
  - Right Child : �� * 2 + 1
  - Parent : ��/2 -> ��
Linked List
- �� 키�� 크, �� 키�� 크�� .

4. Binary Tree Traversal ¶

PreOrder : Root -> Left Child -> Right Child : ��파�� 하��

~cpp 
PreOrder(a) 
{
    if(a)
    {
        visit a
        Preorder(a->left)
        Preorder(a->right)
    }
}

InOrder : Left Child -> Root -> Right Child : �� 한 ��

~cpp 
InOrder(a) 
{
    if(a)
    {
        InOrder(a->left)
        visit a
        InOrder(a->right)
    }
}

PostOrder : Left Child -> Right Child -> Root

~cpp 
PostOrder(a) 
{
    if(a)
    {
        PostOrder(a->left)
        PostOrder(a->right)
        visit a
    }
}

LevelOrder : ��

~cpp 
AddQ(Root)
while(1)
{
    a = DeleteQ();
    Visit a;
    if(!a) break;
    if(a->left) AddQ(a->left)
    if(a->right) AddQ(a->right)
}

5. Binary Search Trees (�� 탐�� 트��) ¶

�� 탐�� 하�� .(��?--;)
- �� 탐�� : θ(n)
- �� 탐�� : θ(log2 n) - 2�� . �� 표��하�� ?--;
- n�� 한 2048�� 하�� 탐�� 2048�� 탐�� 11��
- but, �� 탐�� . �� . �� ..--;
��
- Binray Search Tree �� 히 Binary Tree �� 한��.
- Keys in Left Subtree < Keys of Node
- Keys in Right Subtree > Keys of Node(�� 한�� .)
��
- Search x => Compare with Root
  - if x = Root's Key then ��
  - else if x > Root's Key Root�� Right Subtree�� Root�� 팅. ��
  - else if x < Root's Key Root를 Left Subtree의 Root로 셋팅. 거기서부터 검색 다시 시작

6. Insert x ¶

��트�� 크�� .

7. Delete x(�� 함) ¶

Search x
- �� x�� leaf(�� ) - �� ..--;
- x�� Child�� 1�� - �� . �� 할�� .(�� ?--;)
- x�� Child�� 2�� - �� Left Subtree�� 큰 �� . �� y�� 하�� y�� Child�� . y�� x��
  - y�� Child �� - �� .
  - y�� Child �� - �� 한�� .. �� 할��

8. Tree�� (Cross Reference 할�� 했�� 형��. C++�� -.-) ¶

~cpp 
// 트������ ���한 함������

void init(Node** node,char* ch)			// ������화
{
	(*node)->pLeft = (*node)->pRight = NULL;	// ������ ��������� ������ NULL���
	(*node)->Data = new char[strlen(ch) + 1];	// ��������� ����������� 할���
	strcpy((*node)->Data,ch);			// ��������� ��������� ������
}

void PrintandDelete(Node* root)			// ��� ������������ ���회(Preorder������?)
{
    if( root->pLeft )		
        Print( root->pLeft );

    cout << root->Data << endl;

    if( root->pRight )
        Print( root->pRight );

    delete root;					// 할������ ������ ������
}

int Add(Node** root,char* ch)
{
    if(!(*root))					// ������������ ���������
    {
        *root = new Node;				// 할���
        init(root,ch);		   	         // ������화
        return 1;
    }
	
    else if(strcmp((*root)->Data,ch)>0)		// ��������� ������������ 크��� ��������� ������
	return add(&((*root)->pLeft),ch);
    else if(strcmp((*root)->Data,ch)<0)		// ��������� ������������ ��������� ������������ ������
	return add(&((*root)->pRight),ch);
    else if(strcmp((*root)->Data,ch)==0)		// ��������� ��������� ������
	return 1;
}

DataStructure

Data Structure/Tree

Contents

1. Tree �� ¶

2. Binary Tree ¶

3. Binray Tree �� 표�� ¶

4. Binary Tree Traversal ¶

5. Binary Search Trees (�� 탐�� 트��) ¶

6. Insert x ¶

7. Delete x(�� 함) ¶

8. Tree�� (Cross Reference 할�� 했�� 형��. C++�� -.-) ¶

Data Structure/Tree

Contents

1. Tree ������ ��������� ¶

2. Binary Tree ¶

3. Binray Tree ��� 표�� ¶

4. Binary Tree Traversal ¶

5. Binary Search Trees (������������ ������ 탐��� 트���) ¶

6. Insert x ¶

7. Delete x(������ ������ ������함) ¶

8. Tree��� ��������� ������ ���������(Cross Reference 할��� 했������ ������ ���형���������. C++������������ ���������-.-) ¶

1. Tree �� ¶

3. Binray Tree �� 표�� ¶

5. Binary Search Trees (�� 탐�� 트��) ¶

7. Delete x(�� 함) ¶

8. Tree�� (Cross Reference 할�� 했�� 형��. C++�� -.-) ¶