#include <stdio.h>             // c 库
#include <stdlib.h>                //maclloc 库
#include <iostream>                // c++ 库

// 有本句 ，下面cout 前面可以没有  std::
using namespace std;
typedef int  ElemType;  //元素数据类型 char 
#define MAXSIZE 10

typedef struct TreeNode {
    ElemType key;
    TreeNode* left;
    TreeNode* right;
}*Tree;

//  loop ---  insert Bst Node       
Tree InsertBst(Tree &T, ElemType k) {
    if (!T) {
        T = new TreeNode;
        T->key = k;
        T->left = T->right = NULL;
        return T;
    }
    Tree p = T;
    while (p) {
        if (k < p->key)
            if (p->left)
            p = p->left;
            else
            {
                Tree q = new TreeNode;
                q->key = k;
                q->left = q->right = NULL;
                p ->left = q;
                return T;
            }
        else if (k > p->key)
            if (p->right)
            p =p->right;
            else
            {
                Tree q = new TreeNode;
                q->key = k;
                q->left = q->right = NULL;
                p->right = q;
                return T;
            }
    }

}

//  recursion ---  insert Bst Node  
Tree InsertBst2(Tree& T, ElemType k) {
    if (!T) {
        T = new TreeNode;
        T->key = k;
    T->left = T->right = NULL;
    return T;
    }
    else if (k < T->key)
          InsertBst2(T->left, k);
    else 
          InsertBst2(T->right, k);
}


// Use array Creat Bst
void CreatBst(Tree& T,ElemType Str[], int n) {
    for (int i = 0; i < n; i++) {
        InsertBst2( T, Str[i]);
    }
}

//  visit TreeNode
void visit(Tree T) {
    cout << T->key <<" ";
}


// InOrder traverse  Tree 
void InTraver(Tree T) {
    if (T){
        InTraver(T->left);
        visit(T);
        InTraver(T->right);
    }
    else return;
}



int main() {

    Tree T=NULL;
    ElemType Str[MAXSIZE] = { 50,66,60,26,21,30,70,68 };
    CreatBst(T, Str, 8);
    InTraver(T);

}