当前位置:首页 > 开发 > 编程语言 > Java > 正文

Java实现-二叉查找树(BST)的操作

发表于: 2012-03-20   作者:bylijinnan   来源:转载   浏览次数:
摘要: see also: http://blog.csdn.net/jiqiren007/article/details/6534810 import java.util.LinkedList; import ljn.help.*; public class OperationsOnBinarySearchTree { /** * It shows the operat
see also: http://blog.csdn.net/jiqiren007/article/details/6534810
import java.util.LinkedList;

import ljn.help.*;
public class OperationsOnBinarySearchTree {

	/**
	 * It shows the operations on Binary Search Tree.
	 * see also: http://blog.csdn.net/jiqiren007/article/details/6534810
	 */
	private Node root;
	public static void main(String[] args) {
		int[] data={12,5,18,2,9,15,19,0,0,8,0,0,17,};
	  /*    12                                                     
           /   \                                                    
          5     18                                                   
        /   \   / \
       2     9 15  19
            /    \
           8      17
       */
		OperationsOnBinarySearchTree bst=new OperationsOnBinarySearchTree(data);
		bst.levelTraverse();
		bst.insert(13);
		bst.levelTraverse();
		bst.delete(13);
		bst.levelTraverse();
		bst.delete(12);
		bst.levelTraverse();
		bst.inOrder(bst.root);
		
	}
	public OperationsOnBinarySearchTree(int[] data){
		root=Helper.createTree(data);
	}
	
	public void delete(int dataDelete){
		if(root==null){
			return;
		}
		Node curNode=root;
		NodePair pair=findNodeAndParent(curNode,dataDelete);
		Node nodeDelete=pair.son;
		Node parent=pair.parent;
		if(nodeDelete==null){
			return;
		}
		if(isLeaf(nodeDelete)){
			if(parent.getLeft()==nodeDelete){
				parent.setLeft(null);
			}
			if(parent.getRight()==nodeDelete){
				parent.setRight(null);
			}
		}else{
			if( hasLeftOnly(nodeDelete)	){
				if(parent.getLeft()==nodeDelete){
					parent.setLeft(nodeDelete.getLeft());
				}
				if(parent.getRight()==nodeDelete){
					parent.setRight(nodeDelete.getLeft());
				}
			}else if( hasRightOnly(nodeDelete)	){
				if(parent.getLeft()==nodeDelete){
					parent.setLeft(nodeDelete.getRight());
				}
				if(parent.getRight()==nodeDelete){
					parent.setRight(nodeDelete.getRight());
				}
			}else{//has both left child and right child.Successor is in the min(curNode.getRight())
				NodePair tmpPair=min(nodeDelete.getRight());
				Node successor=tmpPair.son;
				Node sParent=tmpPair.parent;
				nodeDelete.setData(successor.getData());
				if(null==sParent){
					nodeDelete.setRight(null);
				}else{
					sParent.setLeft(successor.getRight());
				}
			}
		}
		
		
	}
	
	public NodePair findNodeAndParent(Node curNode,int data){
		if(curNode==null){
			return null;
		}
		Node parent=null;
		Node son=null;
		NodePair pair=null;
		while(curNode!=null){
			int curData=curNode.getData();
			if(curData==data){
				son=curNode;//when curNode.getData()==data,'parent' is null.Is it OK?
				break;
			}
			if(data<curData){
				parent=curNode;
				curNode=curNode.getLeft();
			}
			if(data>curData){
				parent=curNode;
				curNode=curNode.getRight();
			}
		}
		pair=new NodePair(son,parent);
		return pair;
	}
	public boolean hasLeftOnly(Node node){
		return node!=null&&node.getLeft()!=null&&node.getRight()==null;
	}
	public boolean hasRightOnly(Node node){
		return node!=null&&node.getRight()!=null&&node.getLeft()==null;
	}
	public boolean isLeaf(Node node){
		return node!=null&&node.getLeft()==null&&node.getRight()==null;
	}
	public NodePair min(Node curNode){
		if(curNode==null){
			return null;
		}
		Node parent=null;
		while(curNode.getLeft()!=null){//when 'curNode' has no left child,'curNode' is min,and its parent is null(ok?)
			parent=curNode;
			curNode=curNode.getLeft();
		}
		return new NodePair(curNode,parent);
	}
	
	//we don't get 'max''s parent node like 'min'
	public Node max(Node curNode){
		if(curNode==null){
			return null;
		}
		while(curNode.getRight()!=null){
			curNode=curNode.getRight();
		}
		return curNode;
	}
	
	
	public Node find(int target){
		if(root==null){//empty tree
			return null;
		}else{
			return findHelp(root,target);
		}
	}
	public Node findHelp(Node curNode,int target){
		Node result=null;
		int curData=curNode.getData();
		if(target==curData){
			result=curNode;
		}
		if(target<curData){
			findHelp(curNode.getLeft(),target);
		}
		if(target>curData){
			findHelp(curNode.getRight(),target);
		}
		return result;
	}
	
	public void insert(int dataInsert){
		if(root==null){//the tree is empty
			root=new Node(dataInsert);
		}else{
			insertHelp(root,dataInsert);
		}
	}
	
	public void insertHelp(Node curNode,int dataInsert){
		Node nodeToInsert=new Node(dataInsert);
		int curData=curNode.getData();
		if(dataInsert<=curData){//insert into left tree
			Node left=curNode.getLeft();
			if(left==null){
				curNode.setLeft(nodeToInsert);
			}else{
				insertHelp(left,dataInsert);
			}
		}
		if(dataInsert>curData){//insert into right tree
			Node right=curNode.getRight();
			if(right==null){
				curNode.setRight(nodeToInsert);
			}else{
				insertHelp(right,dataInsert);
			}
		}
	}
		
	public void levelTraverse(){
		if(root==null){
			return;
		}
		Node node=root;
		LinkedList<Node> queue=new LinkedList<Node>();
		queue.addLast(node);
		while(!queue.isEmpty()){
			node=queue.removeFirst();
			System.out.print(node.getData()+" ");
			if(node.getLeft()!=null){
				queue.addLast(node.getLeft());
			}
			if(node.getRight()!=null){
				queue.addLast(node.getRight());
			}
		}
		System.out.println();
	}
	
	public void inOrder(Node curNode){
		if(curNode==null){
			return;
		}
		inOrder(curNode.getLeft());
		System.out.print(curNode.getData()+" ");
		inOrder(curNode.getRight());
	}
	//when deleting a node,we need the node and its parent.
	private static class NodePair{
		
		Node son;
		Node parent;
		
		NodePair(Node son,Node parent){
			this.son=son;
			this.parent=parent;
		}
		
	}
	
}

Java实现-二叉查找树(BST)的操作

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
概要 在前面分别介绍了"二叉查找树的相关理论知识,然后给出了二叉查找树的C和C++实现版本"。这一章
Java实现二叉查找树(Binary Search Tree) Java实现二叉查找树(Binary Search Tree) 对数:(底
C++数据结构之二叉查找树(BST) 二分查找法在算法家族大类中属于“分治法”,二分查找的过程比较简
//二叉搜索树 public class BinarySearchTree<T extends Comparable<? super T>> { /**
间时紧张,先记一笔,后续优化与完善。 媒介 后面一篇文章,笔者就二叉找查树行进了一些解释与实现
转载http://hxraid.iteye.com/blog/609312 当所有的静态查找结构添加和删除一个数据的时候,整个结
一棵AVL树是其每个节点的左右子树的高度最多相差1的二叉查找树(这里主要研究AVL树的插入操作) 当
对于二叉查找树的每个节点Node,它的左子树中所有的关键字都小于Node的关键字,而右子树中的所有关
二叉查找树描述 二叉查找树的性质:对于树中的每个结点X,它的左子树中所有关键字值小于X的关键值,
原文URL: http://www.cnblogs.com/CareySon/archive/2012/04/19/ImpleBinaryTreeWithCSharp.html 简
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号