java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了 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 学院整理),希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 PHPERZ 网站的支持!
来源: http://www.phperz.com/article/17/1225/357680.html