树表的查找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<T>//二叉排序树类public class BsTclass//二叉排序树根结点public BSTNode r;广//用于存放待删除结点的双亲结点private BSTNode f;1构造方法public BSTclass(){r=null;}1二叉排序树的基本运算算法5/81
设计二叉排序树类模板BSTClass<T> public class BSTClass //二叉排序树类 { public BSTNode r; //二叉排序树根结点 private BSTNode f; //用于存放待删除结点的双亲结点 public BSTClass() //构造方法 { r=null; } //二叉排序树的基本运算算法 } 5/81