이진 트리 만들기

1. 배열로 이진 트리 만들기

#include <iostream>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

typedef struct Node {
	int left;
	int right;
};

Node tree(1000001);

int main() {
	fastio;

	int parent , child;
	int root = -1;

	while (1) {
		cin >> child;
		if (root == -1) {
			root = child;
			continue;
		}

		parent = root;

		while (1) {
			if (트리의 오른쪽으로 가는 조건) {
				if (tree(parent).right) {
					parent = tree(parent).right;
				}
				else {
					tree(parent).right = child;
					break;
				}
			}
			else { 트리의 왼쪽으로 가는 조건
				if (tree(parent).left) { 
					parent = tree(parent).left;
				}
				else {
					tree(parent).left = child;
					break;
				}
			}
		}
	}

}

• 위의 이진 트리는 인덱스 값 = 데이터인 트리입니다. tree(5)는 값이 5인 노드를 의미합니다. 인덱스와 데이터를 구분하려면 노드 구조에 int 데이터를 추가하여 생성해야 합니다.
• 인덱스 = 데이터로 트리를 만들었기 때문에 모든 노드의 데이터 값은 양수입니다.
• 하위 노드에서 상위 노드에 액세스할 수 없습니다. 부모 노드는 좌우 자식 정보를 담고 있지만 자식 노드는 부모에 대한 정보를 저장하는 부분이 없습니다.
• 부모 노드에 대한 정보를 자식 노드에 저장하려면 int 부모 배열을 만들어 저장해야 합니다.
• children(left, right)의 값이 0이면 자식이 없음을 의미합니다.
• 자식이 들어갈 때마다 루트 노드부터 시작하여 노드가 들어가는 위치를 찾습니다.