前言
本章，我們主要需要了解以下內(nèi)容
- 什么是線索二叉樹
- 怎么去把二叉樹線索化
- 怎么通過線索二叉樹查找某個(gè)數(shù)的后繼結(jié)點(diǎn)
- 二叉樹的查看——二叉樹怎們遍歷
什么是線索二叉樹
首先我們來了解一下什么是線索二叉樹？
定義：一個(gè)二叉樹通過如下的方法“穿起來”：所有原本為空的右(孩子)指針改為指向該節(jié)點(diǎn)在中序序列中的后繼，所有原本為空的左(孩子)指針改為指向該節(jié)點(diǎn)的中序序列的前驅(qū)。
再看一下為什么要有線索二叉樹？
顧名思義，線索二叉樹，肯定是根據(jù)線索查找，查找速度肯定更快。
- 線索二叉樹能線性地遍歷二叉樹，從而比遞歸的中序遍歷更快。使用線索二叉樹也能夠方便的找到一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，這比顯式地使用父親節(jié)點(diǎn)指針或者棧效率更高。這在棧空間有限，或者無法使用存儲父節(jié)點(diǎn)的棧時(shí)很有作用（對于通過深度優(yōu)先搜索來查找父節(jié)點(diǎn)而言)。
那線索僅僅是這樣嗎？當(dāng)然不，我們都是懶的，能等待解決的問題，為什么會去想新的辦法。我們要解決的是:
- 為了解決無法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前驅(qū)和后繼結(jié)點(diǎn)的問題
- 但是同時(shí)出現(xiàn)了二叉鏈表找左、右孩子困難的問題，即在構(gòu)建線索二叉樹之后，鏈表的原來遍歷方式會出問題。
最后看一下什么線索二叉樹的圖解
在我們的線索二叉樹的書上，基本上都有以下這張圖：
大家看到上面這張圖還是有點(diǎn)懵的叭，我們一起看一下我下面手畫的圖
怎么去把二叉樹線索化
哦！在著之前獻(xiàn)給大家提一下，二叉樹的遍歷方式，有這樣的幾種
- 前序遍歷二叉樹的遞歸定義(根左右)
- 中序遍歷二叉樹的遞歸定義(左根右)
- 后續(xù)遍歷二叉樹的遞歸意義(左右根)
本博文主要討論的是中序遍歷
它的中序遍歷結(jié)果就是abcde f ghi
它的中序線索二叉樹遍歷如下
先畫線索二叉樹
虛線箭頭為線索指針，對于所有左指針指向空的節(jié)點(diǎn)：將該節(jié)點(diǎn)的左指針指向該節(jié)點(diǎn)在中序遍歷中的上一節(jié)點(diǎn)；對于所有右指針指向空的節(jié)點(diǎn)，將該節(jié)點(diǎn)的右指針指向該節(jié)點(diǎn)在中序遍歷中的下一結(jié)點(diǎn)。最后一個(gè)末尾結(jié)點(diǎn)除外。
中序圖解線索二叉樹
怎么通過線索二叉樹查找某個(gè)數(shù)的后繼結(jié)點(diǎn)
即形成了一個(gè)特殊的雙向鏈表，之所以特殊，以f–>e為例，f–>e并不是直接到達(dá)，而是通過f–>b–>d–>e間接到達(dá)。
我們嘗試用java去構(gòu)建一顆線索二叉樹叭
先申明，我從未使用java構(gòu)建過樹，二叉樹都沒有，若有錯(cuò)誤，請指出
數(shù)據(jù)結(jié)點(diǎn)類
|
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 { /**數(shù)據(jù)域**/ private int data; /**左指針**/ private treenode left; /** 左孩子是否為線索，采用布爾類型主要是判斷是否未null足以**/ private boolean leftisthread; /**右指針**/ private treenode right; /** 右孩子是否為線索**/ private boolean rightisthread; /**根據(jù)數(shù)據(jù)域來確定所在的指針對應(yīng)位置**/ 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 { /** 根節(jié)點(diǎn) **/ private treenode root; /** 大小 **/ private int size; /** 線索化的時(shí)候保存前驅(qū) **/ 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; // 創(chuàng)建二叉樹 this.root = createtree(data, 1); } /** * 創(chuàng)建二叉樹 * */ 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() ) { // 將左孩子設(shè)置為線索 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) { //不要問我為什么設(shè)置這么大，結(jié)尾看我效果截圖 int[] arr = new int[10000]; for (int i = 0; i < arr.length; i++) { arr[i]=i+1; } //創(chuàng)建一顆二叉樹 bitree bitree = new bitree(arr); //中序遍歷二叉樹 system.out.println("中序遍歷結(jié)果如下:"); long start1 = system.currenttimemillis(); bitree.inlist(bitree.getroot()); long end1 = system.currenttimemillis(); system.out.println(); system.out.println("普通遍歷時(shí)間為:"+(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("線索二叉樹的遍歷時(shí)間為:"+(end2-start2)+"毫秒"); }} |
運(yùn)行結(jié)果
當(dāng)我使用1-10的時(shí)候效果截圖
完全看不出來差距，所以，哈哈才設(shè)置那么大，能夠?qū)嵺`出來線索二叉樹的遍歷速度確實(shí)更快的。
ps：看完這篇文章，你不來點(diǎn)個(gè)贊嗎？不來個(gè)三連嗎？重點(diǎn)是，你今天get到了嗎？別之后alt+insert自動生成get喲，用你那看起來不聰明的小腦袋瓜想一想。
到此這篇關(guān)于java數(shù)據(jù)結(jié)構(gòu)二叉樹難點(diǎn)解析的文章就介紹到這了,更多相關(guān)java 二叉樹內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/qq_43325476/article/details/120716127
