您好,登录后才能下订单哦!
本篇文章为大家展示了利用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如何实现一个树算法,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。