树结构同时集成了数组查找迅速和链表添删迅速的优点。先来看看普通的搜索二叉树的实现：

package com.wly.algorithmbase.datastructure;/** * 二叉搜索树 * @author wly */public class BinaryTree {	private static BTreeNode root;	public static void main(String[] args) {				BinaryTree tree = new BinaryTree();		tree.insert(new BTreeNode(11, 23));		tree.insert(new BTreeNode(6, 12));		tree.insert(new BTreeNode(16, 51));		tree.insert(new BTreeNode(3, 32));		tree.insert(new BTreeNode(9, 42));		tree.insert(new BTreeNode(14, 52));		tree.insert(new BTreeNode(19, 62));		tree.insert(new BTreeNode(13, 72));		tree.insert(new BTreeNode(12, 82));						tree.find(2);		tree.print(root);		tree.delete(11);		tree.print(root);	}	/**	 * 插入节点	 * 关键在于缓存当前节点，检查当前节点的子节点	 */	public void insert(BTreeNode node) {		if(root == null) {			root = node;		} else {			BTreeNode currentNode = root;			BTreeNode parent;			while(true) {				parent = currentNode;				if(node.getKey() < currentNode.getKey()) {					currentNode = currentNode.getLeft();					if(currentNode == null) {						parent.setLeft(node);						return;					}				} else {					currentNode = currentNode.getRight();					if(currentNode == null) {						parent.setRight(node);						return;					}				}			}		}	}	/**	 * 根据关键字查找	 */	public BTreeNode find(int key) {		BTreeNode current = root;		while(true) {			if(current == null) {				System.out.println("未查找到key=" + key + "的节点");				return null;			} else {				if(current.getKey() > key) {					current = current.getLeft();				} else if(current.getKey() < key) {					current = current.getRight();				} else {					System.out.println("查找到key=" + key + ",data=" + current.getData() + "的节点");					return current;				}			}		}	}		/**	 * 根据key值删除节点,删除的成功与否取决于是否存在该节点	 * @param key	 * @return true删除成功，false删除失败	 */	public boolean delete(int key) {		BTreeNode deleteNode = find(key);		if(deleteNode == null) {			System.out.println("未查找到key=" + key + "的节点，无法进行删除");			return false;		} else {			removeFromTree(deleteNode);			System.out.println("成功删除key=" + key + "的节点");			return true;		}	}		/**	 * 将自身从树中移除	 */	public void removeFromTree(BTreeNode node) {		//1.自身不包含子节点		if(node.getLeft() == null && node.getRight() == null) { 			if(node.isLeft) {				node.getParent().setLeft(null);			} else {				node.getParent().setRight(null);			}		}				//2.包含一个子节点		if(node.getLeft() != null && node.getRight() == null) {			if(node.isLeft) {				node.getParent().setLeft(node.getLeft());			} else {				node.getParent().setRight(node.getLeft());			}		} else if(node.getLeft() == null && node.getRight() != null) {			if(node.isLeft) {				node.getParent().setLeft(node.getRight());			} else {				node.getParent().setRight(node.getRight());			}		}						//3.包含两个子节点		//查找后继节点		BTreeNode successorNode = node.getSuccessor(node);				//从树种移除该后继节点		if(successorNode.getParent() != null) {			if(successorNode.isLeft) {				successorNode.getParent().setLeft(null);			} else {				successorNode.getParent().setRight(null);			}		}		successorNode.setLeft(node.getLeft());		successorNode.setRight(node.getRight());		//从树中移除待删除节点，并用后继节点替换		if(node.getParent() != null) {			if(node.isLeft) {				node.getParent().setLeft(successorNode);			} else {				node.getParent().setRight(successorNode);			}		} else {			root = successorNode;		}	}		/**	 * 打印树结构	 */	public void print(BTreeNode node) {		if(node != null) {			System.out.print(node.getKey() + "|" + node.getData());			System.out.println();		}		if(node.getLeft() != null) {			print(node.getLeft());		}		if(node.getRight() != null) {			print(node.getRight());		}	}	}/** * 节点类 * @author wly * */class BTreeNode {	private BTreeNode left;	private BTreeNode right;		private BTreeNode parent;		boolean isLeft; //是左子节点吗，否则就是右子节点		int key; //检索关键字	int data; //包含的数据对象		public BTreeNode() {		super();	}		public BTreeNode(int key, int data) {		super();		this.key = key;		this.data = data;	}		public BTreeNode getLeft() {		return left;	}	public void setLeft(BTreeNode left) {		this.left = left;		if(left != null) {			left.parent = this;			left.isLeft = true;		}	}	public BTreeNode getRight() {		return right;	}	public void setRight(BTreeNode right) {		this.right = right;		if(right != null) {			right.parent = this;			right.isLeft = false;		}	}		public BTreeNode getParent() {		return parent;	}	public void setParent(BTreeNode parent) {		this.parent = parent;			}	public int getKey() {		return key;	}	public void setKey(int key) {		this.key = key;	}	public int getData() {		return data;	}	public void setData(int data) {		this.data = data;	}		/**	 * 返回指定节点的后继节点(即大于指定节点的最小节点)	 * @param node	 * @return	 */	public BTreeNode getSuccessor(BTreeNode node) {		BTreeNode result = node.getRight(); //先取得右节点		if(result == null) {			return null;		} else {			while(result.getLeft() != null) {				result = result.getLeft();			}		}		return result;	}}

运行结果：

未查找到key=2的节点11|236|123|329|4216|5114|5213|7212|8219|62查找到key=11,data=23的节点成功删除key=11的节点12|826|123|329|4216|5114|5213|7219|62

O啦~~~

转载请保留出处：

谢谢!!