溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Java Morris遍歷算法及在二叉樹(shù)中應(yīng)用的方法是什么的相關(guān)知識(shí)，內(nèi)容詳細(xì)易懂，操作簡(jiǎn)單快捷，具有一定借鑒價(jià)值，相信大家閱讀完這篇Java Morris遍歷算法及在二叉樹(shù)中應(yīng)用的方法是什么文章都會(huì)有所收獲，下面我們一起來(lái)看看吧。
Morris遍歷是一種用于二叉樹(shù)遍歷的算法，它可以在不使用?；蜿?duì)列的情況下實(shí)現(xiàn)中序遍歷。該算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。
Morris遍歷的基本思想是，利用葉子節(jié)點(diǎn)的空指針來(lái)存儲(chǔ)臨時(shí)信息，以達(dá)到節(jié)省空間的目的。具體來(lái)說(shuō)，對(duì)于當(dāng)前遍歷到的節(jié)點(diǎn)，如果它有左子節(jié)點(diǎn)，就找到左子樹(shù)中最右邊的節(jié)點(diǎn)，將其右子節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)，然后將當(dāng)前節(jié)點(diǎn)更新為其左子節(jié)點(diǎn)。如果它沒(méi)有左子節(jié)點(diǎn)，就輸出當(dāng)前節(jié)點(diǎn)的值，并將當(dāng)前節(jié)點(diǎn)更新為其右子節(jié)點(diǎn)。重復(fù)以上步驟，直到遍歷完整棵樹(shù)。
Morris遍歷的優(yōu)點(diǎn)是空間復(fù)雜度低O(1)，但它的缺點(diǎn)是會(huì)改變?cè)瓉?lái)的二叉樹(shù)結(jié)構(gòu)，因此需要在遍歷完后還原二叉樹(shù)。此外，該算法可能會(huì)比遞歸或使用棧的算法稍微慢一些。
二叉樹(shù)的線索化,主要是利用了葉子結(jié)點(diǎn)中的空指針域,存放了在某種遍歷順序下的前驅(qū)或者后續(xù)結(jié)點(diǎn),從而達(dá)到了線索二叉樹(shù)的目的
例如,下圖中序遍歷結(jié)果展示如下,根據(jù)中序遍歷對(duì)空指針域進(jìn)行線索化
線索化的二叉樹(shù)為下, 畫(huà)在左邊表示left結(jié)點(diǎn)指向,畫(huà)在右邊表示right指向,例如7的前驅(qū)結(jié)點(diǎn)為5,那么7的left指向5,7的后繼節(jié)點(diǎn)為1,那么7的right指向1
由此,我們可能總結(jié)出這樣的結(jié)論:中序遍歷二叉樹(shù)的指向當(dāng)前結(jié)點(diǎn)的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)的左子樹(shù)的最右端結(jié)點(diǎn),例如指向1的結(jié)點(diǎn)為1的左節(jié)點(diǎn)2的最右端結(jié)點(diǎn)為7,指向2結(jié)點(diǎn)的為2的左節(jié)點(diǎn)4的最右端結(jié)點(diǎn)4.這一點(diǎn)在之后的morris遍歷中很重要
具體的代碼實(shí)現(xiàn)如下:
public class InorderThreadedBinaryTree {
private ThreadTreeNode pre = null;
public void threadedNodes(ThreadTreeNode node) {
//如果node==null，不能線索化
if (node == null) {
return;
}
//1、先線索化左子樹(shù)
threadedNodes(node.left);
//2、線索化當(dāng)前結(jié)點(diǎn)
//處理當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
//以8為例來(lái)理解
//8結(jié)點(diǎn)的.left = null，8結(jié)點(diǎn)的.leftType = 1
if (node.left == null) {
//讓當(dāng)前結(jié)點(diǎn)的左指針指向前驅(qū)結(jié)點(diǎn)
node.left = pre;
//修改當(dāng)前結(jié)點(diǎn)的左指針的類型，指向前驅(qū)結(jié)點(diǎn)
node.leftType = 1;
}
//處理后繼結(jié)點(diǎn)
if (pre != null && pre.right == null) {
//讓當(dāng)前結(jié)點(diǎn)的右指針指向當(dāng)前結(jié)點(diǎn)
pre.right = node;
//修改當(dāng)前結(jié)點(diǎn)的右指針的類型=
pre.rightType = 1;
}
//每處理一個(gè)結(jié)點(diǎn)后，讓當(dāng)前結(jié)點(diǎn)是下一個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
pre = node;
//3、線索化右子樹(shù)
threadedNodes(node.right);
}
}
class ThreadTreeNode {
int val;
ThreadTreeNode left;
//0為非線索化,1為線索化
int leftType;
ThreadTreeNode right;
//0為非線索化,1為線索化
int rightType;
public ThreadTreeNode(int val) {
this.val = val;
}
}但是在實(shí)現(xiàn)Morris遍歷的時(shí)候,并不需要把結(jié)點(diǎn)的左節(jié)點(diǎn)線索化,只需要把結(jié)點(diǎn)的右節(jié)點(diǎn)進(jìn)行線索化即可,具體的原因在下面進(jìn)行分析.
上面我們說(shuō)了Morris遍歷的時(shí)候只需要線索化右節(jié)點(diǎn),這里給大家進(jìn)行解釋.當(dāng)我們?cè)谥行虮闅v一棵樹(shù)的時(shí)候,還比如是這樣一棵樹(shù),我們一步步的node.left來(lái)到了6這個(gè)結(jié)點(diǎn),這個(gè)結(jié)點(diǎn)的left為空,所以我們打印6這個(gè)結(jié)點(diǎn)的值,此時(shí)我們需要返回上一個(gè)結(jié)點(diǎn),如果我們是要中序遞歸進(jìn)行遍歷的話,需要返回上一個(gè)棧,而我們Morris遍歷的時(shí)候無(wú)法進(jìn)行遞歸的返回,所以這個(gè)時(shí)候我們只需要把6的right結(jié)點(diǎn)進(jìn)行線索化,這個(gè)時(shí)候6的right指向4,我們就可以返回到4,把4這個(gè)結(jié)點(diǎn)進(jìn)行打印,4也線索化返回了2,把2進(jìn)行打印,然后進(jìn)行2的right結(jié)點(diǎn)5,5的left結(jié)點(diǎn)為空,因此打印5,之后進(jìn)入到5的right結(jié)點(diǎn)7,打印7,7的right結(jié)點(diǎn)也進(jìn)行了線索化,進(jìn)入7的right結(jié)點(diǎn)為1,然后打印1,進(jìn)入3結(jié)點(diǎn)并且打印
因?yàn)樽詈貌灰淖儤?shù)的結(jié)構(gòu),所以我們?cè)诖蛴〉臅r(shí)候,將線索化的結(jié)點(diǎn)的right結(jié)點(diǎn)置為空.
Morris遍歷是利用了線索二叉樹(shù)的思想,在遍歷的過(guò)程中不適用棧,從而達(dá)到了空間復(fù)雜度為O(1)
具體的實(shí)現(xiàn)如下:
1.初始化當(dāng)前的結(jié)點(diǎn)為根結(jié)點(diǎn)
2.若當(dāng)前的結(jié)點(diǎn)的左節(jié)點(diǎn)為空,則輸出當(dāng)前結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù),即'curr=curr.right'
3.若當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)不為空,則找到當(dāng)前結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),即當(dāng)前結(jié)點(diǎn)左節(jié)點(diǎn)的最右側(cè)結(jié)點(diǎn),記為'prev'
如果'prev.right''為空,則將pre.right指向curr結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的左子樹(shù),即'curr=curr.left'
如果'prev.right''不為空,說(shuō)明已經(jīng)遍歷完了當(dāng)前節(jié)點(diǎn)的左子樹(shù),斷開(kāi) `prev.right` 的連接,即'prev.left=null',輸出當(dāng)前節(jié)點(diǎn),然后遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù),即 `curr=curr.right`.
public class Morris {
/**
* 將當(dāng)前根結(jié)點(diǎn)中序遍歷的結(jié)果存儲(chǔ)到list集合中
* @param root 根結(jié)點(diǎn)
* @return 中序遍歷的結(jié)合
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) { // 左子樹(shù)為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
res.add(curr.val); //如果要求直接打印,直接輸出System.out.println(curr.val);
curr = curr.right;
} else {
// 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
TreeNode prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
// 將前驅(qū)節(jié)點(diǎn)的右子樹(shù)連接到當(dāng)前節(jié)點(diǎn)
prev.right = curr;
curr = curr.left;
} else {
// 前驅(qū)節(jié)點(diǎn)的右子樹(shù)已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開(kāi)連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
prev.right = null;
res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
curr = curr.right;
}
}
}
return res;
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}測(cè)試:
還是這樣一顆二叉樹(shù),輸出如下:
[6, 4, 2, 5, 7, 1, 3]
前序和中序的遍歷很想,只不過(guò)在打印(收集結(jié)點(diǎn)信息的時(shí)候不同),中序遍歷是在當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)為空(curr.left==null),或者當(dāng)前結(jié)點(diǎn)已經(jīng)被線索化(prev.right==curr)的時(shí)候進(jìn)行打印,仔細(xì)觀察前序遍歷的過(guò)程,我們通過(guò)修改打印的順序即可.前序遍歷是在當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)為空(curr.left==null),或者當(dāng)前結(jié)點(diǎn)沒(méi)有被線索化(prev.right==null)的時(shí)候進(jìn)行打印
具體的思路如下:
1.初始化當(dāng)前的結(jié)點(diǎn)為根結(jié)點(diǎn)
2.若當(dāng)前的結(jié)點(diǎn)的左節(jié)點(diǎn)為空,則輸出當(dāng)前結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù),即'curr=curr.right'
3.若當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)不為空,則找到當(dāng)前結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),即當(dāng)前結(jié)點(diǎn)左節(jié)點(diǎn)的最右側(cè)結(jié)點(diǎn),記為'prev'
如果'prev.right''為空,輸出當(dāng)前節(jié)點(diǎn),然后將pre.right指向curr結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的左子樹(shù),即'curr=curr.left'
如果'prev.right''不為空,說(shuō)明已經(jīng)遍歷完了當(dāng)前節(jié)點(diǎn)的左子樹(shù),斷開(kāi) `prev.right` 的連接,即'prev.left=null',然后遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù),即 `curr=curr.right`.
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode curr = root;
while (curr != null) {
if (curr.left == null) { // 左子樹(shù)為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
curr = curr.right;
} else {
// 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
TreeNode prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
res.add(curr.val);//如果要求直接打印,直接輸出System.out.println(curr.val);
// 將前驅(qū)節(jié)點(diǎn)的右子樹(shù)連接到當(dāng)前節(jié)點(diǎn)
prev.right = curr;
curr = curr.left;
} else {
// 前驅(qū)節(jié)點(diǎn)的右子樹(shù)已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開(kāi)連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
prev.right = null;
curr = curr.right;
}
}
}
return res;
}測(cè)試:
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.right = new TreeNode(5);
root.left.right.right = new TreeNode(7);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.left.left = new TreeNode(6);
System.out.println(preorderTraversal(root));
}還是這樣一顆二叉樹(shù),輸出如下:
[1, 2, 4, 6, 5, 7, 3]
后序Morris遍歷實(shí)現(xiàn)起來(lái)有一定的難度,但是基本代碼還是不變,只是在打印的地方有略微的區(qū)別,
具體的思路如下:
1.初始化當(dāng)前的結(jié)點(diǎn)為根結(jié)點(diǎn)
2.若當(dāng)前的結(jié)點(diǎn)的左節(jié)點(diǎn)為空,則輸出當(dāng)前結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的右子樹(shù),即'curr=curr.right'
3.若當(dāng)前結(jié)點(diǎn)的左節(jié)點(diǎn)不為空,則找到當(dāng)前結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),即當(dāng)前結(jié)點(diǎn)左節(jié)點(diǎn)的最右側(cè)結(jié)點(diǎn),記為'prev'
如果'prev.right''為空,然后將pre.right指向curr結(jié)點(diǎn),然后遍歷當(dāng)前結(jié)點(diǎn)的左子樹(shù),即'curr=curr.left'
如果'prev.right''不為空,此時(shí)進(jìn)行逆序存儲(chǔ),說(shuō)明已經(jīng)遍歷完了當(dāng)前節(jié)點(diǎn)的左子樹(shù),斷開(kāi) `prev.right` 的連接,即'prev.left=null',然后遍歷當(dāng)前節(jié)點(diǎn)的右子樹(shù),即 `curr=curr.right`.
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
TreeNode dump = new TreeNode(0);//建立一個(gè)臨時(shí)結(jié)點(diǎn)
dump.left = root; //設(shè)置dump的左節(jié)點(diǎn)為root
TreeNode curr = dump; //當(dāng)前節(jié)點(diǎn)為dump
while (curr != null) {
if (curr.left == null) { // 左子樹(shù)為空，則輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
curr = curr.right;
} else {
// 找到當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
TreeNode prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
if (prev.right == null) {
// 將前驅(qū)節(jié)點(diǎn)的右子樹(shù)連接到當(dāng)前節(jié)點(diǎn)
prev.right = curr;
curr = curr.left;
} else {
reverseAddNodes(curr.left, prev, res);
// 前驅(qū)節(jié)點(diǎn)的右子樹(shù)已經(jīng)連接到當(dāng)前節(jié)點(diǎn)，斷開(kāi)連接，輸出當(dāng)前節(jié)點(diǎn)，然后遍歷右子樹(shù)
prev.right = null;
curr = curr.right;
}
}
}
return res;
}
private void reverseAddNodes(TreeNode begin, TreeNode end, List<Integer> res) {
reverseNodes(begin, end); //將begin到end的進(jìn)行逆序連接
TreeNode curr = end;
while (true) {//將逆序連接后端begin到end添加
res.add(curr.val);
if (curr == begin)
break;
curr = curr.right;
}
reverseNodes(end, begin);//恢復(fù)之前的連接狀態(tài)
}
/**
* 將begin到end的進(jìn)行逆序連接
*
* @param begin
* @param end
*/
private void reverseNodes(TreeNode begin, TreeNode end) {
TreeNode prev = begin;
TreeNode curr = prev.right;
TreeNode post;
while (prev != end) {
post = curr.right;
curr.right = prev;
prev = curr;
curr = post;
}
}測(cè)試:
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.right = new TreeNode(5);
root.left.right.right = new TreeNode(7);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.left.left = new TreeNode(6);
System.out.println(postorderTraversal(root));
}還是這樣一顆二叉樹(shù),輸出如下:
[6, 4, 7, 5, 2, 3, 1]
關(guān)于“Java Morris遍歷算法及在二叉樹(shù)中應(yīng)用的方法是什么”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對(duì)“Java Morris遍歷算法及在二叉樹(shù)中應(yīng)用的方法是什么”知識(shí)都有一定的了解，大家如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼