[Data Structure] 이진 트리

배열로 구현한 이진트리

- 노드 i의 부모 노드 인덱스 = i/2

- 노드 i의 왼쪽 자식 노드 인덱스 = 2i

- 노드 i의 오른쪽 자식 노드 인덱스 = 2i+1

 

 

연결리스트로 구현한 이진트리

- 노드를 구조체로 표현

- 노드(데이터, 왼쪽 링크필드, 오른쪽 링크필드)

typedef int element;
typedef struct treenode {
	element data;
	struct treenode* left; // 왼쪽 노드로 연결하는 포인터
	struct treenode* right; // 오른쪽 노드로 연결하는 포인터
}treenode;

 

 

※ Example

#include <stdio.h>
#include <stdlib.h>

// 연결리스트로 구현한 이진 트리

typedef int element;
typedef struct treenode {
	element data;
	struct treenode* left; // 왼쪽 노드로 연결하는 포인터
	struct treenode* right; // 오른쪽 노드로 연결하는 포인터
}treenode;
/*
       n1(10)
  n2(20)    n3(30)
*/

int main(void) {
	treenode* n1, *n2, *n3;
	n1 = (treenode*)malloc(sizeof(treenode));
	n2 = (treenode*)malloc(sizeof(treenode));
	n3 = (treenode*)malloc(sizeof(treenode));

	n1->data = 10; n1->left = n2; n1->right = n3;
	n2->data = 20; n2->left = NULL; n2->right = NULL;
	n3->data = 30; n3->left = NULL; n3->right = NULL;
}