Java实现二叉搜索树
定义
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。
结构
二叉搜索树的建立过程．
特点
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
遍历
前序遍历
规则：若二叉树为空，则空操作返回，否则先访问根节点，再前序遍历左子树，再后序遍历右子树.
遍历结果：Ａ－Ｂ－Ｄ－Ｅ－Ｃ－Ｆ－Ｇ－Ｈ
中序遍历
规则：若二叉树为空，则空操作返回，否则先从根节点开始（注意不是先访问根节点），再中序遍历左子树，然后是访问根节点，再中序遍历右子树.
遍历结果：Ｄ－Ｂ－Ｅ－Ａ－Ｆ－Ｃ－Ｇ－Ｈ
后序遍历
规则：若二叉树为空，则空操作返回，否则先从根节点开始（注意不是先访问根节点），再中序遍历左子树，再中序遍历右子树，然后是访问根节点.
遍历结果：Ｄ－Ｅ－Ｂ－Ｆ－Ｈ－Ｇ－Ｃ－Ａ
可以从图形和遍历方式推倒出遍历结果，也可以从遍历结果和遍历方式推倒出图形．
实例
创建节点
从上面的结构可以看出节点包括三个属性，节点值，左子节点引用和右子节点引用.
public class Node {
//节点值
int val;
//左子节点引用
Node leftChild;
//右子节点引用
Node rightChild;
public void printNode() {
System.out.println(val);
}
}
创建二叉搜索树
该类只有一个私有属性root以及相关方法，该私有属性指向其根节点.
也可以添加size作为节点数．
public class BinaryTree {
private Node root;
}插入节点
比如在上面的二叉搜索树插入35的值：
１.从根节点开始比较，35＜50，从左子树查找插入位置，
parent = current; current=root.leftChild(25);
２．35>25,说明在其右子树添加，
parent = current; current=root.leftChild(null);
此时current＝＝null,因此新节点30就在该位置添加.
parent.rightChild = newＮode(３０);
public void insert(int data) {
Node newNode = new Node();
newNode.val = data;
if(root == null) {
//如果是第一个节点，也就是根节点为null,直接创建一个新的节点即可
root = newNode;
}
else {
Node current = root;
//current节点的父节点
Node parent;
//循环查找插入的位置
while(true) {
parent = current;
//如果插入的值小于当前节点的值，从左子树查找
if(data < current.val) {
current = current.leftChild;
//直到当前节点为null
if(current == null) {
//设置当前节点的父节点的左子节点为新创建的节点
parent.leftChild = newNode;
return;
}
}
//如果插入的值大于当前节点的值，从左子树查找
else {
current = current.rightChild;
//直到当前节点为null
if(current == null) {
//设置当前节点的父节点的右子节点为新创建的节点
parent.rightChild = newNode;
return;
}
}
}// end of while(true)
}
}查找节点
查找节点也是根据其特点进行查找，某个节点的值总比左子树的值大，比右子树的值小或者等于．
public Node find(int value) {
Node current = root;
while(current.val != value) {
if(value < current.val) {
current = current.leftChild;
}
else {
current = current.rightChild;
}
if(current == null) {
return null;
}
}
return current;
}删除节点
删除节点比较复杂，因为会出现以下几种情况；
１．删除的节点为叶节点，这个比较好处理，直接将该节点设置为null．
2．当删除的是中间节点，其子树如何处理．
２.1 存在左子节点
2.2 存在右子节点
2.3 存在左右子节点
public boolean delete(int value) {
Node current = root;
Node parent = root;
boolean isLeft = false;
boolean isRight = false;
//查找所要删除的节点的左子节点还是右子节点
while(current.val != value) {
parent = current;
isLeft = false;
isRight = false;
if(value < current.val) {
current = current.leftChild;
isLeft = true;
}
else {
current = current.rightChild;
isRight = true;
}
}
//不存在该值
if(current == null) {
return false;
}
//是叶子节点，不存在子节点
if((current.leftChild == null)
&& (current.rightChild == null)) {
System.out.println("是叶子节点，不存在子节点");
if(isLeft) {
//如果是左子节点，设父节点的左子节点为null
parent.leftChild = null;
}
else if(isRight) {
//如果是右子节点，设父节点的右子节点为null
parent.rightChild = null;
}
return true;
}
//存在左子节点
else if((current.leftChild != null)
&& (current.rightChild == null)) {
System.out.println("不是叶子节点，存在左子节点");
if(isLeft) {
parent.leftChild = current.leftChild;
}
else if(isRight) {
parent.rightChild = current.leftChild;
}
current = null;
return true;
}
//存在右子节点
else if((current.leftChild == null)
&& (current.rightChild != null)) {
System.out.println("不是叶子节点，存在右子节点");
if(isLeft) {
parent.leftChild = current.rightChild;
}
else if(isRight) {
parent.rightChild = current.rightChild;
}
current = null;
return true;
}
//左右子节点都存在
else {
System.out.println("不是叶子节点，存在左右子节点");
if(isLeft) {
parent.leftChild = current.rightChild;
Node currentLeft = current.rightChild;
Node parentLeft = currentLeft;
while(currentLeft != null) {
parentLeft = currentLeft;
currentLeft = currentLeft.leftChild;
}
parentLeft.leftChild = current.leftChild;
current = null;
}
else if(isRight) {
parent.rightChild = current.rightChild;
Node currentLeft = current.rightChild;
Node parentLeft = currentLeft;
while(currentLeft != null) {
parentLeft = currentLeft;
currentLeft = currentLeft.leftChild;
}
parentLeft.leftChild = current.leftChild;
current = null;
}
return true;
}
}遍历
前序遍历
public void preOrder(Node localNode) {
if(localNode != null) {
System.out.println(localNode.val);
preOrder(localNode.leftChild);
preOrder(localNode.rightChild);
}
}中序遍历
由于中序遍历是根据左(小)－中(中)－右(大)，
因此，中序遍历所获得的数据是单调递增的．
public void inOrder(Node localNode) {
if(localNode != null) {
inOrder(localNode.leftChild);
System.out.println(localNode.val);
inOrder(localNode.rightChild);
}
}后序遍历
public void posOrder(Node localNode) {
if(localNode != null) {
posOrder(localNode.leftChild);
posOrder(localNode.rightChild);
System.out.println(localNode.val);
}
}查找最小值
最小值一定位于根节点的左子树中，因此一直从根节点开始一直遍历其左子树，直到该节点没有左子节点．
public Node getMin() {
Node current = root,last = null;
while(current != null) {
last = current;
current = current.leftChild;
}
return last;
}
查找最大值
最小值一定位于根节点的右子树中，因此一直从根节点开始一直遍历其右子树，直到该节点没有右子节点．
public Node getMax() {
Node current = root,last = null;
while(current != null) {
last = current;
current = current.rightChild;
}
return last;
}打印二叉搜索树的树形结构
public void printTree(Node head) {
System.out.println("-----------------\r\nBinary Tree:");
printInOrder(head, 0, "Root-", 8);
System.out.println();
}
public void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.rightChild, height + 1, "R-", len);
String val = to + head.val;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val;// + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.leftChild, height + 1, "L-", len);
}
public String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
} 存在的问题
二叉搜索树插入时是按照一定规则进行插入的，因此在中序遍历时获得的数据是有序的，比如下面查找35，只需要比较３次就可以获得结果，因此插入或者查找的效率还是比较高的．
但是存在的一个问题是，如果插入的数据是单调变化的，那就变成了线性链表，最后导致查找效率降低．
因此，也就出现了其他更好的二叉树数据结构，比如红黑树，红黑树是一种平衡的二叉树，后面琢磨明白了再另写一篇进行说明．
上一篇： jQuery实现美观的多级动画效果菜单代码_jquery
下一篇： 二叉搜索树的后序遍历序列