-
Java代码
/**
* 二叉搜索树,不可以保存null.可以保存相同的元素
* 二叉搜索树,左子树小于父节点,右子树大于父节点.
*/
public class BinarySearchTree {
//数据数量
private int size;
//根节点,null表示为空树
private Node root;
//节点对象
private class Node {
//保存数据
int elem;
//保存相同数据数量
int number;
//指向左孩子
Node lChildren;
//指向右孩子
Node rChildren;
//指向父节点,在删除的时候比较容易定位。
Node parent;
public Node(int elem, Node lChildren, Node rChildren, Node parent) {
this.elem = elem;
this.lChildren = lChildren;
this.rChildren = rChildren;
this.parent = parent;
number = 1;
}
}
/**
* 添加元素,不能添加null
*/
BinarySearchTree addNode(Integer elem) {
if (elem == null) {
throw new UnsupportedOperationException("不能插入空元素");
}
Node addNode = new Node(elem, null, null, null);
if (root == null) {
root = addNode;
} else {
//遍历插入
addNode(root, addNode);
}
size++;
return this;
}
/**
* 遍历添加节点
* 终止条件:添加到合适的位置
* 如果已经存在相同的数据则将节点的number+1
* 根节点的数据小于添加节点的数据,则遍历根节点的右子树
* 根节点的数据大于添加节点的数据,则遍历根节点的左子树
* 总是添加到叶子节点
*
* @param parent 根节点
* @param addNode 添加的节点
*/
private void addNode(Node parent, Node addNode) {
if (parent.elem < addNode.elem) {
if (parent.rChildren != null) {
addNode(parent.rChildren, addNode);
} else {
addNode.parent = parent;
parent.rChildren = addNode;
}
} else if (parent.elem > addNode.elem) {
if (parent.lChildren != null) {
addNode(parent.lChildren, addNode);
} else {
addNode.parent = parent;
parent.lChildren = addNode;
}
} else {
parent.number++;
}
}
int height() {
return height(root);
}
/**
* 递归求树的高度
* 终止条件:根节点为null,返回0
* 求右子树高度rightSize
* 求左子树高度leftSize
*
* @param parent 根节点
* @return 返回左子树高度和右子树高度的最大值。也即是树的高度
*/
private int height(Node parent) {
if (parent == null) {
return 0;
}
int leftSize = 1 + height(parent.lChildren);
int rightSize = 1 + height(parent.rChildren);
return Math.max(leftSize, rightSize);
}
void inOrderPrint() {
inOrderPrint(root);
}
/**
* 中序遍历 左节点--根节点--有节点
*
* @param root
*/
private void inOrderPrint(Node root) {
if (root != null) {
//递归左子树
inOrderPrint(root.lChildren);
System.out.println("elem:" + root.elem + ",number:" + root.number);
//递归右子树
inOrderPrint(root.rChildren);
}
}
int size() {
return size;
}
/**
* 删除元素,若元素存在1个以上则将该节点的number - 1
*
* @param elem 待删除的元素
* @return true:删除成功<br/> false:删除失败(没有查询到)
*/
Integer del(Integer elem) {
return del(root, elem);
}
/**
* 删除节点一共分为三大类情况
* delNode:删除节点,delParent:delNode的父节点,root:根节点
* 1:delNode没有子树
* (1):删除root,也即是delNode的parent==null。直接将root置空
* (2):删除非root,delParent和delNode断开连接也即是delParent.rChildren=null(or delParent.lChildren=null)
* 2:delNode只有一个子树
* (1):删除root,将root指向delNode
* (2):删除非root,将delParent的下一个节点指向delNode的子节点
* 也即是delParent.rChildren=delParent.rChildren(or delParent.lChildren=delParent.lChildren)
* 3:delNode有两个子树
* Step One:找寻delNode左子树的最大节点MaxNode(or 找寻右子树的最小节点MinNode),交换delNode和MaxNode(or MinNode)的数据
* Step Two:
* (1):delNode左子树的maxNode为delNode.lChildren(or delNode右子树的minNode为delNode.rChildren)
* delNode.lChildren=maxNode.lChildren(or delNode.rChildren=minNode.rChildren)
* (2):delNode左子树的maxNode不是delNode.lChildren(or delNode右子树的minNode不是delNode.rChildren)
* delNode.parent.rChildren=maxNode.lChildren(or delNode.parent.lChildren=minNode.rChildren)
*
* @param parent
* @param elem
* @return
*/
private Integer del(Node parent, Integer elem) {
//搜索待删除的元素
Node node = searchNode(parent, elem);
if (node == null) {
return null;
}
Integer result = node.elem;
if (node.number != 1) {
node.number--;
return result;
}
Node delParent = node.parent;
//删除节点没有孩子
if (node.lChildren == null && node.rChildren == null) {
//删除的为根节点
if (delParent == null) {
//根节点
root = null;
} else {
//判断是左孩子还是右孩子
if (delParent.lChildren == node) {
delParent.lChildren = null;
} else {
delParent.rChildren = null;
}
//Help GC
node.parent = null;
}
}
//删除节点只有一个孩子
if (node.lChildren != null && node.rChildren == null) {
//删除的为根节点
if (delParent == null) {
//根节点 node == root
root = node.lChildren;
root.parent = null;
//Help GC
node.lChildren = null;
} else {
delParent.lChildren = node.lChildren;
node.lChildren.parent = delParent;
//Help GC
node.lChildren = null;
node.parent = null;
}
}
if (node.lChildren == null && node.rChildren != null) {
if (delParent == null) {
//根节点
root = node.rChildren;
root.parent = null;
//Help GC
node.rChildren = null;
} else {
//断开连接
delParent.rChildren = node.rChildren;
//添加父节点
node.rChildren.parent = delParent;
//Help GC
node.rChildren = null;
node.parent = null;
}
}
//删除节点有两个孩子
if (node.rChildren != null && node.lChildren != null) {
//可能拥有左子树
Node maxNode = findMaxNode(node.lChildren);
//和当前节点交换内容
node.elem = maxNode.elem;
node.number = maxNode.number;
//获取删除元素的父节点
delParent = maxNode.parent;
//交换元素为删除元素的右节点
if (delParent == node) {
delParent.lChildren = maxNode.lChildren;
if (delParent.lChildren != null) {
delParent.lChildren.parent = delParent;
}
//Help GC
maxNode.lChildren = null;
maxNode.parent = null;
} else {
delParent.rChildren = maxNode.lChildren;
if (delParent.rChildren != null) {
delParent.rChildren.parent = delParent;
}
//Help GC
maxNode.parent = null;
maxNode.lChildren = null;
}
}
return result;
}
boolean search(Integer elem) {
return searchNode(root, elem) == null ? false : true;
}
private Node searchNode(Node parent, Integer elem) {
if (parent == null) {
return null;
}
if (parent.elem > elem) {
return searchNode(parent.lChildren, elem);
} else if (parent.elem < elem) {
return searchNode(parent.rChildren, elem);
} else {
return parent;
}
}
/**
* 查找元素最大节点
* 根据搜索二叉树的性质可知右子树所有节点的数据大于左子树的所有节点
* 因此只要找到最左的元素即可
*
* @param parent 根节点
* @return null:没找到<br/>otherwise:找到最大元素节点
*/
private Node findMaxNode(Node parent) {
if (parent == null) {
return null;
}
while (parent.rChildren != null) {
parent = parent.rChildren;
}
return parent;
}
/**
* 查找元素最小节点
* 根据搜索二叉树的性质可知左子树所有节点的数据小于右子树的所有节点
* 因此只要找到最右的元素即可
*
* @param parent 根节点
* @return null:没找到<br/>otherwise:找到最小元素节点
*/
private Node findMinNode(Node parent) {
if (parent == null) {
return null;
}
while (parent.lChildren != null) {
parent = parent.lChildren;
}
return parent;
}
-
测试
@Test
public void testBinarySearchTree() {
BinarySearchTree binarySearchTree = new BinarySearchTree();
/**
* 构造树：
* 1
* -1 5
* 0 4 6
* 8
* 7
*/
binarySearchTree.addNode(1)
.addNode(5)
.addNode(6)
.addNode(8)
.addNode(5)
.addNode(7)
.addNode(-1)
.addNode(0)
.addNode(4);
System.out.println("binarySearchTree height:" + binarySearchTree.height());
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.search(9));
System.out.println(binarySearchTree.search(4));
System.out.println(binarySearchTree.search(5));
System.out.println(binarySearchTree.search(6));
System.out.println(binarySearchTree.size());
System.out.println(binarySearchTree.del(7));
System.out.println(binarySearchTree.del(9));
/**
* 删除后：
* 1
* -1 5
* 0 4 6
* 8
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(6));
/**
* 删除后：
* 1
* -1 5
* 0 4 8
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(5));
System.out.println(binarySearchTree.del(5));
/**
* 删除后：
* 1
* -1 8
* 0 4
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(1));
/**
* 删除后：
* 8
* -1 4
* 0
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(4));
/**
* 删除后：
* 8
* -1
* 0
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(-1));
/**
* 删除后：
* 8
* 0
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(8));
/**
* 删除后：
* 0
*/
binarySearchTree.inOrderPrint();
System.out.println(binarySearchTree.del(0));
/**
* 删除后：
* null
*/
binarySearchTree.inOrderPrint();
}
测试结果
binarySearchTree height:5
elem:-1,number:1
elem:0,number:1
elem:1,number:1
elem:4,number:1
elem:5,number:2
elem:6,number:1
elem:7,number:1
elem:8,number:1
false
true
true
true
9
7
null
elem:-1,number:1
elem:0,number:1
elem:1,number:1
elem:4,number:1
elem:5,number:2
elem:6,number:1
elem:8,number:1
6
elem:-1,number:1
elem:0,number:1
elem:1,number:1
elem:4,number:1
elem:5,number:2
elem:8,number:1
5
5
elem:-1,number:1
elem:0,number:1
elem:1,number:1
elem:4,number:1
elem:8,number:1
1
elem:-1,number:1
elem:0,number:1
elem:4,number:1
elem:8,number:1
4
elem:-1,number:1
elem:0,number:1
elem:8,number:1
-1
elem:0,number:1
elem:8,number:1
8
elem:0,number:1
0
