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

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 = 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

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)/http:///删除的节点只有一个右子节点时

{

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()方法的代码：

/VyUcWXfwY/删除某个节点

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 successoVyUcWXfwYr = getSuccessor(current) ;//找到后继节点

if(curreVyUcWXfwYnt == root)

root = successor ;

else

if(isLeftChild)

parent.left = successor ;

else

parent.right = successor ;

successor.left = current.left ;

}

return true ;

}

进一步考虑：

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

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

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

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

{

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

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)/http:///删除的节点只有一个右子节点时

{

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()方法的代码：

/VyUcWXfwY/删除某个节点

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 successoVyUcWXfwYr = getSuccessor(current) ;//找到后继节点

if(curreVyUcWXfwYnt == root)

root = successor ;

else

if(isLeftChild)

parent.left = successor ;

else

parent.right = successor ;

successor.left = current.left ;

}

return true ;

}

进一步考虑：

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

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

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

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

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)/http:///删除的节点只有一个右子节点时

{

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()方法的代码：

/VyUcWXfwY/删除某个节点

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 successoVyUcWXfwYr = getSuccessor(current) ;//找到后继节点

if(curreVyUcWXfwYnt == root)

root = successor ;

else

if(isLeftChild)

parent.left = successor ;

else

parent.right = successor ;

successor.left = current.left ;

}

return true ;

}

进一步考虑：

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

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

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。