算法研究系列---二叉查找树
查找树以便于查找的方式来存放数据，尤其是二叉查找树，二叉查找树的特性使其可以使用简单的递归算法进行查找，这种算法在思路上类似于数组的折半查找，且同样高效.
?
?二叉查找树是其节点含有Comparable的对象，并且按如下组织的二叉树:
? ? ? ? ? ? 1:节点的数据大于节点的左子树中的数据。
? ? ? ? ? ? 2：节点的数据小于节点的右子树中的数据。
?
下面着重讨论如何基于java实现二叉查找树 并实现 诸如:插入，查找，删除,遍历等方法
?
?
package tree;public class BinaryTree {// Root node pointer. Will be null for an empty tree. private Node root; /* --Node-- The binary tree is built using this nested node class. Each node stores one data element, and has left and right sub-tree pointer which may be null. The node is a "dumb" nested class -- we just use it for storage; it does not have any methods. */ private static class Node { Node left; Node right; int data; Node(int newData) { left = null; right = null; data = newData; } } public BinaryTree() { root = null; } /** Returns true if the given target is in the binary tree. Uses a recursive helper. */ public boolean lookup(int data) { return(lookup(root, data)); } /** Recursive lookup -- given a node, recur down searching for the given data. */ private boolean lookup(Node node, int data) { if (node==null) { return(false); } if (data==node.data) { return(true); } else if (data<node.data) { return(lookup(node.left, data)); } else { return(lookup(node.right, data)); } } /** Inserts the given data into the binary tree. Uses a recursive helper. */ public void insert(int data) { root = insert(root, data); } /** Remove the given data into the binary tree Uses a recursive helper */ public void remove(int data){ remove(root, data); } private Node remove(Node node, int data) { if(node == null) { return null; } if(data < node.data) { node.left = remove(node.left,data); } else if(data > node.data) { node.right = remove(node.right,data); } else{ if(node.left != null && node.right != null) { node.data = findMax(node.right).data; node.right = removeMax(node.right); } else { node = ((node.left == null) ? node.right:node.left); } } return node; } private Node removeMax(Node node) { if(node != null) { if(node.right != null) { removeMax(node.right); } else { node = node.left; } } return node; } private Node findMax(Node node) { if(node != null) { while(node.right != null) { node = node.right; } } return node; } private Node remove2(Node node, int data) { if(node == null) { return node; } if(node.data < data) { node.right = remove2(node.right,data); } else if(node.data > data) { node.left = remove2(node.left,data); } else { if(node.left != null && node.right != null) { node.data = findMin(node.left).data; node.left = removeMin(node.left); } else { node = ((node.left == null) ? node.right:node.left); } } return node; } private Node removeMin(Node node) { if(node != null) { if(node.left != null) { removeMin(node.left); } else { node = node.right; } } return node; } private Node findMin(Node node) { if(node != null) { while(node.left != null) { node = node.left; } } return node; } private Node insert(Node node, int data) { if (node==null) { node = new Node(data); } else { if (data <= node.data) { node.left = insert(node.left, data); } else { node.right = insert(node.right, data); } } return(node); } /** * 中序历遍 */ public void inOrderTraverse() { inOrderTraverse(root); } /** * 先序历遍 */ public void preOrderTraverse(){ preOrderTraverse(root); } /** * 后序历遍 * @param node */ public void lastOrderTraverse(){ lastOrderTraverse(root); } private void lastOrderTraverse(Node node){ if(node != null) { lastOrderTraverse(node.left); lastOrderTraverse(node.right); System.out.print(node.data + " "); } } private void preOrderTraverse(Node node){ if(node != null) { System.out.print(node.data + " "); preOrderTraverse(node.left); preOrderTraverse(node.right); } } private void inOrderTraverse(Node node) { if(node == null) { return; } inOrderTraverse(node.left); System.out.print(node.data + " "); inOrderTraverse(node.right); }}?
?
package test;
import tree.BinaryTree;public class TestBinaryTree {/** * @param args */public static void main(String[] args) { BinaryTree biTree=new BinaryTree(); int[] data={2,1,3,5,4,55,1245}; for(int i=0; i < data.length; i++) { biTree.insert(data[i]); } biTree.preOrderTraverse(); System.out.println(); biTree.insert(5); biTree.preOrderTraverse(); System.out.println(); biTree.remove(2); biTree.inOrderTraverse(); System.out.println(); }}??
上述代码实现了一颗二叉查找树,并提供了插入，删除，遍历，查找节点的操作，下面一一解释各操作：
?
插入： ?往二叉查找树中插入元素是一个基本操作，因为它正是建树时的基本操作。假设已有一颗二叉查找树，如要往其中插入一个新元素，首先必须要确保节点间的相互关系，即需要保证插入元素后的树仍是一颗二叉查找树，并且须保证方法lookup能找到这个元素，同时，每次的插入操作都是给这棵树加上一个新的叶子节点.
?
遍历,查找:这两个操作比较简单，采用递归方式，具体实现如代码.
?
删除: ?删除操作可以说是最复杂的一个了，为了从二叉查找树中删除元素，需要将与之相匹配的元素传递给方法remove，待删除的元素随后从树中删除并返回, 如果不存在这样的元素则返回null
? ? 但是删除元素时，不是简单的删除就可以了,这里需要看待删除的元素的左右孩子的情况：
? ? ? ? ?1：节点没有孩子，为叶子节点
?2： 该节点有一个孩子
? ? ? ? ?3：该节点有两个孩子
?
第一种情况是最简单的，同时第二种情况也不难，只需要将该节点的一个孩子取代这个节点就可以了，这两种情况的处理可以合二为一,具体实现如代码所示
?
下面考虑节点有两个孩子的情况：
?
? ? ? 假设待删除的节点为N，但现在N有两个孩子，如果试图删除它，就会留下两个没有双亲的孩子，尽管节点N可以被其中一个所取代，但总会有一个孩子没有双亲，即总有一个孩子没有被引用，所以删除节点N 的办法是不可行的.
? ? ?实际上，并不是非得删除节点N才能删除其中的元素，这里，不防寻找一个容易删除的节点,我们称为A，这个节点A只有一个孩子或者没有孩子，然后将节点N中的元素用A中的元素替代，随后删除节点A，并使树中仍然还有正确的元素，但是这里的一个问题，如何确定这个节点A，并保证树仍然为二叉查找树呢？ 显然，节点A是不可以随便选择的，它必须有可以合法的替代节点N中的元素的条件。
? ? ? 假设e为N中的元素，因为节点N有两个孩子，则e不可能是树中最小的元素，也不可能是最大元素，（为了讨论方便,假设树中没有重复元素）， ?并且书中没有重复的元素，若树中元素升序排列,所以有：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ...a<e<b...（a,b为节点N左右孩子的元素）
由于a为节点N的左子树中的元素,b为节点N右子树中的元素,且有上述关系，我们可以想到 a将是N左子树中最大的元素,b是右子树中最小的元素。现假定删除了还有a的节点X，并用a替代e，那么现在N的左子树中所有剩下的元素都小于a，满足所需条件，而且N的右子树中的所有的元素都大于e，从而也大于a，因此该树仍是二叉查找树.
?
? ? 那么如何寻找元素a呢? ? 假设以上论述能够找到适当的俄元素a，所以现在应寻找含有a的节点并且确认他没有两个孩子,为了找到比任一个指定节点中的元素更大的元素，需要查看这个节点的右孩子，因此，a位于这颗子树最右侧的节点R中, 节点R不可能有右孩子，因为如果他有的话，该孩子的元素就会大于a，因此节点R的孩子不可能多余一个,可以很容易的删除它。
?
下面总结上述讨论(由于节点N的右子树情况类似于左子树，不过右子树中我们只要找右子树中最左侧的节点就可以了):
?
? ? ?1： 删除位于有两个孩子的节点N中的元素e
? ? ? ? ? 找到N的左子树中最右侧的节点R
? ? ? ? ? 以节点R中的元素替代节点N的元素
? ? ? ? ? 删除节点R
?
? ? ?2：?删除位于有两个孩子的节点N中的元素e
? ? ? ? ? ?找到N的右子树中最左侧的节点L，
? ? ? ? ? ?以节点L中的元素替代节点N的元素，
? ? ? ? ? ?删除节点L
?
?
?
?
?
?
?
?
?
?
?