先用search找到所应该要插入的位置(假定没有重复的点)
之后找到对应位置，左孩子或者右孩子为空的点将其插入，所以插入的节点必然是树的叶子
在构建BST时用到了插入的操作
代码如下
#include<iostream>
#include<cstdlib>
using namespace std;
#define len 15typedef struct Bitnode
{int data;struct Bitnode *lc;struct Bitnode *rc;
}Bitnode,*Bitree;void searchBiTreeNode(Bitree &root,Bitree &node) // 查找
{if(root==NULL)return ;if(root->data>node->data){searchBiTreeNode(root->lc,node);if(root->lc==NULL)root->lc=node;}else if(root->data<node->data){searchBiTreeNode(root->rc,node);if(root->rc==NULL){root->rc=node;}}
}void insertNode(Bitree &bitree,Bitree &node) // 插入
{if(bitree==NULL)bitree=node;elsesearchBiTreeNode(bitree,node);
}void createbst(Bitree &bitree,int arr[]) // 创建BST树
{for(int i=0;i<len;i++){Bitree s=(Bitree)malloc(sizeof(Bitnode));s->data=arr[i];s->lc=NULL;s->rc=NULL;insertNode(bitree,s);}
}void midsearchbitreeprint(Bitree &bitree) // 中序遍历输出
{if(bitree==NULL)return ;midsearchbitreeprint(bitree->lc);printf("%d ",bitree->data);midsearchbitreeprint(bitree->rc);
}Bitree BST_Search(Bitree &root,int x){ // 查找if(root == NULL){return NULL;}else if(root->data>x){return BST_Search(root->lc,x);}else if(root->data<x){return BST_Search(root->rc,x);}else{return root;}
}int main()
{int arr[len]={62,88,58,47,35,73,51,99,37,93,23,27,45,21,12};Bitree bitree=NULL;createbst(bitree,arr);midsearchbitreeprint(bitree);printf("\n");Bitree searchNode = BST_Search(bitree,27);if(searchNode == NULL){printf("没有找到此节点\n");}else{if(searchNode->lc==NULL && searchNode->rc==NULL){ //叶子节点printf("所查找的节点x=%d是叶子节点\n",searchNode->data);}else{if(searchNode->lc != NULL){printf("x=%d所在节点的左孩子: %d\n",searchNode->data,searchNode->lc->data);}if(searchNode->rc != NULL){printf("x=%d所在节点的右孩子: %d\n",searchNode->data,searchNode->rc->data);}}}return 0;
}