Java数据结构与算法之树(动力节点java学院整理)
发布时间：2020-12-14 14:29:41 所属栏目：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学院整理)，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对编程小技巧网站的支持！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
