二叉搜索樹轉化為雙向鏈表

Yangyang 發布于2019-08-16 12:45 / 1587人閱讀

摘要：首先需要明白二叉搜索樹也是一種排序的數據結構，它的中序遍歷就是一個不遞減的順序排列所以如果要轉換成一個排序好的雙向鏈表，那么僅需要改變原來指向左子節點和右子節點的指針，讓他們分別指向前節點和后節點即可，如圖所示調整指針原先指向左子節點的指針

首先需要明白二叉搜索樹也是一種排序的數據結構，它的中序遍歷就是一個不遞減的順序排列

所以如果要轉換成一個排序好的雙向鏈表，那么僅需要改變原來指向左子節點和右子節點的指針，讓他們分別指向前節點和后節點即可，如圖所示

調整指針

原先指向左子節點的指針調整為鏈表中指向前一個節點的指針

原先指向右子節點的指針調整為鏈表中指向后一個節點的指針

如何調整

考慮根節點和左右子樹的根本情況，因為如果用遞歸，這種根本情況考慮就可以去將同樣的方法用到左右子樹上

對于這種基本情況，可以分成三個部分來看，根節點10，左子樹，右子樹，需要做的就是將10與左子樹中的最大值連起來，然后把10與右子樹中的最小值連起來

現在有個問題就是我們并不知道左子樹中的最大值和右子樹中的最小值，如果我們知道就好了。但是想到遞歸，遞歸到左子樹中，如果左子樹已轉換為雙向鏈表，那么雙向鏈表的最后一個節點就是我們想要的，而右子樹中的第一個節點也是我們想要的

轉換代碼

public static BinaryTreeNode baseconvert(BinaryTreeNode root, BinaryTreeNode lastNode) {

if (root == null)

return lastNode;

BinaryTreeNode current = root;

if (current.leftNode != null)

lastNode=baseconvert(current.leftNode, lastNode);

current.leftNode = lastNode;

if (lastNode != null)

lastNode.rightNode = current;

lastNode = current;

if (current.rightNode != null)

lastNode=baseconvert(current.rightNode, lastNode);

return lastNode;

}

至于為什么需要一個lastNode，

上面的代碼中有兩個參數，一個是根節點，一個是已經轉換好的鏈表的最后一個節點，因為二叉搜索樹中序遍歷的特性，當遍歷到根節點的時候，左子樹已經排好序了，所以會有一個左子樹已經轉換好的鏈表，而這個鏈表的最后一個節點即是我們需要和根節點左連的節點

至于為什么需要一個lastNode，假設當前節點的左子樹都排好序，那么現在lastNode應該是左子樹的最大節點（也就是左子樹的右兒子的右兒子的右兒子直到沒有右兒子的那個節點。）如果不保存lastNode找到當前節點的左子樹的最大節點是不容易的。

另外需要說明的是lastNode指向的是已經排好序的雙向鏈表的尾節點（這個尾節點的pre已經指向完畢了，右節點還沒處理好。）

最開始的時候lastNode為null

current為當前子樹的根節點

如果左子樹存在，那么轉換左子樹，遞歸下去，遞歸返回之后，說明找到了鏈表的第一個節點，也就是4那個節點，將4的前面節點置為null，此時current為4那個節點，這個時候由于6的4這個左子樹已遍歷完了，所以需要往上層返回，返回之前需要將current賦值給lastNode，說明4這個左子樹的最后一個節點就是4

由于往上返回了一層，此時的current已經是6了，將6的左節點賦值為之前返回的4，判斷之前返回的lastNode是否為null，不為空說明需要把根節點和lastNode連起來，其實lastNode為null的情況就只有第一個節點會出現，其他的時候都不會出現。現在已排好序的包括6的左子樹以及6本身了，所以此時的lastNode為6

6和4的雙向連接就完成了，由于6的右子樹存在，又會遞歸到右邊子樹去，由于8不存在左右子樹，遞歸下去一層之后current就是8這個節點，但它的左孩子為空，所以不會左邊遞歸下去，將8的左連接與之前的lastNode連接起來，建立雙向連接的一條連接，然后由于lastNode不為空，所以又把lastNode的右連接與8連接起來，至此雙向連接建立，此時lastNode為8

所以468都已排好序，此時lastNode為8，返回到上一層，也就是根節點10了，在這一層current為10，將current的左連接與lastNode連接起來，如果lastNode存在，將lastNode的右連接與10連接一起，以此建立雙向連接。至此就將根節點和左子樹都連接起來了，然后就是去轉換右子樹，現在的lastNode為10，current為14，14有左孩子，所以需要遞歸到下一層，下一層的current為12，12沒有左孩子，所以不用在坐遞歸，所以12是12這棵子樹轉換成雙向鏈表的最左邊的節點，將lastNode與12連接，也就是10與12連接，此時的lastNode就變成了12，再將12的右子樹遞歸，由于沒有右子樹，所以直接返回到上一層，上一層的current是14,14與已排好序的lastNode連接，也就是12與14連接，然后lastNode變為14，遞歸到14的右子樹，也就current變為16，16再遞歸左子樹，無左子樹，將16與14連接，此時的lastNode變為16，遞歸右子樹，無右子樹，所以整個遞歸工作完成

GPU云服務器云服務器二叉鏈表雙向鏈表二叉樹轉鏈表java 二叉樹排序樹規則

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/71650.html

這幾道Java集合框架面試題在面試中幾乎必問

摘要：若遇到哈希沖突，則將沖突的值加到鏈表中即可。之后相比于之前的版本，之后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值默認為時，將鏈表轉化為紅黑樹，以減少搜索時間。有序，唯一紅黑樹自平衡的排序二叉樹。本文是最最最常見Java面試題總結系列第三周的文章。主要內容： Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區別 HashMap的底層...

bigdevil_s 2019-08-19 11:01 評論0 收藏0
【刷算法】二叉搜索樹與雙向鏈表

摘要：題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。題目描述輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。分析如果是這樣一棵二叉搜索樹： showImg(https://segmentfault.com/img/remote/14600000...

FreeZinG 2019-08-22 18:32 評論0 收藏0
javascript數據結構

摘要：數據結構棧一種遵從先進后出原則的有序集合隊列遵從先進先出原則的有序項優先隊列修改版的隊列，設置優先級循環隊列基于隊列，克服假溢出想象的隊列。這種數據結構非常方便，提供了一個便利的語法來訪問它的元素。 javascript數據結構棧一種遵從先進后出原則的有序集合隊列遵從先進先出原則的有序項優先隊列修改版的隊列，設置優先級循環隊列基于隊列，克服‘假溢出’想象的隊列。例如隊列...

desdik 2019-08-23 13:50 評論0 收藏0
二叉樹那些事兒

摘要：大家在聊到二叉樹的時候，總會離不開鏈表。受限線性表主要包括棧和隊列，受限表示對結點的操作受限制。存儲結構線性表主要由順序表示或鏈式表示。鏈式表示指的是用一組任意的存儲單元存儲線性表中的數據元素，稱為線性表的鏈式存儲結構。大家在聊到二叉樹的時候，總會離不開鏈表。這里先帶大家一起了解一些基本概念。線性表概念線性表是最基本、最簡單、也是最常用的一種數據結構。線性表中數據元素之間的關...

Little_XM 2019-08-22 16:28 評論0 收藏0
「中高級前端」窺探數據結構的世界- ES6版

摘要：單鏈表與雙向鏈表單鏈表是表示一系列節點的數據結構，其中每個節點指向列表中的下一個節點。且分別稱為該結點的左子樹與右子樹。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。1. 什么是數據結構？數據結構是在計算機中組織和存儲數據的一種特殊方式，使得數據可以高效地被訪問和修改。更確切地說，數據結構是數據值的集合，表示數據之間的關系，也包括了作用在數據上...

Lucky_Boy 2019-05-22 10:29 評論0 收藏0