BST： 二叉查找树/排序二叉树/二叉搜索树/二叉排序树 二叉查找树由根节点，左子树，右子树组成， 左子树和右子树又是二叉查找树， 左子树的节点的数据域小于或等于根节点的数据域， 右子树的节点的数据域大于根节点的数据域
二叉查找树的基本操作 1. 2.插入操作： 对于一棵二叉查找树来说， 查找某个数据域的节点一定是沿着确定的路径进行的。
因此，当对某个需要查找的值在二叉查找树中查找成功，说明该节点存在； 反之，如果这个需要查找的值在二叉查找树中查找失败，那么说明查找失败的地方一定是节点需要插入的地方。
因此可以在上面查找操作的基础上，在root==NULL时，新建需要插入的节点。 显然插入的时间复杂度为O（h），h为二叉查找树的高度
struct node{ typename data; node* lchild; node* rchild; }; //需要新建节点，往二叉树中插入节点，使用下列函数 node* newNode(int v){ node* Node = new node;//申请一个node型变量的地址空间 Node->data=v;//节点权值为v Node->lchild=Node->rchild=NULL;//初始状态下没有左右孩子 return Node;//返回新建节点的地址 }; //insert函数 将在二叉树中插入一个数据域为x的新节点（注意，参数root要加引用&） void insert(node* &root,int x){ if(root==NULL){ //空树，说明查找失败，即插入位置 root=newNode(x);//需要新建节点，往二叉树中插入节点，使用下列函数 return; } if(x==root->data){ return; }else if(x<root->data){ insert(root->lchild,x); }else{ insert(root->rchild,x); } }3.二叉查找树的建立 建立一棵二叉查找树，就是先后插入n个节点的过程， 这和一般二叉树的建立是完全一样的，因此代码也基本相同
struct node{ typename data; node* lchild; node* rchild; }; //需要新建节点，往二叉树中插入节点，使用下列函数 node* newNode(int v){ node* Node = new node;//申请一个node型变量的地址空间 Node->data=v;//节点权值为v Node->lchild=Node->rchild=NULL;//初始状态下没有左右孩子 return Node;//返回新建节点的地址 }; //二叉树的建立 void insert(node* &root,int x){ if(root==NULL){ //空树，说明查找失败，即插入位置 root=newNode(x); return; } if(x==root->data){ return; }else if(x<root->data){ insert(root->lchild,x); }else{ insert(root->rchild,x); } } //---------------------------------------------- node* Create(int data[],int n){ node* root=NULL;//新建节点root for(int i=0;i<n;i++){ insert(root,data[i]);//将data[0]~data[n-1]插入二叉树中 } return root; }二叉树的遍历-查找-死胡同 1.先序遍历
void preOder(node* root){ if(root==NULL){ return;//到达空树，递归边界 } //访问根节点，例如将其数据域输出 printf("%d\n",root->data) //访问左子树 preOrder(root->lchild); preOrder(root->rchild); } ///因为先序遍历先访问根节点，因此对一棵二叉树的先序遍历序列 //序列的第一个一定是根节点