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(){}
}
插入数据：
1 //插入子节点
2 public void insert(int iData ,float fData)
3 {
4 Node newNode = new Node(iData,fData) ;
5
6 if(root == null)
7 root = newNode ;
8 else
9 {
10 Node current = root ;
11 Node parent ;
12 while(true)//寻找插入的位置
13 {
14 parent = current ;
15 if(iData<current.iData)
16 {
17 current = current.left ;
18 if(current == null)
19 {
20 parent.left = newNode ;
21 return ;
22 }
23 }
24 else
25 {
26 current =current.right ;
27 if(current == null)
28 {
29 parent.right = newNode ;
30 return ;
31 }
32 }
33 }
34 }
35 }
遍历树：
1 //中序遍历方法
2 public void inOrder(Node localRoot)
3 {
4 if(localRoot != null)
5 {
6 inOrder(localRoot.left) ;//调用自身来遍历左子树
7 localRoot.displayNode() ;//访问这个节点
8 inOrder(localRoot.right) ;//调用自身来遍历右子树
9 }
10 }
查找某个节点：
1 //查找某个节点
2 public Node find(int iData)
3 {
4 Node current = root ;
5 while(current.iData != iData)
6 {
7 if(current.iData<iData)
8 current = current.right ;
9 else
10 current = current.left ;
11 if(current == null)
12 return null ;
13 }
14 return current ;
15 }
查找树中关键字的最大值和最小值：
最大值：不断地寻找右子节点
最小值：不断地寻找左子节点
1 //查找关键字最小的节点
2 public Node findMinNode()
3 {
4 Node current , last ;
5 last = null ;
6 current = root ;
7 if(current.left == null)
8 return current ;
9 else
10 {
11 while(current != null)
12 {
13 last = current ;
14 current = current.left ;
15 }
16 return last ;
17 }
18 }
删除某个节点：
思考：
1).先找到要删除的节点：
1 public boolean delete(int key)
2 {
3 //先找到需要删除的节点
4 Node current = root ;
5 Node parent = root ;
6 boolean isLeftChild = false ;
7
8 while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
9 {
10 parent = current ;
11 if(key < current.iData)
12 {
13 isLeftChild = true ;
14 current = current.left ;
15 }
16 else
17 {
18 isLeftChild = false ;
19 current = current.right ;
20 }
21 if(current == null)//找不到key时返回false
22 return false ;
23 }
24 //continue ........
25 }
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
以下是寻找后继节点的代码：
1 //返回后继节点
2 private Node getSuccessor(Node delNode)
3 {
4 Node successorParent = delNode ;//后继节点的父节点
5 Node successor = delNode ;//后继节点
6 Node current = delNode.right ;//移动到位置节点位置
7 while(current != null)
8 {
9 successorParent = successor ;
10 successor = current ;
11 current = current.left ;
12 }
13 if(successor != delNode.right)
14 {
15 successorParent.left = successor.right ;
16 successor.right = delNode.right ;
17 }
18 return successor ;
19 }
找到了后继节点，接着就要讨论如何用后继节点替代药删除的节点
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语句中完成
以下是删除的节点有连个节点的代码：
1 //接上
2 //删除的节点有两个子节点
3 else
4 {
5 Node successor = getSuccessor(current) ;//找到后继节点
6 if(current == root)
7 root = successor ;
8 else
9 if(isLeftChild)
10 parent.left = successor ;
11 else
12 parent.right = successor ;
13 successor.left = current.left ;
14 }
15 //continue....
综合上述，给出delete()方法的代码：
1 //删除某个节点
2 public boolean delete(int key)
3 {
4 //先找到需要删除的节点
5 Node current = root ;
6 Node parent = root ;
7 boolean isLeftChild = false ;
8
9 while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
10 {
11 parent = current ;
12 if(key < current.iData)
13 {
14 isLeftChild = true ;
15 current = current.left ;
16 }
17 else
18 {
19 isLeftChild = false ;
20 current = current.right ;
21 }
22 if(current == null)//找不到key时返回false
23 return false ;
24 }
25
26 //分情况考虑删除的节点
27 //删除的节点为叶节点时
28 if(current.left == null && current.right == null)
29 {
30 if(current == root)
31 root = null ;
32 else
33 if(isLeftChild)
34 parent.left = null ;
35 else
36 parent.right = null ;
37 }
38 //删除的节点有一个子节点
39 else
40 if(current.right == null)//删除的节点只有一个左子节点时
41 {
42 if(current == root)//要删除的节点为根节点
43 root = current.left ;
44 else
45 if(isLeftChild)//要删除的节点是一个左子节点
46 parent.left = current.left ;
47 else
48 parent.right = current.left ;//要删除的节点是一个右子节点
49 }
50 else
51 if(current.left == null)//删除的节点只有一个右子节点时
52 {
53 if(current == root)//要删除的节点为根节点
54 root = current.right ;
55 else
56 if(isLeftChild)//要删除的节点是一个左子节点
57 parent.left = current.right ;
58 else
59 parent.right = current.right ;//要删除的节点是一个右子节点
60 }
61 //删除的节点有两个子节点
62 else
63 {
64 Node successor = getSuccessor(current) ;//找到后继节点
65 if(current == root)
66 root = successor ;
67 else
68 if(isLeftChild)
69 parent.left = successor ;
70 else
71 parent.right = successor ;
72 successor.left = current.left ;
73 }
74 return true ;
75 }
进一步考虑：
删除那么复杂，那删除是必要的吗?我们可以给每个节点定义一个标志，该标志用于记录该节点是否已经删除了，
显示树时，先判断该节点是否已经删除，如果没有，则显示。
这样的结果是，节点其实是没有删除的，这样显然逃避责任了。当树中没有那么多的删除操作时，这也不失为一种好方法，例如：
已经离职的员工的档案要永久地保存在员工的记录中。
本文转自互联网，由动力节点整理发布