二叉排序树的插入和生成在根结点p的二叉排序树中插入关键字为k的结点的过程如下：（1）若p为空，创建一个key为k的结点，返回将它作为根结点。（2）若k<p.key，将k插入p结点的左子树中并且修改p的左子树。（3）若k>p.key，将k插入p结点的右子树中并且修改p的右子树。（4）其他情况是k=p.key，说明树中已有关键字k，无须插入，直接返回p。6/81
2. 二叉排序树的插入和生成 在根结点p的二叉排序树中插入关键字为k的结点的过程如下： （1）若p为空，创建一个key为k的结点，返回将它作为根结点。 （2）若k<p.key，将k插入p结点的左子树中并且修改p的左子树。 （3）若k>p.key，将k插入p结点的右子树中并且修改p的右子树。 （4）其他情况是k=p.key，说明树中已有关键字k，无须插入，直 接返回p。 6/81
public voidInsertBST(int k)//插入一个关键字为k的结点LyInsertBSTi(r,k);4private BSTNode InsertBSTi(BSTNode P,int k)/ /在以p为根的BST中插入关键字为k的结点( if (p==null)1/空，新插入的元素为根结点p=new BSTNode();中p.key=k;else if (k<p.key)//插入到p的左子树中p.lchild=InsertBsTi(p.lchild,k);else if (k>p.key)1/插入到p的右子树中p.rchild=InsertBST1(p.rchild,k);return p;7/81
public void InsertBST(int k) //插入一个关键字为k的结点 { InsertBST1(r,k); } private BSTNode InsertBST1(BSTNode p,int k) //在以p为根的BST中插入关键字为k的结点 { if (p==null) //空,新插入的元素为根结点 { p=new BSTNode(); p.key=k; } else if (k<p.key) p.lchild=InsertBST1(p.lchild,k); //插入到p的左子树中 else if (k>p.key) p.rchild=InsertBST1(p.rchild,k); //插入到p的右子树中 return p; } 7/81
创建二叉排序树是从一个空树开始，先创建根结点，以后每插入一个关键字k，就调用一次InsertBST(k)算法将k插入到当前的二叉排序树中。//由关键字序列a创建一棵二叉排序树publicvoid CreateBsT(int[l a)//创建根结点(r=newBSTNode();r.key=a[0];//创建其他结点for(int i=1;i<a.length;i++)//插入关键字a[i]InsertBSTi(r,a[i]);8/81
创建二叉排序树是从一个空树开始，先创建根结点，以后每插入一个关 键字k，就调用一次InsertBST(k)算法将k插入到当前的二叉排序树中。 public void CreateBST(int[] a) //由关键字序列a创建一棵二叉排序树 { r=new BSTNode(); //创建根结点 r.key=a[0]; for (int i=1;i<a.length;i++) //创建其他结点 InsertBST1(r,a[i]); //插入关键字a[i] } 8/81
【例9.8】已知一组关键字为(25,18,46,2,53,39,32,4,74,67,60,11)按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树，并求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。9/81
【例9.8】 已知一组关键字为 （25,18,46,2,53,39,32,4,74,67,60,11） 按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排 序树，并求在等概率的情况下查找成功的平均查找长度和查找不成功的平均 查找长度。 9/81
解：生成的二叉排序树如下。2518462531139327467602518463953生成的二叉排序树7432116610/81
解：生成的二叉排序树如下。 25 18 2 46 4 11 39 53 32 74 67 60 25 18 46 2 53 39 32 4 74 67 60 11 生成的二 叉排序树 10/81