江苏龙网

  1. 主页 > 生活百科 > >

二叉树的java实现，超级简单讲解版( 二 )

二叉树


上面我们已经实现了二叉树中的put方法 ， 按照我的习惯的话呢接下来我们还是先讲思想 ， 讲get方法和delete方法：
查询方法get实现思想：
从根结点开始：

  1. 如果要查询的key小于当前结点的key ， 则继续查找当前结点的左子结点
  2. 如果要查询的key大于当前结点的key ， 则继续找当前结点的右子结点
  3. 如果要查询的key等于当前结点的key ， 则树中返回当前结点的value
删除方法delete实现思想：
  1. 找到被删除结点
  2. 找到被删除结点右子树的最小结点
  3. 删除右子树中的最小结点
  4. 让被删除结点的左子树称为最小结点的左子树 ， 让被删除结点的右子树称为最小结点的子树
  5. 让被删除节点的父结点指向最小结点
按照从简单到困难的准则 ， 我们先从简单的开始 ， get方法相对于delete而言要简单一点 ， 所以我们先实现get方法
//从树中找到对应的值public String get(Integer key){return get(root,key);}private String get(Node tree,Integer key){if(root==null){return null;}//比较key,如果新结点大于当前结点的key ， 继续寻找当前结点的右子结点if(key > tree.key){return get(tree.right,key);}else if(key<tree.key){//比较key,如果新结点大于当前结点的key ， 继续寻找当前结点的左子结点return get(tree.left,key);}else{//要查找的key和当前结点的key相等 ， 返回valuereturn tree.value;}}通过不停的递归调用get方法 ， 我们就可以不断的查找树的左右结点 ， 从而最终返回get到的结果值 ， 这个非常简单 ， 没什么好说的 。
接下来比较重要的是delete方法：
//从指定的树中 ， 根据key删除键中的键值对public void delete(Integer key){root=delete(root,key);}private Node delete(Node tree,Integer key){if(tree==null){return null;}if(key > tree.key){tree.right=delete(tree.right,key);}else if(key<tree.key){tree.left=delete(tree.left,key);}else{//待删除的key等于当前结点的key ， 说明当前结点就是要删除的结点//1、如果当前结点的右子树不存在 ， 则直接返回当前结点的左子结点if(tree.right==null){n--;return tree.left;}//2、如果当前结点的左子树不存在 ， 则直接返回当前结点的右子结点if(tree.left==null){n--;returntree.right;}//当前结点的左右子树都存在//找到右子树中的最小结点Node minNode=tree.right;//二叉查找树的左结点一定比右结点小if(minNode.left!=null){minNode=minNode.left;}//到这里就找到了当前结点右子树中最小的结点minNode//删除右子树中最小的结点Node node=tree.right;while (node.left!=null){if(node.left.left==null){//说明N的左结点就是我们要找的最小结点node.left=null;}else{node=node.left;}}//到这里 ， 最小结点已经被删除了//让被删除结点的左子树成为最小结点的左子树 ， 让被删除结点的右子树 ， 成为最小结点的右子树minNode.left=tree.left;minNode.right=tree.right;//让被删除结点的父结点指向最小结点tree=minNode;//个数减1n--;}return tree;}上面的这段代码看着很长 ， 且听我与你一一分解
首先我们通过public方法方便别的类调用 ， 用户只需要传递key值进入我们的后台 ， 我们就可以通过后台的查找方法来查找二叉树中的元素 ， 然后对其进行删除 。
这同样使用了递归的思想 。通过不断的查找二叉树中的元素 ， 找到要删除的那个数据 。
if(key > tree.key){tree.right=delete(tree.right,key);}else if(key<tree.key){tree.left=delete(tree.left,key);}else{//待删除的key等于当前结点的key ， 说明当前结点就是要删除的结点//1、如果当前结点的右子树不存在 ， 则直接返回当前结点的左子结点if(tree.right==null){n--;return tree.left;}//2、如果当前结点的左子树不存在 ， 则直接返回当前结点的右子结点if(tree.left==null){n--;returntree.right;}//当前结点的左右子树都存在//找到右子树中的最小结点Node minNode=tree.right;//二叉查找树的左结点一定比右结点小if(minNode.left!=null){minNode=minNode.left;}//到这里就找到了当前结点右子树中最小的结点minNode//删除右子树中最小的结点Node node=tree.right;while (node.left!=null){if(node.left.left==null){//说明N的左结点就是我们要找的最小结点node.left=null;}else{node=node.left;}}//到这里 ， 最小结点已经被删除了//让被删除结点的左子树成为最小结点的左子树 ， 让被删除结点的右子树 ， 成为最小结点的右子树minNode.left=tree.left;minNode.right=tree.right;//让被删除结点的父结点指向最小结点tree=minNode;//个数减1n--;}


推荐阅读


上一篇：为什么大多数IP地址通常以192.168开头？

下一篇：想验证安装的操作系统是否正版，可以这样找到Win10产品密钥