服务器之家

服务器之家 > 正文

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

时间:2020-09-09 13:30     来源/作者:动力节点

为什么使用树:

   树结合了两种数据结构的有点:一种是有序数组,树在查找数据项的速度和在有序数组中查找一样快;另一种是链表,树在插入数据和删除数据项的速度和链表一样。既然这样,就要好好去学了....
(最主要讨论的是二叉树中的二叉搜索树,即一个节点的左子节点关键值小于这个节点,右子节点的关键值大于这个节点)

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

设计前的思考:

树——>元素(节点)

?
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).如果删除的是一个叶子节点,直接删除即可

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

?
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).如果删除的节点有一个节点时:分两种情况,删除的节点只有一个左子节点,或者只有一个右子节点

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

?
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).如果删除的节点有两个节点时:

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

这种情况就比较复杂,需要去寻找一个节点去替代要删除的节点。这个节点应该是什么节点呢?

据书本介绍,最合适的节点是后继节点,即比要删除的节点的关键值次高的节点是它的后继节点。

说得简单一些,后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。

以上面的为例,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)如果后继节点是刚好是要删除节点的右子节点(此时可以知道,这个右子节点没有左子点,如果有,就不该这个右子节点为后继节点)

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

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

?
1
2
3
4
5
6
//要删除的节点为左子节点时
parent.left = successor ;
successor.left = current.left ;
//要删除的节点是右子节点时
parent.right = successor ;
successor.left = current.left ;

b)如果后继节点为要删除节点的右子节点的左后代:

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

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

?
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学院整理),希望对大家有所帮助

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
返回顶部