二叉树排序代码实现(重复数据无法插入)
public class MyTree {
Node root;//根节点 class Node{ Node left;//左儿子 Node right;//右儿子 Node parent;//父节点 Object data;//数据 public Node(Object data) { super(); this.data = data; } } /** * 打印整个二叉树 */ public void print(){ see(root); } /** * 从node节点开始察看二叉树 * @param node */ public void see(Node node){ if (node != null) { see(node.left); System.out.println(node.data); see(node.right); } } /** * 不可重复添加数据 * @param data */ public void add(Object data){ //判断data是否已经存在 Node node = findNode(data); if (node == null) { //数据不存在 //可以添加 //创建节点将数据放入节点中 node = new Node(data); if (root == null) { //二叉树为空 root = node; }else { //二叉树不为空 Node parent = findparent(data,root); //认爹 node.parent = parent; //爹认孩子 if (compare(parent.data, node.data) > 0) { //左儿子 parent.left = node; }else { //右儿子 parent.right = node; } } }else { //数据已经存在，不能再添加 return; } } /** * 删除数据 * @param data */ public void remove(Object data){ //判断数据是否在二叉树中 Node node = findNode(data); if (node == null) { //数据不在二叉树中 return; }else { //数据在二叉树中 delete(node); } } /** * 删除某个节点 * @param node */ private void delete(Node node) { if (root == node) { //1.删除根节点 if (node.left == null && node.right == null) { //1.1没有儿子 root = null; }else if (node.right == null) { //1.2只有左儿子 //左儿子继位 root = root.left; //断开左儿子的parent指针对node的引用 root.parent = null; }else if (node.left == null) { //1.3只有右儿子 //右儿子继位 root = root.right; //断开右儿子的parent指针对node的引用 root.parent = null; }else { //1.4有两个儿子 Node left = splite(node); //左儿子继位 root = left; //断开left的parent属性对node的引用 left.parent = null; } }else { //2.删除非根节点 if (node.left == null && node.right == null) { //2.1没有儿子 //判断node到底是左儿子还是右儿子 Node parent = node.parent; if (compare(parent.data, node.data) > 0) { //说明node是左儿子 parent.left = null; }else { //说明node是右儿子 parent.right = null; } }else if (node.right == null) { //2.2只有左儿子 //断开左儿子的parent指针对node的引用 node.left.parent = node.parent; //断开node的父节点的left/right指针对node的引用 //判断node是它的父节点的左儿子还是右儿子 Node parent = node.parent;//node的父节点 if (compare(parent.data, node.data) > 0) { //node是左儿子 parent.left = node.left; }else { //node是右儿子 parent.right = node.left; } }else if (node.left == null) { //2.3只有右儿子 //断开右儿子的parent指针对node的引用 node.right.parent = node.parent; //断开node 的父节点的left/right指针对node的引用 //判断node到底是左儿子还是右儿子 Node parent = node.parent; if (compare(parent.data, node.data) > 0) { //node是左儿子 parent.left = node.right; }else { //node是右儿子 parent.right = node.right; } }else { //2.4有两儿子 //分裂node的两个儿子，保留左儿子，将右儿子放到左儿子的最右边（断开node的右儿子的parent指针对node的引用） Node left = splite(node); //断开node的左儿子的parent指针对node的引用 left.parent = node.parent; //断开node的父节点的left/right指针对node的引用 //判断node到底是左儿子还是右儿子 Node parent = node.parent;//node的父节点 if (compare(node.parent.data, node.data) > 0) { //node是左儿子 parent.left = left; }else { //node是右儿子 parent.right = left; } } } } /** * 分裂两个儿子，保留左儿子，将右儿子放到左儿子的最右边 * @param node * @return */ private Node splite(Node node) { Node left = node.left; Node right = node.right; //开始给right找新爹 Node parent = findparent(right.data, left); //right认爹 right.parent = parent; //parent认儿子 parent.right = right; return left; } /** * 比较两个数据大小的方法 * @param data1 * @param data2 * @return */ @SuppressWarnings({ "rawtypes", "unchecked" }) public int compare(Object data1,Object data2){ Comparable c1 = null; Comparable c2 = null; if (data1 instanceof Comparable) { c1 = (Comparable) data1; c2 = (Comparable) data2; }else { c1 = data1.toString(); c2 = data2.toString(); } return c1.compareTo(c2); } /** * 从node节点开始遍历给data找父节点 * @param data * @return */ private Node findparent(Object data,Node node) { //从根节点开始遍历 //Node node = root; Node parent = null; while(node != null){ parent = node; //判断node.data与data的大小 if (compare(data, node.data) > 0) { //data大，往右找 node = node.right; }else { node = node.left; } } return parent; } /** * 找数据所在的节点 * @param data * @return */ private Node findNode(Object data) { //从根节点开始遍历 Node node = root; while(node != null){ if (node.data.equals(data) && node.data.hashCode() == data.hashCode()) { //找到了 break; }else { //如果没找到 //比较data与node.data的大小 if (compare(data, node.data) > 0) { //data大，往右找 node = node.right; }else { //往左找 node = node.left; } } } return node; }}
/测试案例/
public class Testtree {
public static void main(String[] args) { MyTree tree = new MyTree(); tree.add(38); tree.add(28); tree.add(48); tree.add(24); tree.add(32); tree.add(40); tree.add(55); tree.add(30); tree.add(20); tree.remove(32); tree.print(); }}
