binarysearchtree.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 185 行

/*
 * Copyright (C) 2000-2007 Wang Pengcheng <[e-mail]>
 * Licensed to the Wang Pengcheng under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The LGPL licenses this file to You under the GNU Lesser General Public
 * Licence, Version 2.0  (the "License"); you may not use this file except in
 * compliance with the License.  You may obtain a copy of the License at
 *
 *     http://www.gnu.org/licenses/lgpl.txt
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//2 Dec 2007
package cn.edu.whu.iss.algorithm.unit12;

import mypackage.tools.print.*;
import static cn.edu.whu.iss.algorithm.basictools.BasicSortTool.*;

public class BinarySearchTree<T> implements InterfaceBinarySearchTreeMethod<T>{

	private BinarySearchTreeElement<T> root;
	
	public void inorderTreeWalk(BinarySearchTreeElement<T> root) {
		if(root!=null){
			inorderTreeWalk(root.getLeftChild());
			P.rint(root.getObject()+" ");
			inorderTreeWalk(root.getRightChild());
		}
		
	}
	
	public void inorderTreeWalk() {
		inorderTreeWalk(root);
		P.rintln();
	}

	public T delete(T e) {
		BinarySearchTreeElement<T> z = searchNode(root,e);
		BinarySearchTreeElement<T> y,x;
		
		if( (z.getLeftChild()==null)||(z.getRightChild()==null)){
			y=z;
		}else{
			y = getSuccessor(z);
		}
		if(y.getLeftChild()!=null){
			x = y.getLeftChild();
		}else{
			x = y.getRightChild();
		}
		if(x!=null){
			x.setParent(y.getParent());
		}
		if(y.getParent()==null){
			root = x;
		}else{
			if(y==y.getParent().getLeftChild()){
				y.getParent().setLeftChild(x);
			}else{
				y.getParent().setRightChild(x);
			}
		}
		if(y!=z){
			z.setObject(y.getObject());
		}
		
		return y.getObject();
	}

	public T insert(T e) {
		BinarySearchTreeElement<T> z = new BinarySearchTreeElement<T>(e);
		BinarySearchTreeElement<T> y = null;
		BinarySearchTreeElement<T> x = root;
		while(x!=null){
			y=x;
			if(compare(z,x)<0){
				x = x.getLeftChild();
			}else{
				x = x.getRightChild();
			}
		}
		z.setParent(y);
		if(y==null){
			root = z;
		}else if(compare(z,y)<0){
			y.setLeftChild(z);
		}else{
			y.setRightChild(z);
		}
		return z.getObject();
	}

	public T getMax() {
		BinarySearchTreeElement<T> t = getMax(root);
		return t.getObject();
	}
	
	private BinarySearchTreeElement<T> getMax(BinarySearchTreeElement<T> e){
		while(e.getRightChild()!=null){
			e = e.getRightChild();
		}
		return e;
	}

	public T getMin() {
		BinarySearchTreeElement<T> t = getMin(root);
		return t.getObject();
	}
	
	private BinarySearchTreeElement<T> getMin(BinarySearchTreeElement<T> e){
		while(e.getLeftChild()!=null){
			e = e.getLeftChild();
		}
		return e;
	}

	public T getPredecessor(T o) {
		BinarySearchTreeElement<T> t = searchNode(root,o);
		t = getPredecessor(t);
		return t.getObject();
	}
	
	private BinarySearchTreeElement<T> getPredecessor(BinarySearchTreeElement<T> x){
		if(x.getLeftChild()!=null){
			return getMax(x.getLeftChild());
		}else{
			BinarySearchTreeElement<T> y = x.getParent();
			while( (y!=null)&&(x==y.getLeftChild())){
				x=y;
				y=x.getParent();
			}
			return y;
		}
	}
	
	public T search(T key) {
		return search(root,key);
	}
	
	public T search(BinarySearchTreeElement<T> x,T key){
		BinarySearchTreeElement<T> e = searchNode(x, key);
		if(e==null){
			return null;
		}else{
			return e.getObject();
		}
	}
	
	private BinarySearchTreeElement<T> searchNode(BinarySearchTreeElement<T> x,T key){
		while( (x!=null)&&(compare(key,x.getObject())!=0) ){
			if(compare(key,x.getObject())<0){
				x = x.getLeftChild();
			}else{
				x = x.getRightChild();
			}
		}
		return x;
	}

	private BinarySearchTreeElement<T> getSuccessor(BinarySearchTreeElement<T> x){
		if(x.getRightChild()!=null){
			return getMin(x.getRightChild());
		}else{
			BinarySearchTreeElement<T> y = x.getParent();
			while( (y!=null)&&(x==y.getRightChild())){
				x=y;
				y=x.getParent();
			}
			return y;
		}
	}
	
	public T getSuccessor(T o) {
		BinarySearchTreeElement<T> t = searchNode(root, o);
		t = getSuccessor(t);
		return t.getObject();
	}

}