二叉排序树

//have a nice day:D
#include<iostream>
#include<cstdio>

using namespace std;

struct TreeNode{
    int data;
    TreeNode* leftChild;
    TreeNode* rightChild;
    TreeNode(int x): data(x),leftChild(NULL),rightChild(NULL){}
};

void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    cout<<root->data<<" ";
    PreOrder(root->leftChild);
    PreOrder(root->rightChild);
    return;
}

void InOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    InOrder(root->leftChild);
    cout<<root->data<<" ";
    InOrder(root->rightChild);
    return;
}

void PostOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    PostOrder(root->leftChild);
    PostOrder(root->rightChild);
    cout<<root->data<<" ";
    return;
}

TreeNode* Insert(TreeNode* root,int x){
    if(root == NULL){
        root = new TreeNode(x);
    }
    else if(x<root->data){
        root->leftChild = Insert(root->leftChild,x);
    }
    else if(x>root->data){
        root->rightChild = Insert(root->rightChild,x);
    }
    return root;
}

int main(){
    int N;
    int temp;
    while(cin>>N){
        TreeNode* root = NULL;
        for(int i=0; i<N; i++){
            cin>>temp;
            root = Insert(root,temp);
        }
        PreOrder(root);
        cout<<endl;
        InOrder(root);
        cout<<endl;
        PostOrder(root);
        cout<<endl;
    }
    return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int[] arr = new int[n];
			for (int i = 0; i < arr.length; i ++) {
				arr[i] = sc.nextInt();
			}
			TreeNode root = new TreeNode(arr[0]);
			for (int i = 1; i < arr.length; i ++) {
				createBST(root, arr[i]);
			}
			DLR(root);
			System.out.println();
			LDR(root);
			System.out.println();
			LRD(root);
			System.out.println();
		}
	}
	public static void createBST(TreeNode root, int value) {
		if(root.value == value) return;
		if(value < root.value) {
			if(root.left == null) root.left = new TreeNode(value);
			else createBST(root.left, value);
		} else {
			if(root.right == null) root.right = new TreeNode(value);
			else createBST(root.right, value);
		}
	}
	public static void DLR(TreeNode root) {
		if(root != null) {
			System.out.print(root.value + " ");
			DLR(root.left);
			DLR(root.right);
		}
	}
	public static void LDR(TreeNode root) {
		if(root != null) {
			LDR(root.left);
			System.out.print(root.value + " ");
			LDR(root.right);
		}
	}
	public static void LRD(TreeNode root) {
		if(root != null) {
			LRD(root.left);
			LRD(root.right);
			System.out.print(root.value + " ");
		}
	}
	static class TreeNode {
		private int value;
		private TreeNode left;
		private TreeNode right;
		public TreeNode(int value) {
			this.value = value;
		}
	}
}

import java.util.Scanner;

class TreeNode {
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;

	public TreeNode(int val) {
		this.val = val;
	}
}

public class Main {

	static void insert(int v, TreeNode root) {
		if (v != root.val) {
			if (v < root.val) { // 小于根节点，往左
				if (root.left == null) { // 若左节点为空，直接插入
					root.left = new TreeNode(v);
				} else {
					insert(v, root.left); // 若左节点不为空，把左节点当做根节点递归调用insert
				}
			} else {
				if (root.right == null) {
					root.right = new TreeNode(v);
				} else {
					insert(v, root.right);
				}
			}
		}
	}

	// 前序遍历
	static void preorderTraversal(TreeNode root) {
		if (root == null)
			return;
		System.out.print(root.val + " ");
		preorderTraversal(root.left);
		preorderTraversal(root.right);
	}

	// 中序遍历
	static void inorderTraversal(TreeNode root) {
		if (root == null)
			return;
		inorderTraversal(root.left);
		System.out.print(root.val + " ");
		inorderTraversal(root.right);
	}

	// 后序遍历
	static void postorderTraversal(TreeNode root) {
		if (root == null)
			return;
		postorderTraversal(root.left);
		postorderTraversal(root.right);
		System.out.print(root.val + " ");
	}

	public static void main(String[] args) {
		int n = 0;
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			n = in.nextInt();
			int v = in.nextInt();
			TreeNode root = new TreeNode(v);
			n--;
			while (n > 0) {
				v = in.nextInt();
				insert(v, root);
				n--;
			}
			preorderTraversal(root);
			System.out.println();
			inorderTraversal(root);
			System.out.println();
			postorderTraversal(root);
            System.out.println();
		}
	}
}

/**
    参考 CSDN Blog : http://blog.csdn.net/stpeace/article/details/9067029
*/
#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 105;
int num[maxn] = {0};

// BST 树的结点
typedef struct node
{
    int key;
    struct node *lChild;        // 指针定义分开
    struct node *rChild;
}Node, *BST;

// BST 树插入节点
bool insertNode(Node* &p, int i)
{
    if(p == NULL)
    {
        p = new Node;
        p->key = i;
        p->lChild = p->rChild = NULL;
        return true;
    }

    if(i == p->key)
        return false;

    if(i < p->key)
        return insertNode(p->lChild, i);

    if(i > p->key)
        return insertNode(p->rChild, i);
    
    return false;   // 确保一定有返回值
    
}

// 根据已知数组创建 BST
void createBST(Node* &T, int a[], int n)
{
    T = NULL;
    for(int i = 0; i < n; ++i)
    {
        insertNode(T, a[i]);
    }
}

// 先序遍历
void preOrderTraverse(BST T)
{
    if(T != NULL)
    {
        cout << T->key << " ";
        preOrderTraverse(T->lChild);
        preOrderTraverse(T->rChild);
    }
}

// 中序遍历
void inOrderTraverse(BST T)
{
    if(T != NULL)
    {
        inOrderTraverse(T->lChild);
        cout << T->key << " ";
        inOrderTraverse(T->rChild);
    }
}

// 后续遍历
void lastOrderTraverse(BST T)
{
    if(T != NULL)
    {
        lastOrderTraverse(T->lChild);
        lastOrderTraverse(T->rChild);
        cout << T->key << " ";
    }
}

int main()
{
    int n;
    BST T;
    while(cin >> n)
    {
        for(int i = 0; i < n; ++i)
        {
            cin >> num[i];
        }
        createBST(T, num, n);
        preOrderTraverse(T);
        cout << endl;
        inOrderTraverse(T);
        cout << endl;
        lastOrderTraverse(T);
        cout << endl;

    }
    return 0;
}

#include<iostream>
using namespace std;

typedef struct node
{
    int val;
    node * left,*right;
    node(int val):val(val),left(NULL),right(NULL){}
}BTree;

void Insert(BTree * &t,int v)
{
    if(t == NULL)
    {
        t = new node(v);
        return;
    }
    if(t->val == v)
        return;
    if(v < t->val)
        Insert(t->left,v);
    if(v > t->val)
        Insert(t->right, v);
}

void preOrder(BTree * t)
{
    if(t == NULL)
        return;
    cout << t->val << ' ';
    preOrder(t->left);
    preOrder(t->right);
}

void inOrder(BTree * t)
{
    if(t == NULL)
        return;
    inOrder(t->left);
    cout << t->val << ' ';
    inOrder(t->right);
}

void postOrder(BTree * t)
{
    if(t == NULL)
        return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->val << ' ';
}

int main(void)
{
    int n;
    
    while(cin >> n)
    {
        getchar();
        
        BTree * t = NULL;
        
        for(int i = 0;i < n;i++)
        {
            int v;
            cin >> v;
            Insert(t,v);
        }
        
        preOrder(t);
        cout << endl;
        inOrder(t);
        cout << endl;
        postOrder(t);
        cout << endl;
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

struct Node
{
    int v;
    struct Node* lchild,* rchild;
};

Node* newNode(int x)
{
    Node* t = new Node;
    t->v = x;
    t->lchild = t->rchild = nullptr;
    return t;
}

void Insert(Node* &root, int x)
{
    if(root == nullptr)
    {
        root = newNode(x); return ;
    }
    if(root->v == x) return ;
    else if(root->v < x) Insert(root->rchild, x);
    else Insert(root->lchild, x);
}

Node* Create(int n)
{
    int x;
    Node* root = nullptr;
    for(int i = 0;i < n; i++)
    {
        cin >> x; Insert(root, x);
    }
    return root;
}

void PreOrder(Node* root)
{
    if(root == nullptr) return ;
    cout << root->v << ' ';
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}

void MidOrder(Node* root)
{
    if(root == nullptr) return ;
    MidOrder(root->lchild);
    cout << root->v << ' ';
    MidOrder(root->rchild);
}

void LastOrder(Node* root)
{
    if(root == nullptr) return ;
    LastOrder(root->lchild);
    LastOrder(root->rchild);
    cout << root->v << ' ';
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n)
    {
        Node* root = Create(n);
        PreOrder(root); cout << '\n';
        MidOrder(root); cout << '\n';
        LastOrder(root); cout << '\n';
    }
    return 0;
}

#include<iostream>
using namespace std;
struct TNode
{
	int data;
	TNode* left, * right;
	TNode(int x) :data(x), left(nullptr), right(nullptr) {}
};

void build(int node, TNode*& tree)
{
	TNode* move = tree, * parent = nullptr;
	while (move != nullptr)
	{
		parent = move;
		if (node < move->data)
			move = move->left;
		else if (node > move->data)
			move = move->right;
		else
			return;
	}
	TNode* temp = new TNode(node);
	if (parent == nullptr)
		tree = temp;
	else if (node < parent->data)
		parent->left = temp;
	else
		parent->right = temp;
}
void preOrder(TNode*& tree)
{
	if (tree != nullptr)
	{
		cout << tree->data << " ";
		preOrder(tree->left);
		preOrder(tree->right);
	}
}
void inOrder(TNode*& tree)
{
	if (tree != nullptr)
	{
		inOrder(tree->left);
		cout << tree->data << " ";
		inOrder(tree->right);
	}
}

void postOrder(TNode*& tree)
{
	if (tree != nullptr)
	{
		postOrder(tree->left);
		postOrder(tree->right);
		cout << tree->data << " ";
	}
}
int main()
{
	int n;
	while (cin>>n)
	{
		int node;
		TNode* tree = nullptr;
		for (int i = 0; i < n; i++)
		{
			cin >> node;
			build(node, tree);
		}
		preOrder(tree);
		cout << endl;
		inOrder(tree);
		cout << endl;
		postOrder(tree);
		cout << endl;
	}
	return 0;
}

#include <iostream>
#include <memory>
using namespace std;

struct node{
	int data;
	shared_ptr<node> left,right;
	node():data(0),left(nullptr),right(nullptr){};
	node(const int& d):data(d),left(nullptr),right(nullptr){};
};
typedef shared_ptr<node> tree;

void build_tree(tree& l,const int& d){
	if(l==nullptr){
		l = make_shared<node>(d);//待插入节点
		return;
	}
	if(d<l->data)
		build_tree(l->left,d);
	else if(d>l->data)
		build_tree(l->right,d);
	return;
}

void pre_order(tree& l){
	if(l==nullptr) return;
	cout<<l->data<<' ';
	pre_order(l->left);
	pre_order(l->right);
}
void mid_order(tree& l){
	if(l==nullptr) return;
	mid_order(l->left);
	cout<<l->data<<' ';
	mid_order(l->right);
}
void post_order(tree& l){
	if(l==nullptr) return;
	post_order(l->left);
	post_order(l->right);
	cout<<l->data<<' ';
}

int main(){
	int n,x;
	while(cin>>n){
		tree my_tree;
		for(int i(0);i<n;++i){
			cin>>x;
			build_tree(my_tree,x);
		}
		pre_order(my_tree);
		cout<<endl;
		mid_order(my_tree);
		cout<<endl;
		post_order(my_tree);
		cout<<endl;
	}
    return 0;
}

#include <iostream>
using namespace std;

typedef struct node
{
    int data;
    struct node *lchild, *rchild;
}BSTNode, *BSTree;

void InsertTree(BSTree &T, int x)
{
    if(T == NULL){
        T = new BSTNode;
        T->data = x;
        T->rchild = NULL; T->lchild = NULL;
    }
    else if(x < T->data)
        InsertTree(T->lchild, x);
    else if(x == T->data)
        return;
    else
        InsertTree(T->rchild, x);
}

void preTraverse(BSTree T)
{
    if(T == NULL)
        return;
    cout << T->data << " ";
    preTraverse(T->lchild);
    preTraverse(T->rchild);
}

void inTraverse(BSTree T)
{
    if(T == NULL)
        return;
    inTraverse(T->lchild);
    cout << T->data << " ";
    inTraverse(T->rchild);
}

void postTraverse(BSTree T)
{
    if(T == NULL)
        return;
    postTraverse(T->lchild);
    postTraverse(T->rchild);
    cout << T->data << " ";
}

int main()
{
    int n;
    while (cin >> n)
    {
        BSTree T = NULL;
        for (int i = 0; i < n; i++)
        {
            int x; cin >> x; 
            InsertTree(T, x);
        }
        preTraverse(T); cout << endl;
        inTraverse(T); cout << endl;
        postTraverse(T); cout << endl;
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cassert>
using namespace std;

template <typename T>
struct BSTNode
{
	using valueType = T;
	BSTNode* leftChild;
	BSTNode* rightChild;
	valueType element;
	explicit BSTNode(const valueType data = T(), BSTNode* left = nullptr, BSTNode* right = nullptr) : element(data), leftChild(left), rightChild(right)
	{
	}
};

template <typename T>
class BSTree
{
public:
	using valueType = T;
	BSTNode<valueType>* root;
	explicit BSTree()
	{
		root = nullptr;
	}
	void insert(const valueType& data);
	void clear();
	bool empty() { return root == nullptr; }
};

template <typename valueType>
void freeTree(BSTNode<valueType>* &root)
{
	if (root->leftChild)
		freeTree(root->leftChild);
	if (root->rightChild)
		freeTree(root->rightChild);
	if (root)
	{
		delete root;
		root = nullptr;
	}
	return;
}

template <typename valueType>
void BSTree<valueType>::insert(const valueType& data)
{
	BSTNode<valueType>* parent = nullptr, * node = root;
	while (node)
	{
		parent = node;
		if (node->element > data)
			node = node->leftChild;
		else if (node->element < data)
			node = node->rightChild;
		else if (node->element == data)
			return;
	}
	if (root == nullptr)
		root = new BSTNode<valueType>(data);
	else if (parent->element < data)
		parent->rightChild = new BSTNode<valueType>(data);
	else if (parent->element > data)
		parent->leftChild = new BSTNode<valueType>(data);
	return;
}

template <typename valueType>
void BSTree<valueType>::clear()
{
	if (root)
		freeTree(root);
	return;
}


void preOrderTraversal(BSTNode<int>* node)
{
	cout << node->element << " ";
	if (node->leftChild)
		preOrderTraversal(node->leftChild);
	if (node->rightChild)
		preOrderTraversal(node->rightChild);
}

void inOrderTraversal(BSTNode<int>* node)
{

	if (node->leftChild)
		inOrderTraversal(node->leftChild);
	cout << node->element << " ";
	if (node->rightChild)
		inOrderTraversal(node->rightChild);
}

void postOrderTraversal(BSTNode<int>* node)
{

	if (node->leftChild)
		postOrderTraversal(node->leftChild);
	if (node->rightChild)
		postOrderTraversal(node->rightChild);
	cout << node->element << " ";
}


int main()
{
	BSTree<int> tree;
	int n, temp;
	while (cin >> n)
	{
		for (int i = 0; i < n; ++i)
		{
			cin >> temp;
			tree.insert(temp);
		}
		preOrderTraversal(tree.root);
		cout << endl;
		inOrderTraversal(tree.root);
		cout << endl;
		postOrderTraversal(tree.root);
		cout << endl;
		tree.clear();
		assert(tree.empty());
	}
	return 0;
}

#include<stdio.h>
#include<string.h>
struct node{
    node *lchild,*rchild;
    int c;
}tree[110];
int loc;
node *create(){
    tree[loc].lchild=tree[loc].rchild=NULL;
    return &tree[loc++];
}
void postOrder(node *T){
    if(T->lchild!=NULL)
        postOrder(T->lchild);
    if(T->rchild!=NULL)
        postOrder(T->rchild);
    printf("%d ",T->c);
}
void inOrder(node *T){
    if(T->lchild!=NULL)
        inOrder(T->lchild);
    printf("%d ",T->c);
    if(T->rchild!=NULL)
        inOrder(T->rchild);
}
void preOrder(node *T){
    printf("%d ",T->c);
    if(T->lchild!=NULL)
        preOrder(T->lchild);
    if(T->rchild!=NULL)
        preOrder(T->rchild);    
}
node *insert(node *T,int x){
    if(T==NULL){
        T=create();
        T->c=x;
        return T;
    }else if(x<T->c)
        T->lchild=insert(T->lchild,x);
    else if(x>T->c)
        T->rchild=insert(T->rchild,x);
    return T;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        loc=0;
        node *T=NULL;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            T=insert(T,x);
        }
        preOrder(T);
        printf("\n");
        inOrder(T);
        printf("\n");
        postOrder(T);
        printf("\n");
    }
    return 0;
}

#参考SINGLE、DOG的Python版
class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


def insertNode(value, root):     #插入节点
    if root.data == value:
        return
    if root.data < value:
        if not root.right:
            root.right = Node(value)
        else:
            insertNode(value, root.right)
    else:
        if not root.left:
            root.left = Node(value)
        else:
            insertNode(value, root.left)


def pre_orderTtaversing(root):    #前序遍历
    if not root:
        return
    print(root.data, end=" ")
    pre_orderTtaversing(root.left)
    pre_orderTtaversing(root.right)


def mid_orderTtaversing(root):     #中序遍历
    if not root:
        return
    mid_orderTtaversing(root.left)
    print(root.data, end=" ")
    mid_orderTtaversing(root.right)


def post_orderTtaversing(root):    #后序遍历
    if not root:
        return
    post_orderTtaversing(root.left)
    post_orderTtaversing(root.right)
    print(root.data, end=" ")


try:
    while True:
        num = int(input())
        nodeList = list(map(int, input().split()))
        root = Node(nodeList[0])
        for i in range(1, num):
            insertNode(nodeList[i], root)
        pre_orderTtaversing(root)
        print()
        mid_orderTtaversing(root)
        print()
        post_orderTtaversing(root)
        print()
except Exception:
    pass

import java.util.Scanner;

public class Main
{

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt())
        {
            BinarySearchTree searchTree = new BinarySearchTree();
            int n = scan.nextInt();
            for(int i = 0; i < n; i++)
                searchTree.insert(scan.nextInt());
            BinarySearchTree.preOrder(searchTree.root);
            System.out.println();
            BinarySearchTree.inOrder(searchTree.root);
            System.out.println();
            BinarySearchTree.postOrder(searchTree.root);
            System.out.println();
        }
        
        scan.close();
    }

}

class Node
{
    int key;
    Node leftChild;
    Node rightChild;
    
    public Node(int key)
    {
        this.key = key;
        leftChild = null;
        rightChild = null;
    }
}


class BinarySearchTree
{
    Node root;

    public boolean insert(int key)
    {
        if (root == null)
        {
            root = new Node(key);
            return true;
        }
        
        Node current = root;
        Node parent = null;
        boolean belongLeft = false;
        
        while (current != null)
        {
            parent = current;
            if (key < current.key)
            {
                current = current.leftChild;
                belongLeft = true;
            }
            else if (key > current.key)
            {
                current = current.rightChild;
                belongLeft = false;
            }
            else
                return false;
        }
        
        Node insertion = new Node(key);
        if (belongLeft)
            parent.leftChild = insertion;
        else
            parent.rightChild = insertion;
        
        return true;
    }

    /**
     * 先序遍历
     * @param root
     *        根节点
     */
    public static void preOrder(Node root)
    {
        if (root != null)
        {
            System.out.print(root.key + " ");
            preOrder(root.leftChild);
            preOrder(root.rightChild);
        }
    }
    
    /**
     * 中序遍历
     * @param root
     *        根节点
     */
    public static void inOrder(Node root)
    {
        if (root != null)
        {
            inOrder(root.leftChild);
            System.out.print(root.key + " ");
            inOrder(root.rightChild);
        }
    }
    
    /**
     * 后序遍历
     * @param root
     *        根节点
     */
    public static void postOrder(Node root)
    {
        if (root != null)
        {
            postOrder(root.leftChild);
            postOrder(root.rightChild);
            System.out.print(root.key + " ");
        }
    }
    
}

#include<stdio.h>
#include<malloc.h>
typedef struct BNode{
    int data;
    struct BNode* lchild;
    struct BNode* rchild;
}Node,*Tree;
void Create(Tree &t,int x){
    if(!t){
        t=(Node*)malloc(sizeof(Node));
        t->data=x;
        t->lchild=t->rchild=NULL;
    }
    else if(x<t->data)Create(t->lchild,x);
    else if(x>t->data)Create(t->rchild,x);
}
void PreOrder(Tree t){
    printf("%d ",t->data);
    if(t->lchild)PreOrder(t->lchild);
    if(t->rchild)PreOrder(t->rchild);
}
void InOrder(Tree t){
    if(t->lchild)InOrder(t->lchild);
    printf("%d ",t->data);
    if(t->rchild)InOrder(t->rchild);
}
void PostOrder(Tree t){
    if(t->lchild)PostOrder(t->lchild);
    if(t->rchild)PostOrder(t->rchild);
    printf("%d ",t->data);
}
int main(){
    int n;
    int a;
    while(scanf("%d",&n)!=EOF){
        Tree t=NULL;
        for(int i=0;i<n;i++){
            scanf("%d",&a);
            Create(t,a);
        }
        PreOrder(t);
        printf("\n");
        InOrder(t);
        printf("\n");
        PostOrder(t);
        printf("\n");
        free(t);
    }
    return 0;
}

	

import java.util.Scanner;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int value;
    public TreeNode(int value){
        this.value = value;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            int n = scan.nextInt();
            TreeNode root = null;
            for(int i=0;i<n;i++){
                root = insert(root, scan.nextInt());
            }
            preOrder(root);
            System.out.println();
            inOrder(root);
            System.out.println();
            backOrder(root);
            System.out.println();
        }
    }
    
    public static void preOrder(TreeNode root){
        if(root!=null){
            System.out.print(root.value+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    
    public static void inOrder(TreeNode root){
        if(root!=null){
            inOrder(root.left);
            System.out.print(root.value+" ");
            inOrder(root.right);
        }
    }
    
    public static void backOrder(TreeNode root){
        if(root!=null){
            backOrder(root.left);
            backOrder(root.right);
            System.out.print(root.value+" ");
        }
    }
    
    public static TreeNode insert(TreeNode root, int value){
        if(root == null)
            root = new TreeNode(value);
        if(root.value == value)
            return root;
        if(root.value> value){
            root.left = insert(root.left, value);
        }else
            root.right = insert(root.right, value);
        return root;
    }
}

我把二叉排序树又抽象了一层

package com.speical.first;

import java.util.Scanner;

/**
 * @author Special
 * @time 2018/02/05 05:28:59
 */
public class Pro194 {

    static class BST{
        Node root;
        int size;

        class Node{
            int value;
            Node left, right;

            public Node(int value) {
                this.value = value;
            }
        }

        public void addNode(Node node) {
            if(size == 0) {
                root = node;
            }else {
                Node point = root, parent = root;
                while(point != null) {
                    if(node.value == point.value) { return; }
                    parent = point;
                    if(node.value < point.value) {
                        point = point.left;
                    }else if(node.value > point.value) {
                        point = point.right;
                    }
                }
                if(node.value < parent.value) {
                    parent.left = node;
                }else {
                    parent.right = node;
                }
            }
            size++;
        }

        public void preOrder(Node node) {
            if(node != null) {
                System.out.print(node.value + " ");
                preOrder(node.left);
                preOrder(node.right);
            }
        }

        public void inOrder(Node node) {
            if(node != null) {
                inOrder(node.left);
                System.out.print(node.value + " ");
                inOrder(node.right);
            }
        }

        public void postOrder(Node node) {
            if(node != null) {
                postOrder(node.left);
                postOrder(node.right);
                System.out.print(node.value + " ");
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()) {
            int n = input.nextInt();
            BST bst = new BST();
            while(n-- > 0) {
                bst.addNode(bst.new Node(input.nextInt()));
            }
            bst.preOrder(bst.root);
            System.out.println();
            bst.inOrder(bst.root);
            System.out.println();
            bst.postOrder(bst.root);
            System.out.println();
        }
    }

}