二叉搜索树排序数数组插入方式

首先数组递归版

struct Node 
{
    int val;
    int l;
    int r;
    Node(int V,int L ,int R):val(V),l(L),r(R){};}node[2005];
int insert(int val, int x){if (x==0)
    {
        cnt++;
        x = cnt;
        node[x].val = val;
        node[x].l = node[x].r = 0;
        return x;
    }
    if(val<node[x].val){node[x].l=insert(val, node[x].l);
        // 标记行
    }
    else {node[x].r = insert(val, node[x].r);
        // 标记行
    }
    return x;// 标记行 2
}

/* 此处保留一个疑问：当标记行 2 的语句放在俩标记行位置时和上述语句的执行效果会有区别吗?
当然也可借鉴下面这一套二叉搜索树模板（由于需求问题未完全实现）*/

struct TreeNode
{
    int key;
    TreeNodePosion p;
    TreeNodePosion l;
    TreeNodePosion r;
    TreeNode(int val) :key(val), l(NULL), r(NULL), p(NULL) {};};
struct  Tree
{TreeNodePosion root;};
TreeNodePosion tree_search(TreeNodePosion x, int k) {if (x == NULL || x->key == k)return x;
    if (x->key < k)tree_search(x->l, k);
    if (x->key > k)tree_search(x->r, k);
}
TreeNodePosion find_max(TreeNodePosion x) {while ((x->r) != NULL)x = x->r;
    return x;
}
TreeNodePosion find_min(TreeNodePosion x) {while ((x->l) != NULL)x = x->l;
    return x;
}

TreeNodePosion find_succ(TreeNodePosion x) {if (x->r != NULL)return find_min(x->r);
    TreeNodePosion p = x->p;
    TreeNodePosion y = x;
    while (p != NULL)
    {if (p->l == y)break;
        y = p;
        p = p->p;
    }
    return p;
}
TreeNodePosion find_pre(TreeNodePosion x) {if (x->l != NULL)return find_max(x->l);
    TreeNodePosion p = x->p;
    TreeNodePosion y = x;
    while (p != NULL)
    {if (p->r == y)break;
        y = p;
        p = p->p;
    }
    return p;
}

void insert(TreeNodePosion& root, int k) {if (root == NULL) {root = new TreeNode(k); return; }
    TreeNodePosion tem = root;
    TreeNodePosion tem1 = tem;
    while (tem != NULL)
    {
        tem1 = tem;
        if (tem->key > k) {tem = tem->l;}
        else if (tem->key < k) {tem = tem->r;}
        else
        {return;};
    }
    TreeNodePosion new_node = new TreeNode(k);
    new_node->p = tem1;
    if (k < tem1->key) {tem1->l = new_node;}
    else if (k > tem1->key) {tem1->r = new_node;}
}


void pre_order(TreeNodePosion p) {if (p != NULL)
    {
        cout << p->key << ' ';
        pre_order(p->l);
        pre_order(p->r);
    }
}


void in_order(TreeNodePosion p) {if (p != NULL) {in_order(p->l);
        cout << p->key << ' ';
        in_order(p->r);
    }
}


void post_order(TreeNodePosion p) {if (p != NULL) {post_order(p->l);
        post_order(p->r);
        cout << p->key << ' ';
    }
}

int main() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; TreeNodePosion root = NULL;
    cin >> n; int k;
    while (n--)
    {
        cin >> k;
        insert(root, k);
    }
    pre_order(root); cout << '\n';
    post_order(root);

    return 0;
}