二叉查找树

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

增加 查找 删除 序列化

import java.util.ArrayList;
import java.util.List;


public class BinsearTree {

	private static Node rootNode = null ;

	private static List<Node> nodelist = new ArrayList<Node>();

	private class Node{
		private int key;
		private Node LeftchildNode;
		private Node rightchildNode;
		private Node parentNode;
		Node(int key,Node leftchildNode,Node rightNode,Node parentNode){
			this.key = key;
			this.LeftchildNode = leftchildNode;
			this.rightchildNode = rightNode;
			this.parentNode = parentNode;
		}
		public int getKey(){
			return key;
		}

	}

	public Boolean isEmpty(){
		if(rootNode == null){
			return true;
		}else{
			return false;
		}
	}

	public void insert(int k){
		Node parentNode = null;
		Node newNode = new Node(k, null, null, null);
		Node pNode = rootNode;
		if(rootNode ==null){
			rootNode = newNode;
			return;
		}
		while(pNode != null){
			parentNode = pNode;
			if(k<pNode.key){
				pNode = pNode.LeftchildNode;
			}else if(k>pNode.key){
				pNode = pNode.rightchildNode;
			}else{
				return;
			}
		}
		if(k<parentNode.key){
			parentNode.LeftchildNode = newNode;
			newNode.parentNode = parentNode;
		}else{
			parentNode.rightchildNode = newNode;
			newNode.parentNode = parentNode;
		}
	}

	public static void main(String[] args) {
		BinsearTree nodetreeBinsearTree = new BinsearTree();
		System.out.println("查找树是否为空？ " + (nodetreeBinsearTree.isEmpty() ? "是" : "否"));
		int[] src = {9,1,32,4,2,34,5,44,23,11,87,94,31};
		for(int k : src){
			nodetreeBinsearTree.insert(k);
		}
		System.out.println("查找树是否为空？ " + (nodetreeBinsearTree.isEmpty() ? "是" : "否"));
		System.out.println("最小关键字为:" + minnode(rootNode).getKey());
		System.out.println("最大关键字为:" + maxnode(rootNode).getKey());
		tranver(nodetreeBinsearTree);
		Node serNode = findnode(23);
		if(serNode == null){
			System.out.println("不含有该结点");
		}else{
			delate(serNode);
		}
		tranver(nodetreeBinsearTree);
	}

	private static void delate(Node node) {
		if(rootNode == null){
			System.out.println("树为空");
			return;
		}
		if(node==rootNode){
			rootNode = null;
			System.out.println("该节点是树的根节点，删除树成功!");
		}
		if(node.LeftchildNode==null && node.rightchildNode ==null){
			System.out.println("该节点无子节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = null;
			}else{
				node.parentNode.rightchildNode = null;
			}
			System.out.println("删除成功!");
			return;
		}
		if(node.rightchildNode==null){
			System.out.println("该节点有一个左节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = node.LeftchildNode;
			}else{
				node.parentNode.rightchildNode = node.LeftchildNode;
			}
			System.out.println("删除成功!");
			return;
		}
		if(node.LeftchildNode==null){
			System.out.println("该节点有一个右节点");
			if(node == node.parentNode.LeftchildNode){
				node.parentNode.LeftchildNode = node.rightchildNode;
			}else{
				node.parentNode.rightchildNode = node.rightchildNode;
			}
			System.out.println("删除成功!");
			return;
		}
		System.out.println("该节点有两个节点");
		Node node2 = maxnode(node.LeftchildNode);
		if(node == node.parentNode.LeftchildNode){
			node.parentNode.LeftchildNode = node2;
		}else{
			node.parentNode.rightchildNode = node2;
		}
		if(node2 != node.LeftchildNode){
			node2.parentNode.rightchildNode = null;
			node2.LeftchildNode = node.LeftchildNode;
			node.LeftchildNode.parentNode = node2.LeftchildNode;
		}
		node2.parentNode = node.parentNode;
		node2.rightchildNode = node.rightchildNode;
		node.rightchildNode.parentNode = node2.rightchildNode;
		System.out.println("删除成功!");
	}

	private static Node findnode(int key) {
		if(rootNode == null){
			System.out.println("树为空");
		}
		Node prodeNode = rootNode;
		while(prodeNode != null){
			if(key<prodeNode.key){
				prodeNode = prodeNode.LeftchildNode;
			}else if(key>prodeNode.key){
				prodeNode = prodeNode.rightchildNode;
			}else{
				break;
			}
		}
		if(prodeNode != null){
			return prodeNode;
		}else{
			return null;
		}
	}

	private static void tranver(BinsearTree tree) {
		inmidtranver();
		System.out.println("对树进行有序化：");
		for(Node node : nodelist){
			System.out.print(node.key+" ");
		}
		System.out.println();
	}

	private static void  inmidtranver(){
		if(nodelist.size()>0){
			nodelist.clear();
		}
		midtranver(rootNode);
	}

	private static void midtranver(Node rootNode){
		if(rootNode == null){
			return;
		}
		midtranver(rootNode.LeftchildNode);
		nodelist.add(rootNode);
		midtranver(rootNode.rightchildNode);
	}

	private static Node minnode(Node rootNode) {
		if(rootNode == null){
			System.out.println("树为空 ");
		}
		while(rootNode.LeftchildNode  !=null){
			rootNode = rootNode.LeftchildNode;
		}
		return rootNode;
	}

	private static Node maxnode(Node rootNode) {
		if(rootNode == null){
			System.out.println("树为空 ");
		}
		while(rootNode.rightchildNode  !=null){
			rootNode = rootNode.rightchildNode;
		}
		return rootNode;
	}


}