前言
本章，我們主要需要了解以下內容
- 什么是線索二叉樹
- 怎么去把二叉樹線索化
- 怎么通過線索二叉樹查找某個數的后繼結點
- 二叉樹的查看——二叉樹怎們遍歷
什么是線索二叉樹
首先我們來了解一下什么是線索二叉樹？
定義：一個二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指針改為指向該節點在中序序列中的后繼，所有原本為空的左(孩子)指針改為指向該節點的中序序列的前驅。
再看一下為什么要有線索二叉樹？
顧名思義，線索二叉樹，肯定是根據線索查找，查找速度肯定更快。
- 線索二叉樹能線性地遍歷二叉樹，從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個節點的父節點，這比顯式地使用父親節點指針或者棧效率更高。這在?？臻g有限，或者無法使用存儲父節點的棧時很有作用（對于通過深度優先搜索來查找父節點而言)。
那線索僅僅是這樣嗎？當然不，我們都是懶的，能等待解決的問題，為什么會去想新的辦法。我們要解決的是:
- 為了解決無法直接找到該結點在某種遍歷序列中的前驅和后繼結點的問題
- 但是同時出現了二叉鏈表找左、右孩子困難的問題，即在構建線索二叉樹之后，鏈表的原來遍歷方式會出問題。
最后看一下什么線索二叉樹的圖解
在我們的線索二叉樹的書上，基本上都有以下這張圖：
大家看到上面這張圖還是有點懵的叭，我們一起看一下我下面手畫的圖
怎么去把二叉樹線索化
哦！在著之前獻給大家提一下，二叉樹的遍歷方式，有這樣的幾種
- 前序遍歷二叉樹的遞歸定義(根左右)
- 中序遍歷二叉樹的遞歸定義(左根右)
- 后續遍歷二叉樹的遞歸意義(左右根)
本博文主要討論的是中序遍歷
它的中序遍歷結果就是abcde f ghi
它的中序線索二叉樹遍歷如下
先畫線索二叉樹
虛線箭頭為線索指針，對于所有左指針指向空的節點：將該節點的左指針指向該節點在中序遍歷中的上一節點；對于所有右指針指向空的節點，將該節點的右指針指向該節點在中序遍歷中的下一結點。最后一個末尾結點除外。
中序圖解線索二叉樹
怎么通過線索二叉樹查找某個數的后繼結點
即形成了一個特殊的雙向鏈表，之所以特殊，以f–>e為例，f–>e并不是直接到達，而是通過f–>b–>d–>e間接到達。
我們嘗試用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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
package com.testtree;/** * @author pier */public class treenode { /**數據域**/ private int data; /**左指針**/ private treenode left; /** 左孩子是否為線索，采用布爾類型主要是判斷是否未null足以**/ private boolean leftisthread; /**右指針**/ private treenode right; /** 右孩子是否為線索**/ private boolean rightisthread; /**根據數據域來確定所在的指針對應位置**/ public treenode(int data) { this.data = data; this.left = null; this.leftisthread = false; this.right = null; this.rightisthread = false; } public int getdata() { return data; } public void setdata(int data) { this.data = data; } public treenode getleft() { return left; } public void setleft(treenode left) { this.left = left; } public boolean isleftisthread() { return leftisthread; } public void setleftisthread(boolean leftisthread) { this.leftisthread = leftisthread; } public treenode getright() { return right; } public void setright(treenode right) { this.right = right; } public boolean isrightisthread() { return rightisthread; } public void setrightisthread(boolean rightisthread) { this.rightisthread = rightisthread; } @override public boolean equals(object obj) { if (obj instanceof treenode ) { treenode temp = (treenode) obj; if (temp.getdata() == this.data) { return true; } } return false; } @override public int hashcode() { return super.hashcode() + this.data; }} |
二叉樹類
|
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
package com.testtree;/*author:pier2021/10/12*/public class bitree { /** 根節點 **/ private treenode root; /** 大小 **/ private int size; /** 線索化的時候保存前驅 **/ private treenode pre = null; public bitree() { this.root = null; this.size = 0; this.pre = null; } public bitree(int[] data) { this.pre = null; this.size = data.length; // 創建二叉樹 this.root = createtree(data, 1); } /** * 創建二叉樹 * */ public treenode createtree(int[] data, int index) { if (index > data.length) { return null; } treenode node = new treenode(data[index - 1]); treenode left = createtree(data, 2 * index); treenode right = createtree(data, 2 * index + 1); node.setleft(left); node.setright(right); return node; } /**中序遍歷**/ public void inlist(treenode root) { if (root != null) { inlist(root.getleft()); system.out.print(root.getdata() + ","); inlist(root.getright()); } } public treenode getroot() { return root; } public void setroot(treenode root) { this.root = root; } public int getsize() { return size; } public void setsize(int size) { this.size = size; } /**線索化二叉樹**/ public void inthread(treenode root) { if ( root != null ) { // 線索化左孩子 inthread(root.getleft()); // 左孩子為空 if ( null == root.getleft() ) { // 將左孩子設置為線索 root.setleftisthread(true); root.setleft(pre); } // 右孩子為空 if ( pre != null && null == pre.getright() ) { pre.setrightisthread(true); pre.setright(root); } pre = root; // 線索化右孩子 inthread(root.getright()); } } /** * 中序遍歷線索二叉樹 * */ public void inthreadlist(treenode root) { if (root != null) { // 如果左孩子不是線索 while (root != null && !root.isleftisthread()) { root = root.getleft(); } do { // 如果右孩子是線索 system.out.print(root.getdata() + ","); if (root.isrightisthread()) { root = root.getright(); } // 有右孩子 else { root = root.getright(); while (root != null && !root.isleftisthread()) { root = root.getleft(); } } } while (root != null); } }} |
測試類
|
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
|
package com.testtree;/** * @author pier */public class test { public static void main(string[] args) { //不要問我為什么設置這么大，結尾看我效果截圖 int[] arr = new int[10000]; for (int i = 0; i < arr.length; i++) { arr[i]=i+1; } //創建一顆二叉樹 bitree bitree = new bitree(arr); //中序遍歷二叉樹 system.out.println("中序遍歷結果如下:"); long start1 = system.currenttimemillis(); bitree.inlist(bitree.getroot()); long end1 = system.currenttimemillis(); system.out.println(); system.out.println("普通遍歷時間為:"+(end1-start1)+"毫秒"); system.out.println("\n"); //中序遍歷將二叉樹線索化 bitree.inthread(bitree.getroot()); system.out.println("線索二叉樹中序遍歷如下:"); long start2 = system.currenttimemillis(); bitree.inthreadlist(bitree.getroot()); long end2 = system.currenttimemillis(); system.out.println(); system.out.println("線索二叉樹的遍歷時間為:"+(end2-start2)+"毫秒"); }} |
運行結果
當我使用1-10的時候效果截圖
完全看不出來差距，所以，哈哈才設置那么大，能夠實踐出來線索二叉樹的遍歷速度確實更快的。
ps：看完這篇文章，你不來點個贊嗎？不來個三連嗎？重點是，你今天get到了嗎？別之后alt+insert自動生成get喲，用你那看起來不聰明的小腦袋瓜想一想。
到此這篇關于java數據結構二叉樹難點解析的文章就介紹到這了,更多相關java 二叉樹內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/qq_43325476/article/details/120716127
