简单_基本二叉树(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 levelList<List<Node>> nodesList = new ArrayList<List<Node>>();// the positions in a displayable tree for each level's nodesList<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 nodeList<Integer> levelNodesPosList = new ArrayList<Integer>();levelNodesPosList.add(0); // root positionnextPosList.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 listnodesList.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) - 1int 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 displayfor (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) - 1int 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 treeSystem.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(",");elseSystem.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;elsenode = 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和valueK 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;}}}