（C语言，数据结构）查找一个数是否在数列中

Question

设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”，否则，将它插入到序列中使它仍然有序，并输出排序后的序列。，在VC下编程的

Answer 1

这个题目一般会采用排序二叉树来解。
struct Node {
int data;
Node *lchild, *rchild;
Node(int _data = 0, Node *_lchild = NULL, Node *_rchild = NULL):
data(_data), lchild(_lchild), rchild(_rchild) { }
};
bool SearchInsert(Node* &root, int x) {
if(root == NULL) {
root = new Node(x);
return false;
}
if(x == root->data) return true;
if(x < root->data) return SearchInsert(root->lchild, x);
if(x > root->data) return SearchInsert(root->rchild, x);
}
对这棵排序二叉树进行中序遍历就可得到它们有序序列。

Answer 2

如果用数组来解，就是一个二分查找，然后插入的过程。

如果用链表来解，就是一个顺序查找，然后插入的过程。追问

链表解，程序怎么写？求教