12주차 - 트리

< 예제 풀어보기 (13주차-1번) >

< 초기 전제 >

node* ar[9] = { NULL };  
// ar는 노드 포인터를 저장하는 배열
// 1~8번 노드 사용(노드 아이디가 1~8)로 주어지기 때문

< 노드 구조 >

typedef struct node {
	int id, data;
	struct node* left, * right;
} node;
//id는 노드의 번호, data는 노드 안의 값
//left는 노드의 왼쪽 노드의 주소, right는 노드의 오른쪽 노드의 주소

< 노드 생성하기 >

node* newnode(int id, int data) {
	node* n = (node*)malloc(sizeof(node));
	n->id = id;
	n->data = data;
	n->left = NULL;
	n->right = NULL;
	return n;
}

< 노드 초기값 넣기 >

void init_nodes(node* ar[]) {
	ar[1] = newnode(1, 20);
	ar[2] = newnode(2, 30);
	ar[3] = newnode(3, 50);
	ar[4] = newnode(4, 70);
	ar[5] = newnode(5, 90);
	ar[6] = newnode(6, 120);
	ar[7] = newnode(7, 130);
	ar[8] = newnode(8, 80);
}

< 노드 연결하기>

void connect_nodes(node* ar[]) {
	ar[1]->left = ar[2];
	ar[1]->right = ar[3];
	ar[2]->left = ar[4];
	ar[2]->right = ar[5];
	ar[3]->right = ar[6];
	ar[6]->left = ar[7];
	ar[6]->right = ar[8];
}

⭐️ 의사코드 -> c언어 코드가 되는 과정에 집중

< 선위순회(전위순회) >

선위순회란?

[루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회하는 것

void printPreorder(node* v) {
	//본인이 null이면 종료
	if (v == NULL) return;
    //본인부터 방문
	printf(" %d", v->data); 
    //본인이 내부노드인 경우 
	if (isInternal(v)) {
    	//왼쪽 자식 방문
		printPreorder(v->left);
        //오른쪽 자식 방문
		printPreorder(v->right);
	}
}

< 중위순회 >

중위순회란?

[왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회하는 것

void printInorder(node* v) {
	//본인이 null이면 종료
	if (v == NULL) return;
    //본인이 내부노드인 경우
	if (isInternal(v)) {
    	//왼쪽 자식 방문
		printInorder(v->left); 
	}
    //본인노드 방문
	printf(" %d", v->data); 
    //본인이 내부노드인 경우
	if (isInternal(v)) {
    	//오른쪽 자식 방문
		printInorder(v->right);
	}
}

< 후위순회 >

후위순회란?

[왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회하는 것

void printPostorder(node* v) {
	//본인이 null이면 종료
	if (v == NULL) return;
    //본인이 내부노드인 경우
	if (isInternal(v)) {
    	//왼쪽 자식 방문
		printPostorder(v->left);
        //오른쪽 자식 방문
		printPostorder(v->right);  
	}
    //본인노드 방문
	printf(" %d", v->data);       
}

참고 ) isInternal함수

//내부 노드인지 확인
int isInternal(node* root) {
	return root->left != NULL || root->right != NULL;
}

질문사항 있으면 언제든 질문해주세용....👍