3_1_1.cpp

#include <stdio.h>
using namespace std;

class Node {
private:
	int _value;
	Node *_left;
	Node *_right;

public:
	Node(int value) {
		_value = value;
		_left = NULL;
		_right = NULL;
	} Node():_value(0), _left(NULL), _right(NULL) {
	}

	void left(Node * ptr) {
		_left = ptr;
	}

	void right(Node * ptr) {
		_right = ptr;
	}

	void value(int iValue) {
		_value = iValue;
	}

	int value() {
		return _value;
	}

	Node *left(void) {
		return _left;
	}

	Node *right(void) {
		return _right;
	}
};

class Tree {
private:
	Node * head;
public:

	Tree():head(NULL) {	} 

	Tree(int value) {
		Node *node = new Node(value);
		head = node;
	}

	Tree(Node * node) {
		head = node;
	}

	bool Add(Node * node, int value) {
		if (head == NULL) {
			Node *node = new Node(value);
			head = node;
			return true;
		}
		if (value >= node->value()) {
			if (node->right() != NULL)
				return Add(node->right(), value);
			else {
				Node *newNode = new Node(value);
				node->right(newNode);
				return true;
			}
		} else {
			if (node->left() != NULL)
				Add(node->left(), value);
			else {
				Node *newNode = new Node(value);
				node->left(newNode);
				return true;
			}
		}
		return false;
	}

	bool Add(int value) {
		if (head == NULL) {
			Node *node = new Node(value);
			head = node;
			return true;
		}
		if (value >= head->value()) {
			if (head->right() != NULL)
				return Add(head->right(), value);
			else {
				Node *newNode = new Node(value);
				head->right(newNode);
				return true;
			}
		} else {
			if (head->left() != NULL)
				return Add(head->left(), value);
			else {
				Node *newNode = new Node(value);
				head->left(newNode);
				return true;
			}
		}
	}

	Node *RemoveNode(Node * root, int x)
	{

		Node *t = new Node;
		if (x == root->value()) {
			if (root->left() == NULL) {
				t = root->right();
				delete root;
				return t;
			}
			t = root->left();
			while (t->right()) {
				t = t->right();
			}
			t->right(root->right());
			return root->left();
		}
		if (x < root->value())
			root->left(RemoveNode(root->left(), x));
		else
			root->right(RemoveNode(root->right(), x));
		return root;
	}

	bool search(int value, Node *node) {
		while (node != NULL){
			if (value == node->value()) {
				return true;
			} 
			else {
				if(value <= node->value()) return search(value, node->left());
				else return search(value, node->right());
			}
		}
		return false;
	}

	bool search(int value) {
		while (head != NULL){
			if (value == head->value()) {
				return true;
			} 
			else {
				if(value <= head->value()) return search(value, head->left());
				else return search(value, head->right());
			}
		}
		return false;
	}

	void traver_inorder(){
		struct stack{
			Node* node;
			stack* stckNext,*stckPrev;
		}*stck;
		stck = new stack;
		stck->node = head;
		stck->stckNext = NULL;
		stck->stckPrev = NULL;

		for(int i = 1; i <=2 ; i++)
		{
			Node* temp = head;
			while(temp->left()!=NULL){
				stck->stckNext = new stack;
				stck->stckNext->stckPrev = stck;
				stck->stckNext->node = temp->left();

				temp = temp->left();
				stck = stck->stckNext;
			}
			Node* check = NULL;
			while(stck->stckPrev!=NULL){
				if(stck->node->left()!=NULL && check!=stck->node){
					stck->stckNext = new stack;
					stck->stckNext->stckPrev = stck;
					stck->stckNext->node = stck->node->left();
					stck = stck->stckNext;
				}
				else {
					printf("%d ",stck->node->value());
					if(stck->node->right()!=NULL){
						stck->stckNext = new stack;
						stck->stckNext->stckPrev = stck->stckPrev;
						stck->stckNext->node = stck->node->right();
						stck = stck->stckNext;
						delete stck->stckPrev->stckNext;
						stck->stckPrev->stckNext = stck;
						continue;
					} 
					stck=stck->stckPrev;
					delete stck->stckNext;
					check = stck->node;
				}

			}
			if (i==1)
				printf("%d ",head->value());
			check = head->left(); //buffer
			head->left(head->right());
			head->right(check);
		}
	}

};

	Tree* Get_Tree_From_Keyboard(size_t size){
		int temp;
		scanf("%d",&temp);
		Tree *_result = new Tree(temp);
		--size;
		while(size>0){
			scanf("%d",&temp);
			_result->Add(temp);
			--size;
		}
		return _result;
	}
	int main(int argc, char argv[]){
		size_t size;
		scanf("%d ",&size);
		Tree* myTree = Get_Tree_From_Keyboard(size);
		myTree->traver_inorder();
		return 0;
	}