基于《数据结构Java语言描述》
定义 ：二叉排序树（Binary Sort Tree）也称为二叉查找树，它或者是一棵空树，或具有以下性质的二叉树：
（1）、若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
（2）、若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。
案例：
右边的二叉排序树中序遍历后，其结果是？
答：3 6 8 9 10 12 16 19 23 26 30 33
小结：二叉排序树的一个重要性质：若中序遍历一棵二叉树，可以得到一个结点值递增的有序序列。
总结：在根节点，比它小的数在左边，比它大的数在左边。
二叉排序树的查找算法思想：
- 若二叉排序树为空，则查找失败。
- 若二叉排序树非空，将给定关键字kx与根结点的关键字进行比较：
- 若相等，则查找成功，结束查找；
-若给定关键字kx小于根结点的关键字，则递归查找左子树； - 若给定关键字kx大于根结点的关键字，则递归查找右子树。
public static BiTNodesearchNode(BiTNode t, T kx) { // 若子树是空子树或子树根结点的关键字等于kx,返回t if (t == null || t.data.key.equals(kx)) { return t; } else if (kx.compareTo(t.data.key) < 0) { // 关键字小于当前子树的根结点的关键字 return searchNode(t.lchild, kx); // 在左子树继续查找 } else { return searchNode(t.rchild, kx); // 在右子树继续查找 } }
基于《数据结构JAVA语言描述》给出一个有序数组{16, 8, 6, 3, 10, 9, 12, 26, 19, 23, 33, 30 }
BinarySortTree类
public class BinarySortTree {
// 在二叉排序树中查找关键字为kx的结点，如果找到返回结点，否则返回null
public static BiTNode searchNode(BiTNode t, Integer kx) {
if (t == null || kx.equals(t.data.key)) {// 若子树是空子树或子树根结点的关键字等于kx,返回t
return t;
} else if (kx.compareTo((Integer) t.data.key) < 0) {// 关键字小于当前子树的根结点的关键字
return searchNode(t.lchild, kx);// 在左子树继续查找
} else {
return searchNode(t.rchild, kx);// 在右子树继续查找
}
}
// 在二叉排序树中插入关键字为kx的结点
public static BiTNode insertNode(BiTNode t, Integer kx) {
if (t == null) {// 空树的场合,返回根结点
t = createNode(kx);
} else {
if (kx.compareTo((Integer) t.data.key) < 0) {// 添加的结点关键字小于当前子树的根结点的关键字
if (t.lchild == null) {// 当前子树的左子树是null
t.lchild = createNode(kx);
} else {
insertNode(t.lchild, kx); // 递归的向左子树添加
}
} else if (kx.compareTo((Integer) t.data.key) > 0) {// 添加的结点关键字大于当前子树的根结点的关键字
if (t.rchild == null) {// 当前子树的右子树是null
t.rchild = createNode(kx);
} else {
insertNode(t.rchild, kx); // 递归的向右子树添加
}
} else {// 添加的结点关键字在二叉树中已存在，无需插入
System.out.println("kx已存在无需插入");
}
}
return t;
}
// 创建结点
public static BiTNode createNode(Integer kx) {
RecT data = new RecT(kx);
BiTNode node = new BiTNode(data, null, null);
return node;
}
// 在二叉排序树中删除关键字为kx的结点
//
public static BiTNode deleteNode(BiTNode t, Integer kx) {
if (t == null) {// 空树的场合，返回null
System.out.println("该二叉树是一棵空树");
return null;
} else {
// 1.找到要删除的结点 targetNode
BiTNode targetNode = searchNode(t, kx);
// 如果没有找到要删除的结点，返回null
if (targetNode == null) {
System.out.println("没有找到要删除的结点");
return t;
}
// 2.找到targetNode的父结点parent
BiTNode parent = searchParent(t, kx);
// 3.1删除叶子结点
if (targetNode.lchild == null && targetNode.rchild == null) {
if (parent != null) {// targetNode有父结点的场合
// 判断targetNode 是父结点的左子结点，还是右子结点
if (parent.lchild != null && parent.lchild.data.key.equals(kx)) { // 是左子结点
parent.lchild = null;
} else if (parent.rchild != null && parent.rchild.data.key.equals(kx)) {// 是右子结点
parent.rchild = null;
}
} else {// targetNode是根结点的场合
t = null;
return t;
}
} else if (targetNode.lchild != null && targetNode.rchild != null) { // 3.2删除有两棵子树的结点
t = delRightTreeMin(t, targetNode);// targetNode右子树中最小的结点替换targetNode，并删除该结点。
} else {// 3.3删除只有一棵子树的结点
if (targetNode.lchild != null) {// targetNode有左子树的场合
if (parent != null) {// targetNode有父结点的场合
if (parent.lchild != null && parent.lchild.data.key.equals(kx)) {// targetNode是 parent的左子结点
parent.lchild = targetNode.lchild;
} else {// targetNode是 parent的右子结点
parent.rchild = targetNode.lchild;
}
} else {// targetNode是根结点的场合
t = targetNode.lchild;
}
} else { // targetNode有右子树的场合
if (parent != null) {// targetNode有父结点的场合
if (parent.lchild != null && parent.lchild.data.key.equals(kx)) {// targetNode是 parent的左子结点
parent.lchild = targetNode.rchild;
} else { // targetNode是 parent的右子结点
parent.rchild = targetNode.rchild;
}
} else { // targetNode是根结点的场合
t = targetNode.rchild;
}
}
}
}
return t;
}
// 在二叉排序树中查找关键字为kx的父结点,如果没有找到，返回null,否则返回父结点
public static BiTNode searchParent(BiTNode t, Integer kx) {
BiTNode p = t;// 要查找的结点
BiTNode f = null;// 要查找的结点的父结点
while (p != null && !kx.equals(p.data.key)) {
f = p;
if (kx.compareTo((Integer) p.data.key) < 0) {
p = p.lchild;
} else {
p = p.rchild;
}
}
if (p == null) {// 没有找到关键字kx，返回null
return null;
} else {
return f;// 找到了关键字kx，返回父结点
}
}
// targetNode右子树中最小的结点替换targetNode，并删除该结点。返回删除结点后的树
public static BiTNode delRightTreeMin(BiTNode t, BiTNode targetNode) {
BiTNode p = targetNode.rchild;// P指向targetNode右子树
while (p.lchild != null) {// P指向targetNode右子树最小结点
p = p.lchild;
}
Integer min = (Integer) p.data.key;
t = deleteNode(t, min);// 删除targetNode右子树最小结点
targetNode.data.key = min;// targetNode结点关键字替换为最小值
return t;
}
}
BiTNode类
public class BiTNode{
public RecT data;// 结点的数据元素
public BiTNode lchild, rchild;// 结点的左右孩子
public BiTNode(RecT data, BiTNode lchild, BiTNode rchild) {
super();
this.data = data;
this.lchild = lchild;
this.rchild = rchild;
}
}
Test测试类
public class Test {
public static void main(String[] args) {
Integer[] keys = { 16, 8, 6, 3, 10, 9, 12, 26, 19, 23, 33, 30 };// 关键字序列
BiTNode t = null;
// 1.构建二叉排序树
for (int i = 0; i < keys.length; i++) {
t = BinarySortTree.insertNode(t, keys[i]);
}
// 2.中序遍历二叉排序树
System.out.println("中序遍历二叉排序树~");
infixOrderTree(t);
// 3.1删除结点9
t = BinarySortTree.deleteNode(t, new Integer(9));
// 中序遍历删除关键字9后的二叉排序树
System.out.println("删除关键字9后的二叉排序树~");
infixOrderTree(t);
// 3.2删除结点6
t = BinarySortTree.deleteNode(t, new Integer(6));
// 中序遍历删除关键字6后的二叉排序树
System.out.println("删除关键字6后的二叉排序树~");
infixOrderTree(t);
// 3.3删除结点33
t = BinarySortTree.deleteNode(t, new Integer(33));
// 中序遍历删除关键字33后的二叉排序树
System.out.println("删除关键字33后的二叉排序树~");
infixOrderTree(t);
// 3.4删除结点19
t = BinarySortTree.deleteNode(t, new Integer(19));
// 中序遍历删除关键字19后的二叉排序树
System.out.println("删除关键字19后的二叉排序树~");
infixOrderTree(t);
// 3.5删除结点10
t = BinarySortTree.deleteNode(t, new Integer(10));
// 中序遍历删除关键字10后的二叉排序树
System.out.println("删除关键字10后的二叉排序树~");
infixOrderTree(t);
// 3.6删除结点8
t = BinarySortTree.deleteNode(t, new Integer(8));
// 中序遍历删除关键字8后的二叉排序树
System.out.println("删除关键字8后的二叉排序树~");
infixOrderTree(t);
// 4. 查找关键字为23的结点
BiTNode node = BinarySortTree.searchNode(t, new Integer(23));
System.out.println("结点的关键字为：" + node.data.key);
}
// 中序遍历二叉排序树
public static void infixOrderTree(BiTNode t) {
if (t == null) {// 空树的场合
System.out.println("二叉排序树为空，不能遍历");
} else {
infixOrder(t);
System.out.println();
}
}
// 中序遍历
public static void infixOrder(BiTNode t) {
if (t.lchild != null) {// 递归遍历左子树
infixOrder(t.lchild);
}
System.out.print(t.data.key + " ");// 输出关键字
if (t.rchild != null) {// 递归遍历右子树
infixOrder(t.rchild);
}
}
}
如有不对请指正！
