#include <iostream>
using namespace std;
typedef struct BSNode
{
    int data;
    BSNode *left;
    BSNode *right;
} BSNode;
bool InsetNode(BSNode *&root, int e)
{
    if (root == nullptr)
    {
        root = new BSNode;
        root->data = e;
        root->left = nullptr;
        root->right = nullptr;
        return true;
    }
    else if (e < root->data)
    {
        return InsetNode(root->left, e);
    }
    else if (e > root->data)
    {
        return InsetNode(root->right, e);
    }
    return false;
}
void InOrderTraversal(BSNode *root) // 中序遍历
{
    if (root != nullptr)
    {
        InOrderTraversal(root->left);
        printf("%d ", root->data);
        InOrderTraversal(root->right);
    }
}
void PreOrder(BSNode *root) // 先序遍历
{
    if (root != nullptr)
    {
        printf("%d ", root->data);
        InOrderTraversal(root->left);

        InOrderTraversal(root->right);
    }
}
int main()
{
    BSNode *root = nullptr;
    int value;
    printf("请输入结点的值:");
    cin >> value;
    while (value != 999)
    {

        if (!InsetNode(root, value))
        {
            printf("%d已经有了,插入失败!\n", value);
        }
        printf("\n中序遍历二叉树:");
        InOrderTraversal(root);
        printf("\n先序遍历二叉树:");
        PreOrder(root);
        printf("\n请输入结点的值:");
        cin >> value;
    }
    return 0;
}