为什么使用树：
树结合了两种数据结构的有点：一种是有序数组，树在查找数据项的速度和在有序数组中查找一样快；另一种是链表，树在插入数据和删除数据项的速度和链表一样。既然这样，就要好好去学了....
(最主要讨论的是二叉树中的二叉搜索树，即一个节点的左子节点关键值小于这个节点，右子节点的关键值大于这个节点)
设计前的思考：
树——>元素（节点）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
//插入子节点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 ;}}}}} |
遍历树：
|
1
2
3
4
5
6
7
8
9
10
|
//中序遍历方法 public void inorder(node localroot) { if(localroot != null) { inorder(localroot.left) ;//调用自身来遍历左子树 localroot.displaynode() ;//访问这个节点 inorder(localroot.right) ;//调用自身来遍历右子树 } } |
查找某个节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//查找某个节点 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 ; } |
查找树中关键字的最大值和最小值：
最大值：不断地寻找右子节点
最小值：不断地寻找左子节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//查找关键字最小的节点 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).先找到要删除的节点：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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).如果删除的是一个叶子节点，直接删除即可
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
//接上................ //分情况考虑删除的节点 //删除的节点为叶节点时 if(current.left == null && current.right == null) { if(current == root) root = null ; else if(isleftchild) parent.left = null ; else parent.right = null ; }//continue........... |
b).如果删除的节点有一个节点时：分两种情况，删除的节点只有一个左子节点，或者只有一个右子节点
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
//接上.......//删除的节点有一个子节点 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//返回后继节点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)如果后继节点是刚好是要删除节点的右子节点（此时可以知道，这个右子节点没有左子点，如果有，就不该这个右子节点为后继节点）
|
1
2
3
4
5
6
|
//要删除的节点为左子节点时parent.left = successor ;successor.left = current.left ;//要删除的节点是右子节点时parent.right = successor ;successor.left = current.left ; |
b)如果后继节点为要删除节点的右子节点的左后代：
|
1
2
3
4
5
6
7
8
9
10
|
//假如要删除的节点为右子节点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
4
5
6
7
8
9
10
11
12
13
14
15
|
//接上 //删除的节点有两个子节点 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()方法的代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
//删除某个节点 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学院整理)，希望对大家有所帮助
