Java数据结构与算法之树(动力节点java学院整理)

为什么使用树：

   树结合了两种数据结构的有点：一种是有序数组，树在查找数据项的速度和在有序数组中查找一样快；另一种是链表，树在插入数据和删除数据项的速度和链表一样。既然这样，就要好好去学了....
(最主要讨论的是二叉树中的二叉搜索树，即一个节点的左子节点关键值小于这个节点，右子节点的关键值大于这个节点)

设计前的思考：

树——>元素（节点）

class Node
{
 public int iData ;
 public float fData ;
 public Node left ;
 public Node right ;
 //方法
 public Node(int iData,float fData){}
 public void displayNode(){} 
}
class Tree
{
 Node root ;//树根
 //方法
 public void insert(){}
 public void displayTree(){}
 public void find(){}
 public void delete(){}
}

插入数据：

 //插入子节点
 public void insert(int iData ,float fData)
 {
 Node newNode = new Node(iData,fData) ;
 if(root == null)
 root = newNode ;
 else
 {
 Node current = root ;
 Node parent ;
 while(true)//寻找插入的位置 
 {
 parent = current ;
 if(iData<current.iData)
 {
 current = current.left ;
 if(current == null)
 {
 parent.left = newNode ;
 return ;
 }
 }
 else
 {
 current =current.right ;
 if(current == null)
 {
 parent.right = newNode ;
 return ;
 }
 }
 }
 }
 }

遍历树：

//中序遍历方法
 public void inOrder(Node localRoot)
 {
 if(localRoot != null)
 {
 inOrder(localRoot.left) ;//调用自身来遍历左子树
 localRoot.displayNode() ;//访问这个节点
 inOrder(localRoot.right) ;//调用自身来遍历右子树
 }
 }

查找某个节点：

//查找某个节点
 public Node find(int iData)
 {
 Node current = root ;
 while(current.iData != iData)
 {
 if(current.iData<iData)
 current = current.right ;
 else
 current = current.left ;
 if(current == null)
 return null ;
 }
 return current ;
 }

查找树中关键字的最大值和最小值：

最大值：不断地寻找右子节点

最小值：不断地寻找左子节点

//查找关键字最小的节点
 public Node findMinNode()
 {
 Node current , last ;
 last = null ;
 current = root ;
 if(current.left == null)
 return current ;
 else
 {
 while(current != null)
 {
 last = current ;
 current = current.left ;
 }
 return last ;
 }
 }

 删除某个节点：

 思考：

1).先找到要删除的节点：

public boolean delete(int key)
 {
 //先找到需要删除的节点
 Node current = root ;
 Node parent = root ;
 boolean isLeftChild = false ;
 while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
 {
 parent = current ;
 if(key < current.iData)
 {
 isLeftChild = true ;
 current = current.left ;
 }
 else
 {
 isLeftChild = false ;
 current = current.right ;
 }
 if(current == null)//找不到key时返回false
 return false ;
 }
 //continue ........
 }

2).再考虑要删除的节点是怎样的节点，经分析，有三种情况：叶节点、有一个节点的节点、有两个节点的节点

A).如果删除的是一个叶子节点，直接删除即可

//接上................
 //分情况考虑删除的节点
 //删除的节点为叶节点时
 if(current.left == null && current.right == null)
 {
 if(current == root)
 root = null ;
 else
 if(isLeftChild)
 parent.left = null ;
 else
 parent.right = null ;
 }
//continue...........

B).如果删除的节点有一个节点时：分两种情况，删除的节点只有一个左子节点，或者只有一个右子节点

//接上.......
//删除的节点有一个子节点
 else
 if(current.right == null)//删除的节点只有一个左子节点时
 {
 if(current == root)//要删除的节点为根节点
 root = current.left ;
 else
 if(isLeftChild)//要删除的节点是一个左子节点
 parent.left = current.left ;
 else
 parent.right = current.left ;//要删除的节点是一个右子节点
 }
 else
 if(current.left == null)//删除的节点只有一个右子节点时
 {
 if(current == root)//要删除的节点为根节点
 root = current.right ;
 else
 if(isLeftChild)//要删除的节点是一个左子节点
 parent.left = current.right ;
 else
 parent.right = current.right ;//要删除的节点是一个右子节点
 }
//continue.......

c).如果删除的节点有两个节点时：

这种情况就比较复杂，需要去寻找一个节点去替代要删除的节点。这个节点应该是什么节点呢？

据书本介绍，最合适的节点是后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。

说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。

以上面的为例，40的后继节点为74,10的后继节点是13,19的后继节点时26

以下是寻找后继节点的代码： 

 //返回后继节点
 private Node getSuccessor(Node delNode)
 {
 Node successorParent = delNode ;//后继节点的父节点
 Node successor = delNode ;//后继节点
 Node current = delNode.right ;//移动到位置节点位置
 while(current != null)
 {
 successorParent = successor ;
 successor = current ;
 current = current.left ;
 }
 if(successor != delNode.right)
 {
 successorParent.left = successor.right ;
 successor.right = delNode.right ;
 }
 return successor ;
 }

 找到了后继节点，接着就要讨论如何用后继节点替代药删除的节点

a)如果后继节点是刚好是要删除节点的右子节点（此时可以知道，这个右子节点没有左子点，如果有，就不该这个右子节点为后继节点）

//要删除的节点为左子节点时
parent.left = successor ;
successor.left = current.left ;
//要删除的节点是右子节点时
parent.right = successor ;
successor.left = current.left ;

b)如果后继节点为要删除节点的右子节点的左后代：

//假如要删除的节点为右子节点
successorParent.left = successor.right ;//第一步
successor.right = current.right ;//第二步
parent.right = successor ;
successor.left = current.left ;
//假设要删除的节点为左子节点
successorParent.left = successor.right ;
successor.right = current.right ;
parent.left = successor ;
successor.left = current.left ;

注意：第一步和第二步在getSuccessor()方法的最后的if语句中完成

以下是删除的节点有连个节点的代码：

//接上 
 //删除的节点有两个子节点
 else
 {
 Node successor = getSuccessor(current) ;//找到后继节点
 if(current == root)
 root = successor ;
 else
 if(isLeftChild)
 parent.left = successor ;
 else
 parent.right = successor ;
 successor.left = current.left ;
 }
 //continue....

综合上述，给出delete()方法的代码：

//删除某个节点
 public boolean delete(int key)
 {
 //先找到需要删除的节点
 Node current = root ;
 Node parent = root ;
 boolean isLeftChild = false ;
 while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
 {
 parent = current ;
 if(key < current.iData)
 {
 isLeftChild = true ;
 current = current.left ;
 }
 else
 {
 isLeftChild = false ;
 current = current.right ;
 }
 if(current == null)//找不到key时返回false
 return false ;
 }
 //分情况考虑删除的节点
 //删除的节点为叶节点时
 if(current.left == null && current.right == null)
 {
 if(current == root)
 root = null ;
 else
 if(isLeftChild)
 parent.left = null ;
 else
 parent.right = null ;
 }
 //删除的节点有一个子节点
 else
 if(current.right == null)//删除的节点只有一个左子节点时
 {
 if(current == root)//要删除的节点为根节点
 root = current.left ;
 else
 if(isLeftChild)//要删除的节点是一个左子节点
 parent.left = current.left ;
 else
 parent.right = current.left ;//要删除的节点是一个右子节点
 }
 else
 if(current.left == null)//删除的节点只有一个右子节点时
 {
 if(current == root)//要删除的节点为根节点
 root = current.right ;
 else
 if(isLeftChild)//要删除的节点是一个左子节点
 parent.left = current.right ;
 else
 parent.right = current.right ;//要删除的节点是一个右子节点
 }
 //删除的节点有两个子节点
 else
 {
 Node successor = getSuccessor(current) ;//找到后继节点
 if(current == root)
 root = successor ;
 else
 if(isLeftChild)
 parent.left = successor ;
 else
 parent.right = successor ;
 successor.left = current.left ;
 }
 return true ;
 }

进一步考虑：

删除那么复杂，那删除是必要的吗?我们可以给每个节点定义一个标志，该标志用于记录该节点是否已经删除了，显示树时，先判断该节点是否已经删除，如果没有，则显示。

这样的结果是，节点其实是没有删除的，这样显然逃避责任了。当树中没有那么多的删除操作时，这也不失为一种好方法，例如：

已经离职的员工的档案要永久地保存在员工的记录中。

以上所述是小编给大家介绍的Java数据结构与算法之树(动力节点java学院整理)，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！

# java  # 数据结构与算法  # java数据结构算法  # 树  # Java数据结构之链表、栈、队列、树的实现方法示例  # java数据结构之树基本概念解析及代码示例  # Java数据结构之红黑树的真正理解  # java数据结构排序算法之树形选择排序详解  # java 数据结构二叉树的实现代码  # Java中二叉树数据结构的实现示例  # Java数据结构学习之树  # 是一个  # 只有一个  # 遍历  # 子树  # 键值  # 的是  # 有一  # 有两个  # 找不到  # 两种  # 数据结构  # 最小值  # 要找  # 身来  # 第二步  # 小编  # 有一个  # 为左  # 链表  # 在此 

相关文章： 详解免费开源的.NET多类型文件解压缩组件SharpZipLib（.NET组件介绍之七）  网站图片在线制作软件,怎么在图片上做链接？  如何通过NAT技术实现内网高效建站？  如何在自有机房高效搭建专业网站？  微信网站制作公司有哪些,民生银行办理公司开户怎么在微信网页上查询进度？  制作旅游网站html,怎样注册旅游网站？  h5在线制作网站电脑版下载,h5网页制作软件？  c# 在ASP.NET Core中管理和取消后台任务  如何选择可靠的免备案建站服务器？  免费网站制作模板下载,除了易企秀之外还有什么H5平台可以制作H5长页面，最好是免费的？  如何快速搭建高效WAP手机网站吸引移动用户？  Python文件管理规范_工程实践说明【指导】  深圳网站制作平台,深圳市做网站好的公司有哪些？  单页制作网站有哪些,朋友给我发了一个单页网站，我应该怎么修改才能把他变成自己的呢，请求高手指点迷津？  宝塔新建站点为何无法访问？如何排查？  logo在线制作免费网站在线制作好吗,DW网页制作时，如何在网页标题前加上logo？  如何通过.red域名打造高辨识度品牌网站？  高性能网站服务器部署指南：稳定运行与安全配置优化方案  赚钱网站制作软件,建一个网站怎样才能赚钱?是如何盈利的？  湖北网站制作公司有哪些,湖北清能集团官网？  网站网页制作电话怎么打,怎样安装和使用钉钉软件免费打电话？  制作ppt免费网站有哪些,有哪些比较好的ppt模板下载网站？  如何基于云服务器快速搭建个人网站？  高防服务器如何保障网站安全无虞？  高防服务器租用首荐平台，企业级优惠套餐快速部署  如何用PHP工具快速搭建高效网站？  如何在云主机上快速搭建多站点网站？  网站设计制作公司地址,网站建设比较好的公司都有哪些？  C++如何编写函数模板？（泛型编程入门）  建站之星后台密码遗忘？如何快速找回？  建站168自助建站系统：快速模板定制与SEO优化指南  建站之星收费标准详解：套餐费用及年费价格表一览  网站制作价目表怎么做,珍爱网婚介费用多少？  如何用花生壳三步快速搭建专属网站？  建站之星如何配置系统实现高效建站？  Swift中switch语句区间和元组模式匹配  如何用免费手机建站系统零基础打造专业网站？  想学网站制作怎么学,建立一个网站要花费多少？  教学论文网站制作软件有哪些,写论文用什么软件 ？  建站之星客服服务时间及联系方式如何？  nginx修改上传文件大小限制的方法  较简单的网站制作软件有哪些,手机版网页制作用什么软件？  建站VPS选购需注意哪些关键参数？  ,制作一个手机app网站要多少钱？  建站主机解析：虚拟主机配置与服务器选择指南  建设网站制作价格,怎样建立自己的公司网站？  如何挑选高效建站主机与优质域名？  如何在香港免费服务器上快速搭建网站？  建站主机如何安装配置？新手必看操作指南  小说建站VPS选用指南：性能对比、配置优化与建站方案解析