#include "..\CookHeader.h"

typedef struct _TreeNode {
	struct _TreeNode* left = NULL;
	string data;
	struct _TreeNode* right = NULL;
} TreeNode;

Array <TreeNode*> memory;
TreeNode* root;    // 루트 노드 (고정)
Array <string> dataAry = { "바나나맛우유", "레쓰비캔커피", "츄파춥스", "도시락", "삼다수", "코카콜라", "삼각김밥" };

void freeMemory() { 
	for (int i = 0; i < len(memory); i++)
		delete memory[i];
}

void preOrder(TreeNode* node) {
	if (node == NULL)
		return;
	print(node->data + " ");
	preOrder(node->left);
	preOrder(node->right);
}

int main() {
	Array <string> sellAry;  // 무작위로 판매된 제품 배열
	srand(time(NULL));
	for (int i = 0; i < 20; i++) {
		int num = rand() % len(dataAry); // dataAry 중에서 하나 추출
		sellAry.push_back(dataAry[num]);
	}
	print("오늘 판매된 물건(중복O) -->");
	printArray(sellAry);

	TreeNode* node;
	TreeNode* current; // 현재 노드 작업용 (변경)

	node = new TreeNode;
	node->data = sellAry[0];
	root = node;
	memory.push_back(node);

	for (int i = 1; i < len(sellAry); i++) {
		string name = sellAry[i];
		node = new TreeNode;
		node->data = name;

		current = root;
		while (true) {
			if (name == current->data)
				break;
			if (name < current->data) {
				if (current->left == NULL) {
					current->left = node;
					break;
				}
				current = current->left;
			}
			else {
				if (current->right == NULL) {
					current->right = node;
					break;
				}
				current = current->right;
			}
		}
		memory.push_back(node);
	}
	println("\n이진 탐색 트리 구성 완료!");

	print("\n오늘 판매된 물건(중복X) -->");
	preOrder(root);
	println("");

	freeMemory();
}