对于BST而言，插入一个节点主要是要保持其“小-中-大”的逻辑不变，因此插入的节点的逻辑可以从根节点开始，一步步寻找新节点的“最终归宿”，比如在如下BST中，要插入新节点16，最终应该插入到节点17的左孩子处。
在实现插入算法的时候，由于树状结构本身是递归的，因此可以使用递归函数更优雅地实现插入算法。如下：
情况①:
第一次插入节点给这个二叉树
二叉树是空的,则直接把Root根指针指向新节点
struct node *Root=NULL;
Root = bstInsert(Root,25);
对应插入代码为:
if(root == NULL)
return new;
情况②:
非第一次插入节点
递进深入二叉树
递进的条件:
只要节点的Lchild或Rchild不为NULL 则以下一个节点作为根 继续深入
回归的条件:
到了 尾巴为NULL 同时满足大小关系条件 则返回当前节点地址
代码：
//构建二叉树节点 typedef struct bst { //数据域 int data; //指针域 struct bst *lchild; struct bst *rchild; }BST, *pBST; //二叉树插入算法 pBST bstInsert(pBST root, int data) { //0.申请空间 pBST Newnode = (pBST)malloc(sizeof(BST)); //1.数据域赋值 Newnode->data = data; //2.指针域赋值 Newnode->lchild = NULL; Newnode->rchild = NULL; // 若此时BST为空，则Newnode称为二叉树的根节点 if(root == NULL) return Newnode; //只要满足这个条件就开始回归 // 若新节点比根节点小，那么新节点应该插入左子树中 // 至于插入到左子树的具体什么位置就不用管了，直接递归即可 if(data < root->data) root->lchild = bstInsert(root->lchild, data); // 若新节点比根节点大，那么新节点应该插入右子树中 // 至于插入到右子树的具体什么位置就不用管了，直接递归即可 else if(data > root->data) root->rchild = bstInsert(root->rchild, data); // 若已存在，则不处理 else printf("节点已存在"); free(Newnode); return root; }
