[트리(순회)] (CHECK) 이진 트리, 전위, 중위, 후위, 레벨 순회 및 트리 복원 C++

void preorder(Node* root) {
	if (root == nullptr) return;
	cout << root->key << " "; // pre[cnt++] = root->key;
	preorder(root->left);
	preorder(root->right);
}

void inorder(Node* root) {
	if (root == nullptr) return;
	inorder(root->left);
	cout << root->key << " "; // in[cnt++] = root->key;
	inorder(root->right);
}

void postorder(Node* root) {
	if (root == nullptr) return;
	postorder(root->left);
	postorder(root->right);
	cout << root->key << " "; // post[cnt++] = root->key;
}

void levelorder(Node* root) {
	if (root == nullptr) return;
    
	queue<Node*> q;
	q.push(root);
	while (!q.empty()) {
		Node* cur = q.front();
		q.pop();
		cout << cur->key << " "; // level[cnt++] = root->key;
		if (cur->left != nullptr) q.push(cur->left);
		if (cur->right != nullptr) q.push(cur->right);
	}
}

// 전위, 중위 -> 후위
void preInToPost(int preL, int preR, int inL, int inR) {
	if ((preL > preR) || (inL > inR)) return;
	int key = pre[preL];
	int mid = idx[root];// 중위 순행 루트 인덱스(idx[in[i]] = i;)
	int left = mid - inL;
	int right = inR - mid;

	preInToPost(preL + 1, preL + left, inL, inL + left - 1);
	preInToPost(preR - right + 1, preR, inR - right + 1, inR);
	cout << key << " "; // post[cnt++] = key;
}

// 중위, 후위 -> 전위
void inPostToPre(int inL, int inR, int postL, int postR) {
	if ((inL > inR) || (postL > postR)) return;
	int key = post[postR];
	int mid = idx[root];// 중위 순행 루트 인덱스(idx[in[i]] = i;)
	int left = mid - inL;
	int right = inR - mid;

	cout << key << " "; // pre[cnt++] = key;
	inPostToPre(inL, inL + left - 1, postL, postL + left - 1);
	inPostToPre(inR - right + 1, inR, postR - right, postR - 1);
}

// 중위, 후위 -> 트리
Node* inPostToTree(int start, int end, int& pIndex) {
	if (start > end) return nullptr;

	Node* root = addNode(post[pIndex--]);
	int index = idx[root->key]; // 중위 순행 루트 인덱스(idx[in[i]] = i;)

	root->right = inPostToTree(index + 1, end, pIndex);
	root->left = inPostToTree(start, index - 1, pIndex);

	return root;
}

int main(void) {
	int N = pow(2,level) - 1; // N 원소 개수
	int level = log(N+1)/log(2);  // level 레벨
    
	for (int i = 0; i < N; i++) idx[in[i]] = i;
	preInToPost(0, N-1, 0, N-1);
	inPostToPre(0, N-1, 0, N-1);
    
	int cnt = N-1;
	Node* temp = inPostToTree(0, N-1, cnt);
}

* 참고

https://foxtrotin.tistory.com/442

https://www.jiwon.me/binary-tree-traversal/

https://www.techiedelight.com/ko/construct-binary-tree-from-inorder-postorder-traversals/

https://8iggy.tistory.com/112