简单_基本二叉树(BST)

package sunfa.tree;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * 基本的BST(二叉树)
 * 
 * BST的遍历 :<br>
 * 1、利用二叉树本身特点进行递归遍历（属内部遍历） <br>
 * (1)前序遍历 　　访问根；按前序遍历左子树；按前序遍历右子树 　　 <br>
 * (2)中序遍历 按中序遍历左子树；访问根；按中序遍历右子树 　　<br>
 * (3)后序遍历 　　按后序遍历左子树；按后序遍历右子树；访问根 <br>
 * (4)按层次遍历<br>
 * 2、二叉树的非递归遍历（属外部遍历）<br>
 * 
 */
public class BTree<K, V> {
	public static void main(String[] args) {
		BTree<Integer, Integer> tree = new BTree<Integer, Integer>(null);
		Random ran = new Random();
		Integer[] arr = { 13, 84, 33, 24, 66, 51, 41, 94, 38, 11, 100 };
		for (int i = 0; i < arr.length; i++) {
			tree.put(arr[i], null);
		}
		System.out.println("树的高度:" + tree.h());
		System.out.println("按层次遍历树:");
		tree.printNodeByLevel();
		System.out.println();

		System.out.println("先序递归遍历：");
		tree.printTreePreOrder(tree.root);
		System.out.println();

		System.out.println("中序递归遍历：");
		tree.printTreeInOrder(tree.root);
		System.out.println();

		System.out.println("后序递归遍历：");
		tree.printTreePostOrder(tree.root);
		System.out.println();

		System.out.println("查找指定节点的高度:");
		System.out.println(tree.height(tree.getNode(Integer.valueOf(13))));
		System.out.println("判断树是否是AVL树："
				+ tree.checkAVL(tree.getNode(Integer.valueOf(51))));
		
		int aa = 100;
		Node<Integer, Integer> successorNode = tree.getSuccessor(tree.getNode(aa));
		Node<Integer, Integer> predecessorNode = tree.getPredecessor(tree.getNode(aa));
		System.out.println("后驱测试:"+(successorNode==null?"null":successorNode.key));
		System.out.println("前驱测试:"+(predecessorNode==null?"null":predecessorNode.key));
	}

	private Node<K, V> root = null;
	private Comparator<K> comp;

	public BTree(Comparator<K> c) {
		this.comp = c;
	}

	public static void displayBinaryTree(Node root, int n) {
		if (root == null)
			return;

		LinkedList<Node> queue = new LinkedList<Node>();

		// all nodes in each level
		List<List<Node>> nodesList = new ArrayList<List<Node>>();

		// the positions in a displayable tree for each level's nodes
		List<List<Integer>> nextPosList = new ArrayList<List<Integer>>();

		queue.add(root);
		// int level=0;
		int levelNodes = 1;

		int nextLevelNodes = 0;
		List<Node> levelNodesList = new ArrayList<Node>();
		List<Integer> nextLevelNodesPosList = new ArrayList<Integer>();

		int pos = 0; // the position of the current node
		List<Integer> levelNodesPosList = new ArrayList<Integer>();
		levelNodesPosList.add(0); // root position
		nextPosList.add(levelNodesPosList);
		int levelNodesTotal = 1;
		while (!queue.isEmpty()) {
			Node node = queue.remove();

			if (levelNodes == 0) {
				nodesList.add(levelNodesList);
				nextPosList.add(nextLevelNodesPosList);
				levelNodesPosList = nextLevelNodesPosList;

				levelNodesList = new ArrayList<Node>();
				nextLevelNodesPosList = new ArrayList<Integer>();

				// level++;
				levelNodes = nextLevelNodes;
				levelNodesTotal = nextLevelNodes;

				nextLevelNodes = 0;
			}
			levelNodesList.add(node);

			pos = levelNodesPosList.get(levelNodesTotal - levelNodes);
			if (node.left != null) {
				queue.add(node.left);
				nextLevelNodes++;
				nextLevelNodesPosList.add(2 * pos);
			}

			if (node.right != null) {
				queue.add(node.right);
				nextLevelNodes++;

				nextLevelNodesPosList.add(2 * pos + 1);
			}

			levelNodes--;
		}
		// save the last level's nodes list
		nodesList.add(levelNodesList);

		int maxLevel = nodesList.size() - 1; // ==level

		// use both nodesList and nextPosList to set the positions for each node

		// Note: expected max columns: 2^(level+1) - 1
		int cols = 1;
		for (int i = 0; i <= maxLevel; i++) {
			cols <<= 1;
		}
		cols--;
		Node[][] tree = new Node[maxLevel + 1][cols];

		// load the tree into an array for later display
		for (int currLevel = 0; currLevel <= maxLevel; currLevel++) {
			levelNodesList = nodesList.get(currLevel);
			levelNodesPosList = nextPosList.get(currLevel);
			// Note: the column for this level's j-th element:
			// 2^(maxLevel-level)*(2*j+1) - 1
			int tmp = maxLevel - currLevel;
			int coeff = 1;
			for (int i = 0; i < tmp; i++) {
				coeff <<= 1;
			}
			for (int k = 0; k < levelNodesList.size(); k++) {
				int j = levelNodesPosList.get(k);
				int col = coeff * (2 * j + 1) - 1;
				tree[currLevel][col] = levelNodesList.get(k);
			}
		}

		// display the binary search tree
		System.out.format("%n");
		for (int i = 0; i <= maxLevel; i++) {
			for (int j = 0; j < cols; j++) {
				Node node = tree[i][j];
				if (node == null)
					System.out.format(",");
				else
					System.out.format("%2d", node.key);
			}
			System.out.format("%n");
		}
	}

	/**
	 * 从树根节点起往树添加节点，但每个节点下只能有2个子节点。 将指定值与此映射中的指定键进行关联。如果该映射以前包含此键的映射关系，那么将替换旧值。
	 * 与 key 关联的先前值；如果没有针对 key 的映射关系，则返回 null。（返回 null 还可能表示该映射以前将 null 与 key
	 * 关联。）
	 * 
	 * @param key
	 * @param value
	 * @return
	 */
	public V put(K key, V value) {
		if (root == null) {
			root = new Node<K, V>(key, value, null);
			return value;
		}
		Node<K, V> t = root;
		while (true) {
			int cmp = compare(key, t.key);
			if (cmp == 0) {
				return t.setValue(value);
			} else if (cmp < 0) {
				if (t.left != null)
					t = t.left;
				else {
					t.left = new Node<K, V>(key, value, t);
					return null;
				}
			} else {
				if (t.right != null)
					t = t.right;
				else {
					t.right = new Node<K, V>(key, value, t);
					return null;
				}
			}
		}
	}

	/**
	 * 树的遍历 :<br>
	 * 1、利用二叉树本身特点进行递归遍历（属内部遍历） <br>
	 * (1)前序遍历 　　访问根；按前序遍历左子树；按前序遍历右子树 　　 <br>
	 * (2)中序遍历 按中序遍历左子树；访问根；按中序遍历右子树 　　<br>
	 * (3)后序遍历 　　按后序遍历左子树；按后序遍历右子树；访问根 <br>
	 * (4)按层次遍历<br>
	 * 2、二叉树的非递归遍历（属外部遍历）<br>
	 */
	public void printNodeByLevel() {
		if (root != null) {
			list.clear();
			list.add(root);
			printNodeByLevel0(list);
		} else {
			System.out.println("root is null");
		}
	}

	/**
	 * 先序递归遍历<br>
	 * 先序、中序、后序，这里的先 中 后到底是对谁而言的？是相对于你当前的节点而言的。<br>
	 * 先的意思是：你当前的节点先被遍历(先打印值)，然后遍历你当前节点的左节点，然后是右节点。<br>
	 * 
	 * 所以中序遍历的结果是把树的元素按造从小到大的顺序打印出来了，这个比较常用。
	 * 
	 * @param node
	 */
	public void printTreePreOrder(Node<K, V> node) {
		if (node == null)
			return;
		System.out.print(node.key + ",");
		printTreePreOrder(node.left);
		printTreePreOrder(node.right);
	}

	/**
	 * 中序递归遍历
	 * 
	 * @param node
	 */
	public void printTreeInOrder(Node<K, V> node) {
		if (node == null)
			return;
		printTreeInOrder(node.left);
		System.out.print(node.key + ",");
		printTreeInOrder(node.right);
	}

	/**
	 * 后续递归遍历
	 * 
	 * @param node
	 */
	public void printTreePostOrder(Node<K, V> node) {
		if (node == null)
			return;
		printTreeInOrder(node.left);
		printTreeInOrder(node.right);
		System.out.print(node.key + ",");
	}

	List<Node<K, V>> list = new ArrayList<Node<K, V>>();

	private void printNodeByLevel0(List<Node<K, V>> list) {
		if (list == null || list.size() == 0) {
			return;
		}
		List<Node<K, V>> list2 = new ArrayList<Node<K, V>>();
		for (int i = 0; i < list.size(); i++) {
			Node<K, V> node = list.get(i);
			if (node != null) {
				System.out.print(node.key + ",");
				if (node.left != null) {
					list2.add(node.left);
				}
				if (node.right != null) {
					list2.add(node.right);
				}
			}
		}
		System.out.println();
		if (list2.size() > 0) {
			// System.out.print("debug:");
			// for (int i = 0; i < list.size(); i++) {
			// System.out.print(((Node)list.get(i)).key+"_");
			// }
			// System.out.println();
			list.clear();
			list.addAll(list2);
			printNodeByLevel0(list);
		}
	}

	/**
	 * 根据key获取节点的value,查找失败返回NULL
	 * 
	 * @param key
	 * @return
	 */
	public Object get(K key) {
		Node<K, V> node = getNode(key);
		return node == null ? null : node.value;
	}

	/**
	 * 查找指定的key对应的节点，没有找到返回NULL
	 * 
	 * @param key
	 * @return
	 */
	public Node<K, V> getNode(K key) {
		Node<K, V> node = root;
		while (node != null) {
			int cmp = compare((K) key, node.key);
			if (cmp == 0)
				return node;
			else if (cmp < 0)
				node = node.left;
			else
				node = node.right;
		}
		return null;
	}

	/**
	 * 非递归删除节点 <br>
	 * 1、删除的是叶子节点，则将其父节点对它的引用置NULL<br>
	 * 2、删除的节点只含有一个节点 <br>
	 * 3、删除的节点有2个子节点,这情况3转换成情况1或2的方式来简化问题。<br>
	 * 获取被删除节点的前驱或后驱替换被删除节点，此时前驱或后驱节点必然是没有右孩子或没有左孩子的节点，其删除操作使用前面的方法完成即可。<br>
	 * 把被删除节点的右子节点下最大的节点提升到被删除节点的位置<br>
	 * 
	 * @param key
	 * @return
	 */
	public Object remove(K key) {
		Node<K, V> node = getNode(key);
		if (node == null) {
			return null;
		}
		Node<K, V> delNode = node;// 默认待删除节点是找到的节点
		V val = node.value;
		/*
		 * 待删除的节点即有左子树又有右子树，那么就先找到它的前驱或后驱，因为它的前驱或后驱必然是没有左子树或没有右子树的节点，这个很关键。问题在这里被简化了。
		 */
		if (delNode.left != null && delNode.right != null) { // 复杂情况3被转化成了情况1和2
			//获取待删除节点的后驱节点,如果一个节点有左右子树，那么它肯定有前驱或后驱
			Node<K, V> nextNode = getSuccessor(delNode);
			//交换待删除节点和它的后驱节点的key和value
			K tempK = node.key;
			V tempV = node.value;
			node.key = nextNode.key;
			node.value = nextNode.value;
			nextNode.key = tempK;
			nextNode.value = tempV;
			
			//经过上面步骤后待删除节点变成了它的后驱节点了
			delNode = nextNode;
		}

		if (delNode.left == null && delNode.right == null) {
			/**
			 * 判断待删除的节点是其父节点的左子节点还是右子节点,可以通过引用来判断或通过比较大小来判断。比如下面注释部分的代码：<br>
			 * K k1 = delNode.parent.key;
			 * if(((Comparable<K>)k1).compareTo(delNode.key)>0){
			 * delNode.parent.left = null; }else{ delNode.parent.right = null; }
			 */
			if (delNode.parent.left == delNode) {
				delNode.parent.left = null;
			} else {
				delNode.parent.right = null;
			}
		} else if (delNode.left != null && delNode.right == null) {
			delLOrR(delNode, true);
		} else if (delNode.right != null && delNode.left == null) {
			delLOrR(delNode, false);
		}
		delNode = null;
		return val;
	}

	/**
	 * 删除指定的节点
	 * 
	 * @param delNode
	 *            待删除的节点
	 * @param lr
	 *            true待删除的节点是其父节点的左子节点，false是其父节点的右子节点
	 */
	private void delLOrR(Node<K, V> delNode, boolean lr) {
		if (delNode.parent.left == delNode) {
			if (lr) {
				delNode.parent.left = delNode.left;
			} else {
				delNode.parent.left = delNode.right;
			}
		} else {
			if (lr) {
				delNode.parent.right = delNode.left;
			} else {
				delNode.parent.right = delNode.right;
			}
		}
	}

	/**
	 * 获取指定节点的后驱节点,所谓后驱节点是比该节点大的所有节点中最小的节点。 <br>
	 * 1、节点的右子节点不为NULL，右边最小节点即为后驱节点。<br>
	 * 2、节点的右子节点为NULL，沿着节点走直到根的父节点即为后驱节点。<br>
	 * 
	 * 前驱与后驱正好相反
	 * 
	 * @param node
	 * @return
	 */
	private Node<K, V> getSuccessor(Node<K, V> node) {
		if (node == null)
			return null;
		// 如果节点的右子树存在，那么该节点的后驱就是以该节点为二叉树的最小子节点
		if (node.right != null) {
			return min(node.right);
		}  
		/*                                  7
		 *                                 /
		 *      10                        4
		 *      /                          \
		 *      5                           5
		 *       \                           \
		 *        6                           6
		 *        很明显节点6的后续是10                             很明显节点6的后续是7
		 */
		while (node.parent != null && node.parent.right == node)//如果当前节点存在右节点则一直往上搜索
			node = node.parent;
		return node.parent;//搜索完毕后它的父节点就是该节点的后驱节点
	}

	/**
	 * 获取指定节点的之前前驱节点
	 * @param node
	 * @return
	 */
	private Node<K, V> getPredecessor(Node<K, V> node) {
		//根节点或空节点是没有前驱的
		if (node == null)
			return null;
		if (node.left != null)
			return max(node.left);
		while (node.parent!=null && node.parent.left == node)
			node = node.parent;
		return node.parent;
	}
	/**
	 * 以指定节点为根的二叉查找树中最小元素节点
	 * 
	 * @param node
	 * @return
	 */
	private Node<K, V> min(Node<K, V> node) {
		if (node != null) {
			while (node.left != null)
				node = node.left;
		}
		return node;
	}

	/**
	 * 返回以指定节点为跟的二叉查找树中最大元素的节点
	 * 
	 * @param node
	 * @return
	 */
	private Node<K, V> max(Node<K, V> node) {
		if (node != null) {
			while (node.right != null)
				node = node.right;
		}
		return node;
	}

	/**
	 * 返回二叉树的高度
	 * 
	 * @return
	 */
	public int h() {
		return height(this.root);
	}

	/**
	 * 获取树节点的高度<br>
	 * 根节点的高度为-1
	 */
	public int height(Node<K, V> node) {
		if (node == null)
			return -1;
		return 1 + Math.max(height(node.left), height(node.right));
	}

	/**
	 * 判断树是否是AVL树<br>
	 * 1、左右子树的高度差绝对值小于1. 2、左右子树也都是AVL树
	 * 
	 * @param node
	 * @return
	 */
	public boolean checkAVL(Node<K, V> node) {
		if (node == null)
			return true;
		return Math.abs(height(node.left) - height(node.right)) <= 1
				&& checkAVL(node.left) && checkAVL(node.right);
	}

	public int compare(K k1, K k2) {
		return this.comp != null ? ((comp.compare(k1, k2)))
				: ((Comparable<K>) k1).compareTo(k2);
	}

	static class Node<K, V> {
		K key;
		V value;
		Node<K, V> parent, left, right;

		public Node(K key, V value, Node<K, V> parent) {
			super();
			this.key = key;
			this.value = value;
			this.parent = parent;
		}

		/**
		 * 插入新值，返回旧值
		 * 
		 * @param value
		 * @return
		 */
		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}
	}
}