알고리즘 연습 문제 43: 귀속과 비귀속이 두 갈래 나무의 전 순서를 반복한다.

. 귀속과 비귀속 두 가지 방법으로 두 갈래 나무의 전서를 두루 훑어본다.
------------------------------------------------
역귀환의 교체는 순환을 빌리는 것이 틀림없다고 생각하기 쉽다. 그러나 우리가 이곳에서 두 갈래 나무를 옮길 때 사실은 컴파일러 내부의 창고를 빌려 저장과 인쇄를 실현하고 기억 기능을 가진다.
현재 만약 순환만 한다면 이런 기억 기능은 존재하지 않을 것이기 때문에 우리는 보조 대기열을 이용하여 실현해야 한다
그러면 이 과정은 훨씬 간단해진다. 예를 들면 아래의 나무 한 그루
                   9
               6     11
           3   8  10  15
         1   7
            2
우리는 먼저 대열(즉 체인 테이블 구조)에 뿌리 원소를 넣는다
그리고 좌우 나무를 두루 돌아다니면
9 6 11
이어서 6 을 두루 돌아다니며 좌우 나무에 가입
9 6 3 8 11
그리고 두루 돌아다닌다.이런 식으로 추측한 결과 인쇄 대기열이 나왔다
같은 이치인데, 중순으로 두루 다니려면?여기에 LinkNode라는 구조체에 변수를 넣어서 방문했는지 여부를 표시해야 한다. 이것은 모두가 고려할 수 있다. 단지 이때 노드를 넣는 것은 노드 좌우에 넣는 것이다. 먼저 왼쪽 트리를 넣고 자신을 넣은 다음에 오른쪽 트리를 넣는 것이다.
예컨대
루트 9에 먼저 접근하면 체인은 6 9로 표시됩니다. (접근할 수 있도록 표시) 11
그리고 6 을 방문하면 체인은 3 6 8 9 11로 표시됩니다.
액세스 3, 1 3, 6, 8, 9 11
액세스 1, 1 2 3 6 8 9 11
액세스 2, 1 2 3 6 8 9 11
8 을 방문하면 123 6 7 8 9 11.
이런 식으로 유추하면 결과는 위와 같다

//============================================================================
// Name        : BTreeMLR.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

struct Node{
	int value;
	Node* left;
	Node* right;
};

struct LinkNode{
	Node* node;
	LinkNode* next;
};

class BTree{
private:
	Node* root;

	void Add(Node* &p, int value){
		if(p == NULL){
			Node* temp = new Node();
			temp->value = value;
			temp->left = NULL;
			temp->right = NULL;
			p = temp;
			return ;
		}
		if(value < p->value)
			Add(p->left, value);
		else if(value > p->value)
			Add(p->right, value);
	}

	void MLR(Node* p){
		if(p == NULL)
			return;
		cout<<p->value<<" ";
		MLR(p->left);
		MLR(p->right);
	}

public:
	BTree(){
		root = NULL;
	}

	void Add(int value){
		Add(root, value);
	}

	void MLR(){
		MLR(root);
	}

	void MLR2(){
		// 
		Node* child = root;

		if(root == NULL)
			return;
		LinkNode* head = new LinkNode();
		head->node = root;
		head->next = NULL;

		LinkNode* current = head;

		while(current != NULL){
			LinkNode* p = current;
			LinkNode* temp = current->next;

			child = current->node;
			if(child->left != NULL){
				LinkNode* newNode = new LinkNode();
				newNode->next = NULL;
				newNode->node = child->left;

				p->next = newNode;
				p = p->next;
			}
			if(child->right != NULL){
				LinkNode* newNode = new LinkNode();
				newNode->next = NULL;
				newNode->node = child->right;

				p->next = newNode;
				p = p->next;
			}
			p->next = temp;
			current = current->next;
		}

		while(head != NULL){
			cout<<head->node->value<<" ";
			head = head->next;
		}

	}

};
int main() {

	BTree* bTree = new BTree();
	int input = 0;
	while(true){
		cin>>input;
		if(input!=-1)
			bTree->Add(input);
		else break;
	}

	bTree->MLR();
	cout<<endl;
	bTree->MLR2();
	return 0;
}

9 6 11 10 15 3 8 1 7 2 -1
9 6 3 1 2 8 7 11 10 15 
9 6 3 1 2 8 7 11 10 15