二叉排序树

二叉排序树来自（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉360百科树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

• 中文名 二叉排序树
• 外文名 Binary Sort Tree 
• 别 称 二叉查找树、二叉搜索树 
• 别称外文名 Binary Search Tree

基本步骤

　　若根来自结点的关键字值等于查找的关键字，成功。

　　否则，若小于根结点的关键字值，递归查左子树。

　　若大于根结点的关太键字值，递归查右子树。

　360百科　若子树为空，查找不成功。

　　若座含弱爱想插入算法：

　　首先执行查找算法，找出被插结点的父许坐木检亲结点。

　　判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。

　　若娘酒者乡二叉树为空。则首先兰即门既善肉练单独生成根结点。

　　注意：新插入的结点总是叶子结点。

　　void InsertBST(t，key)

　　//在二叉排序树中插入查找关键字key

　　{

　　if(t==NULL){

　　t=new BiTree;

　　t->lchild=t->rchild=NULL;

　　t->data=模key;

　　return; }

　　if(ke国度势永ydata ) InsertBS已字料员执衡连解握属T(t->lchild,key);

　　els曲压志食快缩诉受占去e InsertBST (t->rchild, key );

　　}

　　void CreateBiTree(tree,d【 】,n）

　　//n个数据在数组d中，tree为二叉排序树根

　　{tree=现企例奏按此备需良查NULL;

　　for(如春快却话酒青呢集i=0;i InsertBST(tree,d);

　　}