JAVA实现平衡树

2019-11-06 07:14:08

字体：大中小

来源：转载

供稿：网友

复习，上代码

package tree;/** * Created by rightHead on 2017/3/4. */public abstract class BalanceTree<T> { PRivate final class Node { T data; int equals; int deep; Node left, right, dad; } private Node root; private final int BF = 2; public void insert(T data) { if (root == null) { root = newNode(data, null); } else { executeInsert(data, root); } } private int deep(Node node) { if (node != null) { return node.deep; }else{ return 0; } } private void adjustDeep(Node node, Node temp) { int leftHigh = deep(node.left); int rightHigh = deep(node.right); node.deep = leftHigh>rightHigh ? leftHigh+1 : rightHigh+1; leftHigh = deep(temp.left); rightHigh = node.deep; temp.deep = leftHigh>rightHigh ? leftHigh+1 : rightHigh+1; } private void adjustLeftLeft(Node node) { Node temp = node.left; node.left = temp.right; if (temp.right != null){ temp.right.dad = node; } if (node.dad != null){ if (node.dad.right == node){ node.dad.right = temp; }else{ node.dad.left = temp; } } temp.right = node; temp.dad = node.dad; node.dad = temp; if (node == root){ root = temp; } // 下面调整树的深度 adjustDeep(node, temp); } private void adjustRightRight(Node node) { Node temp = node.right; node.right = temp.left; if (temp.left != null){ temp.left.dad = node; } if (node.dad != null){ if (node.dad.right == node){ node.dad.right = temp; }else{ node.dad.left = temp; } } temp.left = node; temp.dad = node.dad; node.dad = temp; if (node == root){ root = temp; } adjustDeep(node, temp); } private void adjustLeftRight(Node node) { adjustRightRight(node.left); adjustLeftLeft(node); } private void adjustRightLeft(Node node) { adjustLeftLeft(node.right); adjustRightRight(node); } private void countDeep(Node node) { int leftDeep = deep(node.left); int rightDeep = deep(node.right); node.deep = leftDeep >= rightDeep ? leftDeep+1 : rightDeep+1; } private void executeInsert(T data, Node node) { if (compare(node.data, data) == 1){ // 要插入数据小于当前节点 if (node.left != null){ executeInsert(data, node.left); countDeep(node); if (deep(node.left) - deep(node.right) == BF){ // 深度到达2 开始旋转新节点插在当前节点的左子树，所以左子树一定比右子树大 if (compare(node.left.data, data) == 1){ adjustLeftLeft(node); }else{ adjustLeftRight(node); } } }else{ node.left = newNode(data, node); countDeep(node); } }else if (compare(node.data, data) == 2){ if (node.right != null){ executeInsert(data, node.right); countDeep(node); if (deep(node.right) - deep(node.left) == BF){ // 深度到达2 开始旋转新节点插在当前节点的右子树，所以右子树一定比左子树大 if (compare(node.right.data, data) == 2){ adjustRightRight(node); }else{ adjustRightLeft(node); } } }else{ node.right = newNode(data, node); countDeep(node); } }else { node.equals++; } } private Node newNode(T data, Node f) { Node node = new Node(); node.data = data; node.equals = 0; node.deep = 1; node.dad = f; node.right = node.left = null; return node; } abstract int compare(T arg1, T arg2); public void leftOrderPrintf() { leftPrintf(root); } private void leftPrintf(Node node) { if (node.left != null){ leftPrintf(node.left); } System.out.println(node.data); if (node.right != null){ leftPrintf(node.right); } } public void deleteAll() { root = null; // 直接抛弃整棵树，把头节点的强引用赋空 } public void delete(T data) { deleteNode(data, root); } private void deleteNode(T data, Node node) { Node temp1, temp2; if (node.data == data) { if (node.equals > 1){ node.equals--; }else if (node.right!=null && node.left!=null){ temp1 = node.right; while (temp1.left != null){ int leftHigh = deep(temp1.left)-1; int rightHigh = deep(temp1.right); temp1.deep = leftHigh>=rightHigh ? leftHigh : rightHigh; temp1 = temp1.left; } node.data = temp1.data; temp2 = temp1.dad; temp2.left = null; if (deep(node.left) - deep(node.right) == BF){ if (deep(node.left.left) > deep(node.left.right)){ adjustLeftLeft(node); }else{ adjustLeftRight(node); } } }else{ if (node.left != null){ temp1 = node.left; }else { temp1 = node.right; } if (temp1 != null){ node.data = temp1.data; node.deep--; node.left = node.right = null; temp1 = null; }else{ temp2 = node.dad; if (temp2.left == node){ temp2.left = null; }else{ temp2.right = null; } node = null; } } return; }else if (compare(node.data, data) == 1){ if (node.left != null){ deleteNode(data, node.left); }else{ System.out.println("无此点"); } }else if (compare(node.data, data) == 2){ if (node.right != null){ deleteNode(data, node.right); }else{ System.out.println("无此点"); } } int leftHigh = deep(node.left); int rightHigh = deep(node.right); node.deep = leftHigh>rightHigh ? leftHigh : rightHigh; }}

测试程序

package tree;/** * Created by rightHead on 2017/3/5. */public class Test { public static void main(String[] args) { BalanceTree<Integer> balanceTree = new BalanceTree<Integer>() { @Override public int compare(Integer arg1, Integer arg2) { if (arg1 > arg2){ return 1; }else if (arg1 < arg2){ return 2; }else { return 3; } } }; // 8 4 5 7 6 9 2 1 3 0 balanceTree.insert(8); balanceTree.insert(4); balanceTree.insert(5); balanceTree.insert(7); balanceTree.insert(6); balanceTree.insert(9); balanceTree.insert(2); balanceTree.insert(1); balanceTree.insert(3); balanceTree.insert(0); balanceTree.leftOrderPrintf(); balanceTree.delete(3); System.out.println("xoxxoxoxoxoxoxoxo"); balanceTree.leftOrderPrintf(); }}

上一篇：从零开始来看一下Java泛型的设计

下一篇：Java实现约瑟夫环问题