/** * user:ypc; * date:2021-05-18; * time: 15:09; */ class Node { int val; Node left; Node right; Node(int val) { this.val = val; } } public void insert(int key) { Node node = new Node(key); if (this.root == null) { root = node; } Node cur = root; Node parent = null; while (cur != null) { if (cur.val == key) { //System.out.println("元素已经存在"); return; } else if (cur.val > key) { parent = cur; cur = cur.left; } else { parent = cur; cur = cur.right; } } if (key > parent.val) { parent.right = node; } else { parent.left = node; } }
public boolean search(int key) { Node cur = root; while (cur != null) { if (cur.val == key) { return true; } else if (cur.val > key) { cur = cur.left; } else { cur = cur.right; } } return false; }
public void removenode1(Node parent, Node cur) { if (cur.left == null) { if (cur == root) { root = cur.right; } else if (cur == parent.right) { parent.left = cur.right; } else { parent.right = cur.right; } } else if (cur.right == null) { if (cur == root) { root.left = cur; } else if (cur == parent.right) { parent.right = cur.left; } else { parent.left = cur.left; } } else { Node tp = cur; Node t = cur.right; while (t.left != null) { tp = t; t = t.left; } if (tp.left == t) { cur.val = t.val; tp.left = t.right; } if (tp.right == t) { cur.val = t.val; tp.right = t.right; } } } public void remove(int key) { Node cur = root; Node parent = null; while (cur != null) { if (cur.val == key) { removenode1(parent, cur); //removenode2(parent, cur); return; } else if (key > cur.val) { parent = cur; cur = cur.right; } else { parent = cur; cur = cur.left; } } }
public void removenode2(Node parent, Node cur) { if (cur.left == null) { if (cur == root) { root = cur.right; } else if (cur == parent.right) { parent.left = cur.right; } else { parent.right = cur.right; } } else if (cur.right == null) { if (cur == root) { root.left = cur; } else if (cur == parent.right) { parent.right = cur.left; } else { parent.left = cur.left; } } else { Node tp = cur; Node t = cur.left; while (t.right != null) { tp = t; t = t.right; } if (tp.right == t) { cur.val = t.val; tp.right = t.left; } if (tp.left == t) { cur.val = t.val; tp.left = t.left; } } }
/** * user:ypc; * date:2021-05-18; * time: 15:09; */ class TestBinarySearchTree { public static void main(String[] args) { int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9}; BinarySearchTree binarySearchTree = new BinarySearchTree(); for (int i = 0; i < a.length; i++) { binarySearchTree.insert(a[i]); } binarySearchTree.inOrderTree(binarySearchTree.root); System.out.println(); binarySearchTree.preOrderTree(binarySearchTree.root); binarySearchTree.remove(7); System.out.println(); System.out.println("方法一删除后"); binarySearchTree.inOrderTree(binarySearchTree.root); System.out.println(); binarySearchTree.preOrderTree(binarySearchTree.root); } }
到此这篇关于Java基础之二叉搜索树的基本操作的文章就介绍到这了,更多相关二叉搜索树的基本操作内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
免责声明:本站发布的内容(图片、视频和文字)以原创、来自互联网转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:ts@56dr.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。
Copyright © 2009-2021 56dr.com. All Rights Reserved. 特网科技 版权所有 珠海市特网科技有限公司 粤ICP备16109289号
域名注册服务机构:阿里云计算有限公司(万网) 域名服务机构:烟台帝思普网络科技有限公司(DNSPod) CDN服务:阿里云计算有限公司 中国互联网举报中心 增值电信业务经营许可证B2