연결리스트 이진트리

연결리스트 이진트리는 왼쪽 오른쪽 주소를 저장하는 변수만 만들어주고 오른쪽과 왼쪽에 연결만 해주면 연결리스트 이진트리를 만들 수 있다.

루트노드, 왼쪽 서브 트리, 오른쪽 서브 트리를 순차적으로 방문하는 방법들

전위 순회

루트 노드를 먼저 방문

Root → L → R

중위 순회

루트 노드를 중간에 방문

L → Root → R

후위 순회

루트 노드를 마지막에 방문

L → R → Root

이진트리 노드 수 계산

단순히 노드 하나 당 카운터 +1을 계속해서 해주면 된다.

단 카운터의 주소값을 넘겨줘야하며 재귀를 사용해야함

(노드의 오른쪽, 왼쪽 가기)

이진트리 리프(말단 정점) 수 계산

노드 수 계산과 비슷하나 말단 정점이므로 자식 노드가 없다면 카운트를 해준다.

#pragma once
#ifndef __MY_BINARY_TREE_H__
#define __MY_BINARY_TREE_H__
#include <cstdlib>
#include <cstdio>
#include <cmath>
#define MAX(X, Y) (((X)>(Y))? (X) : (Y))
typedef struct BT_Node { //연결리스트 구조체 선언
	int data;
	struct BT_Node* left;
	struct BT_Node* right;
}BT_Node;
BT_Node* BT_Create_Node(int newData) { //노드 생성하기
	BT_Node* newnode = (BT_Node*)malloc(sizeof(BT_Node));
	newnode->data = newData;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode; //노드 리턴
}
void BT_Destroy_Node(BT_Node* node) {
	if (node != NULL) { //노드 삭제하기
		free(node);
	}
}
void BT_Make_Left_Sub_Tree(BT_Node* parent, BT_Node* sub) {
	if (parent->left != NULL) { //왼쪽 노드 결합
		BT_Destroy_Node(parent->left);
	}
	parent->left = sub;
}
void BT_Make_Right_Sub_Tree(BT_Node* parent, BT_Node* sub) {
	if (parent->right != NULL) { //오른쪽 노드 결합
		BT_Destroy_Node(parent->right);
	}
	parent->right = sub;
}
void BT_Preorder_Traversal(BT_Node* node) { //전위 순회
	if (node == NULL) {
		return;
	}
	printf("%d ", node->data); //루트 노드 먼저 방문
	BT_Preorder_Traversal(node->left);
	BT_Preorder_Traversal(node->right);
}
void BT_Inorder_Traversal(BT_Node* node) { //중위 순회
	if (node == NULL) {
		return;
	}
	BT_Inorder_Traversal(node->left);
	printf("%d ", node->data); //루트 노드 중간에 방문
	BT_Inorder_Traversal(node->right);
}
void BT_Postorder_Traversal(BT_Node* node) { //후위 순회
	if (node == NULL) {
		return;
	}
	BT_Postorder_Traversal(node->left);
	BT_Postorder_Traversal(node->right);
	printf("%d ", node->data); //루트 노드 마지막에 방문
}
int BT_Count_Node(BT_Node* node, int* count) { //노드의 개수 세기
	if (node != NULL) {
		*(count) += 1;
		BT_Count_Node(node->left, count); //카운터의 주소값을 넘겨줌
		BT_Count_Node(node->right, count); //왼쪽 오른쪽 방문
	}
	return *(count);
}
int BT_Count_Leaf(BT_Node* node, int* count) { //리프 노드 개수 세기
	if (node != NULL) {
		if (node->left == NULL && node->right == NULL) { //자식 노드가 없을 때
			*(count) += 1;
		}
		BT_Count_Leaf(node->left, count);
		BT_Count_Leaf(node->right, count);
	}
	return *(count);
}
int BT_Height(BT_Node* root) { //노드 그리기
	if (root == NULL)
		return 0;
	return MAX(BT_Height(root->left), BT_Height(root->right)) + 1;
}
void BT_PrintTree2Matrix(int** M, BT_Node* bt_node, int col, int row, int height) {
	if (bt_node == NULL) return;
	M[row][col] = bt_node->data;
	BT_PrintTree2Matrix(M, bt_node->left, col - pow(2, height - 2), row + 1, height - 1);
	BT_PrintTree2Matrix(M, bt_node->right, col + pow(2, height - 2), row + 1, height - 1);
}
void BT_TreePrinter(BT_Node* root) //노드 출력하기
{
	int h = BT_Height(root);
	int col = (1 << h) - 1;
	int** M = new int* [h];
	for (int i = 0; i < h; i++) {
		M[i] = new int[col];
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < col; j++) {
			M[i][j] = 0;
		}
	}
	for (int j = 0; j < col; j++) {
		printf("==");
	}
	printf("\\n");
	BT_PrintTree2Matrix(M, root, col / 2, 0, h);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < col; j++) {
			if (M[i][j] == 0)
				printf(" ");
			else
				printf("%2d", M[i][j]);
		}
		printf("\\n");
	}
	for (int j = 0; j < col; j++) {
		printf("==");
	}
	printf("\\n");
}
#endif