為什么使用樹：
樹結合了兩種數據結構的有點：一種是有序數組，樹在查找數據項的速度和在有序數組中查找一樣快；另一種是鏈表，樹在插入數據和刪除數據項的速度和鏈表一樣。既然這樣，就要好好去學了....
(最主要討論的是二叉樹中的二叉搜索樹，即一個節點的左子節點關鍵值小于這個節點，右子節點的關鍵值大于這個節點)
設計前的思考：
樹——>元素（節點）
|
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學院整理)，希望對大家有所幫助
