7-2 이진 트리의 구현,연산, 변환

04. 이진 트리의 구현

배열을 이용한 이진 트리의 구현

- 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적임

- 트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하여 낭비가 심해짐

포인터를 이용한 이진 트리의 구현

- 포인터를 이용한 이진 트리의 노드 생성

struct node{
	struct node* left;
	struct node* right;
	int info;
}

연결 리스트로 구현

 

 

 

 

05. 이진 트리 연산

이진 트리의 순회

- 이진 트리의 각 노드를 ( 빠짐없이 그리고 중복없이) 한 번씩 방문하는 것

 

이진 트리의 전위 순회

루트노드- 왼쪽 자식노드 - 오른쪽 자식노드

이진 트리의 후위 순회

왼쪽 자식노드 - 오른쪽 자식 노드 루트 노드

이진트리의 중위 순회

왼쪽 자식 노드 - 루트노드 - 오른쪽 자식 노드

 

이진 트리의 순회 알고리즘

- 전위 순회(PLR)

struct node *nodeptr ;
void preorder(struct node *tree_ptr){
  if(tree_ptr){
	printf("%d",tree_ptr->info);
	preorder(tree_ptr->left);
	preorder(tree_ptr->right);	}	}

- 중위 순회(LPR)

struct node* nodeptr ;
void inorder(struct node *tree_ptr){
  if(tree_ptr){
	inorder(tree_ptr->left);
	printf("%d",tree_ptr->info);
	inorder(tree_ptr->right);   }	}

- 후위 순회(LRP)

 

struct node *nodeptr ;
void postorder(structnode*tree_ptr){
  if(tree_ptr){
	postorder(tree_ptr->left);
	postorder(tree_ptr->right);
	printf("%d",tree_ptr->info);	}	}

 

이진 트리의 생성/삽입/삭제

- 일반적인 이진 트리를 생성하는 것은 (이중) 연결 리스트 연산을 사용함

- 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 (이중) 연결 리스트의 삽입 연산을 사용함

 

- 노드를 삭제할 때, 삭제하려는 노드가 리프노드인 경우는 해당 노드를 가리키는 포인터를 null로 지정하면 됨

- 리프노드가 아닌 경우에는 삭제하려는 노드의 자식노드에 대한 처리를 추가로 해주어야 함

 

이진 트리의 노드 개수 세는 연산

int get_node_count(nodeptr *root){
	if(root==null)return0;
	int result=1;
	result = get_node_count((nodeptr*)root->left)
	+
		get_node_count((nodeptr*)root->right);
returnresult;	 }

Int get_leaf_count(nodeptr *root){
	int result=0;
	if(root==null){
		return0;
	}elseif(root->left==null&&root->right==null){
		return1; }
	result=get_leaf_count((nodeptr*)root->left)
		+
		get_leaf_count((nodeptr*)root->right);
	returnresult;	}

 

 

06. 일반 트리를 이진 트리로 변환

이진 트리로 변환 방법

일반 트리에 대하여 각 노드의 형제들을 연결

-> 각 노드에 대하여 가장 왼쪽 릉크만 남기고 모두 제거

 

루트노드는 반드시 왼쪽 자식노드 하나만 갖도록 함