树表的查找9.3几种特殊树形结构一统称为树表。这里的树表采用链式存储结构，由于链式存储结构既适合查找，也适合数据修改，属于动态查找表。对于动态查找表，不仅要讨论查找方法，还讨论修改方法1/81
几种特殊树形结构—统称为树表。 这里的树表采用链式存储结构，由于链式存储结构既适合查找，也适合 数据修改，属于动态查找表。 对于动态查找表，不仅要讨论查找方法，还讨论修改方法。 1/81
9.3.1二叉排序树1.二叉排序树的定义二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：若它的左子树非空，则左子树上所有结点值（默认为结点关键字）均小于根结点值。若它的右子树非空，则右子树上所有结点值均大于根结点值。左，右子树本身又各是一棵二叉排序树。2/81
1. 二叉排序树的定义 若它的左子树非空，则左子树上所有结点值（默认为结点关键字） 均小于根结点值。 若它的右子树非空，则右子树上所有结点值均大于根结点值。 左、右子树本身又各是一棵二叉排序树。 二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二 叉排序树或者是空树，或者是满足如下性质的二叉树： 2/81
一棵二叉排序树示例：根结点最左下结点，即为关键字最小的结点根结点最右下结点，即为关键字最大的结点8特点：中序序列：1，2，3，4，5，6，7，8中序序列是一个递增有序序列！3/81
一棵二叉排序树示例： 4 2 1 3 5 7 6 8 根结点最左下结 点，即为关键字 最小的结点 根结点最右下结点，即 为关键字最大的结点 特点： 中序序列：1，2，3，4，5，6，7，8 中序序列是一个递增有序序列！ 3/81
定义二叉排序树的结点类型如下//二叉排序树结点类class BSTNode//存放关键字，假设关键字为int类型publicint key;public BSTNode lchild;//存放左孩子指针1存放右孩子指针public BSTNode rchild;1/构造方法BSTNode(){lchild=rchild=null4/81
定义二叉排序树的结点类型如下： class BSTNode //二叉排序树结点类 { public int key; //存放关键字,假设关键字为int类型 public BSTNode lchild; //存放左孩子指针 public BSTNode rchild; //存放右孩子指针 BSTNode() //构造方法 { lchild=rchild=null; } } 4/81
设计二叉排序树类模板BSTClass//二叉排序树类public class BsTclass//二叉排序树根结点public BSTNode r;广//用于存放待删除结点的双亲结点private BSTNode f;1构造方法public BSTclass(){r=null;}1二叉排序树的基本运算算法5/81
设计二叉排序树类模板BSTClass public class BSTClass //二叉排序树类 { public BSTNode r; //二叉排序树根结点 private BSTNode f; //用于存放待删除结点的双亲结点 public BSTClass() //构造方法 { r=null; } //二叉排序树的基本运算算法 } 5/81
二叉排序树的插入和生成在根结点p的二叉排序树中插入关键字为k的结点的过程如下：（1）若p为空，创建一个key为k的结点，返回将它作为根结点。（2）若kp.key，将k插入p结点的右子树中并且修改p的右子树。（4）其他情况是k=p.key，说明树中已有关键字k，无须插入，直接返回p。6/81
2. 二叉排序树的插入和生成 在根结点p的二叉排序树中插入关键字为k的结点的过程如下： （1）若p为空，创建一个key为k的结点，返回将它作为根结点。 （2）若kp.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 (kp.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 (kp.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