package com.yunos.tv.test;

/**
 * 二叉树算法
 * 
 * @author 冻番茄 phpd.cn
 */
import com.alibaba.fastjson.JSON;

public class BstTest {

	public static void main(String[] args) {
		//初始化一个二叉树
		int[] n = { 8, 3, 10, 1, 6, 14, 4, 7, 13, 13, 1 };
		Node root = null;
		for (int i : n) {
			root = insert(root, i);
		}
		System.out.println(JSON.toJSONString(root, true));
		System.out.println(JSON.toJSONString(search(root, 6), true));
		root = delete(root, 8);
		root = delete(root, 1);
		System.out.println(JSON.toJSONString(root, true));
	}

	/**
	 * 二叉树删除节点
	 * @param node
	 * @param key
	 * @return
	 */
	private static Node delete(Node node, int key) {
		if (node == null) {
			return null;
		}
		//根据二叉树算法，当前节点小于key从左边查找并删除，反之从右边查找并删除
		if (key < node.getKey()) {
			node.setLeftNode(delete(node.getLeftNode(), key));
		} else if (key > node.getKey()) {
			node.setRightNode(delete(node.getRightNode(), key));
		} else {
			/*
			 * 查找到的话进行删除操作，删除分三种情况
			 * 1、该节点没有左右子节点则直接删除。
			 * 2、同时有左节点并且有右节点需要从最左边取最大节点替换或从最右边取最小节点替换。
			 * 3、只有左节点或只有右节点，把左节点或右节点直接替换被删除的节点
			 */
			if (node.getLeftNode() == null && node.getRightNode() == null) {
				node = null;
			} else if (node.getLeftNode() != null && node.getRightNode() != null) {
				//从左边查找最大节点进行替换
				node = deleteByLeft(node, node.getLeftNode(), key);
				//从右边查找最小节点进行替换
				//node = deleteByRight(node, node.getRightNode(), key);
			} else if (node.getLeftNode() != null) {
				node = node.getLeftNode();
			} else if (node.getRightNode() != null) {
				node = node.getRightNode();
			}
		}
		return node;
	}

	/**
	 * 要删除的节点同时有左右子节点时，从该删除节点右边查找出最小值的节点替换到删除的节点位置
	 * @param sourceNode
	 * @param rightNode
	 * @param key
	 * @return
	 */
	private static Node deleteByRight(Node sourceNode, Node rightNode, int key) {
		if (rightNode.getLeftNode() == null) {
			sourceNode.setKey(rightNode.getKey());
			Node tmp = delete(sourceNode.getRightNode(), rightNode.getKey());
			sourceNode.setRightNode(tmp);
			return sourceNode;
		}
		return deleteByRight(sourceNode, rightNode.getLeftNode(), key);

	}
	
	/**
	 * 要删除的节点同时有左右子节点时，从该删除节点左边查找出最大值的节点替换到删除的节点位置
	 * @param sourceNode
	 * @param leftNode
	 * @param key
	 * @return
	 */
	private static Node deleteByLeft(Node sourceNode, Node leftNode, int key) {

		if (leftNode.getRightNode() == null) {
			sourceNode.setKey(leftNode.getKey());
			Node tmp = delete(sourceNode.getLeftNode(), leftNode.getKey());
			sourceNode.setLeftNode(tmp);
			return sourceNode;
		}
		return deleteByLeft(sourceNode, leftNode.getRightNode(), key);

	}

	/**
	 * 在二叉树中快速查找一个节点
	 * @param node
	 * @param key
	 * @return
	 */
	private static Node search(Node node, int key) {
		if (node == null) {
			return null;
		}
		if (node.getKey() == key) {
			return node;
		}
		if (node.getKey() > key) {
			return search(node.getLeftNode(), key);
		} else {
			return search(node.getRightNode(), key);
		}
	}

	/**
	 * 在二叉树中插入一个节点
	 * @param node
	 * @param key
	 * @return
	 */
	private static Node insert(Node node, int key) {
		if (node == null) {
			node = new Node();
			node.setKey(key);
		} else if (key == node.getKey()) {
			return node;
		} else if (key < node.key) {
			node.setLeftNode(insert(node.getLeftNode(), key));
			return node;
		} else {
			node.setRightNode(insert(node.getRightNode(), key));
		}
		return node;
	}

	public static class Node {

		private int		key;
		private Node	leftNode;
		private Node	rightNode;

		public int getKey() {
			return key;
		}

		public void setKey(int key) {
			this.key = key;
		}

		public Node getLeftNode() {
			return leftNode;
		}

		public void setLeftNode(Node leftNode) {
			this.leftNode = leftNode;
		}

		public Node getRightNode() {
			return rightNode;
		}

		public void setRightNode(Node rightNode) {
			this.rightNode = rightNode;
		}

	}

}