算法研究系列---二叉查找树

查找树以便于查找的方式来存放数据，尤其是二叉查找树，二叉查找树的特性使其可以使用简单的递归算法进行查找，这种算法在思路上类似于数组的折半查找，且同样高效.

 

 二叉查找树是其节点含有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