成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

二叉搜索樹轉(zhuǎn)化為雙向鏈表

Yangyang / 1638人閱讀

摘要：首先需要明白二叉搜索樹也是一種排序的數(shù)據(jù)結(jié)構(gòu)，它的中序遍歷就是一個(gè)不遞減的順序排列所以如果要轉(zhuǎn)換成一個(gè)排序好的雙向鏈表，那么僅需要改變?cè)瓉碇赶蜃笞庸?jié)點(diǎn)和右子節(jié)點(diǎn)的指針，讓他們分別指向前節(jié)點(diǎn)和后節(jié)點(diǎn)即可，如圖所示調(diào)整指針原先指向左子節(jié)點(diǎn)的指針

首先需要明白二叉搜索樹也是一種排序的數(shù)據(jù)結(jié)構(gòu)，它的中序遍歷就是一個(gè)不遞減的順序排列

所以如果要轉(zhuǎn)換成一個(gè)排序好的雙向鏈表，那么僅需要改變?cè)瓉碇赶蜃笞庸?jié)點(diǎn)和右子節(jié)點(diǎn)的指針，讓他們分別指向前節(jié)點(diǎn)和后節(jié)點(diǎn)即可，如圖所示

調(diào)整指針

原先指向左子節(jié)點(diǎn)的指針調(diào)整為鏈表中指向前一個(gè)節(jié)點(diǎn)的指針

原先指向右子節(jié)點(diǎn)的指針調(diào)整為鏈表中指向后一個(gè)節(jié)點(diǎn)的指針

如何調(diào)整

考慮根節(jié)點(diǎn)和左右子樹的根本情況，因?yàn)槿绻眠f歸，這種根本情況考慮就可以去將同樣的方法用到左右子樹上

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

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

轉(zhuǎn)換代碼

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;

}

至于為什么需要一個(gè)lastNode，

上面的代碼中有兩個(gè)參數(shù)，一個(gè)是根節(jié)點(diǎn)，一個(gè)是已經(jīng)轉(zhuǎn)換好的鏈表的最后一個(gè)節(jié)點(diǎn)，因?yàn)槎嫠阉鳂渲行虮闅v的特性，當(dāng)遍歷到根節(jié)點(diǎn)的時(shí)候，左子樹已經(jīng)排好序了，所以會(huì)有一個(gè)左子樹已經(jīng)轉(zhuǎn)換好的鏈表，而這個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)即是我們需要和根節(jié)點(diǎn)左連的節(jié)點(diǎn)

至于為什么需要一個(gè)lastNode，假設(shè)當(dāng)前節(jié)點(diǎn)的左子樹都排好序，那么現(xiàn)在lastNode應(yīng)該是左子樹的最大節(jié)點(diǎn)（也就是左子樹的右兒子的右兒子的右兒子直到?jīng)]有右兒子的那個(gè)節(jié)點(diǎn)。）如果不保存lastNode找到當(dāng)前節(jié)點(diǎn)的左子樹的最大節(jié)點(diǎn)是不容易的。

另外需要說明的是lastNode指向的是已經(jīng)排好序的雙向鏈表的尾節(jié)點(diǎn)（這個(gè)尾節(jié)點(diǎn)的pre已經(jīng)指向完畢了，右節(jié)點(diǎn)還沒處理好。）

最開始的時(shí)候lastNode為null

current為當(dāng)前子樹的根節(jié)點(diǎn)

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

由于往上返回了一層，此時(shí)的current已經(jīng)是6了，將6的左節(jié)點(diǎn)賦值為之前返回的4，判斷之前返回的lastNode是否為null，不為空說明需要把根節(jié)點(diǎn)和lastNode連起來，其實(shí)lastNode為null的情況就只有第一個(gè)節(jié)點(diǎn)會(huì)出現(xiàn)，其他的時(shí)候都不會(huì)出現(xiàn)?，F(xiàn)在已排好序的包括6的左子樹以及6本身了，所以此時(shí)的lastNode為6

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/71650.html

相關(guān)文章

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

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

    bigdevil_s 評(píng)論0 收藏0

  • 【刷算法】二叉搜索樹與雙向鏈表

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

    FreeZinG 評(píng)論0 收藏0

  • javascript數(shù)據(jù)結(jié)構(gòu)

    摘要：數(shù)據(jù)結(jié)構(gòu)棧一種遵從先進(jìn)后出原則的有序集合隊(duì)列遵從先進(jìn)先出原則的有序項(xiàng)優(yōu)先隊(duì)列修改版的隊(duì)列，設(shè)置優(yōu)先級(jí)循環(huán)隊(duì)列基于隊(duì)列，克服假溢出想象的隊(duì)列。這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了一個(gè)便利的語法來訪問它的元素。 javascript數(shù)據(jù)結(jié)構(gòu) 棧 一種遵從先進(jìn)后出原則的有序集合 隊(duì)列 遵從先進(jìn)先出原則的有序項(xiàng) 優(yōu)先隊(duì)列 修改版的隊(duì)列，設(shè)置優(yōu)先級(jí) 循環(huán)隊(duì)列 基于隊(duì)列，克服‘假溢出’想象的隊(duì)列。例如隊(duì)列...

    desdik 評(píng)論0 收藏0

  • 二叉樹那些事兒

    摘要：大家在聊到二叉樹的時(shí)候，總會(huì)離不開鏈表。受限線性表主要包括棧和隊(duì)列，受限表示對(duì)結(jié)點(diǎn)的操作受限制。存儲(chǔ)結(jié)構(gòu)線性表主要由順序表示或鏈?zhǔn)奖硎?。鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 大家在聊到二叉樹的時(shí)候，總會(huì)離不開鏈表。這里先帶大家一起了解一些基本概念。 線性表 概念 線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。 線性表中數(shù)據(jù)元素之間的關(guān)...

    Little_XM 評(píng)論0 收藏0

  • 「中高級(jí)前端」窺探數(shù)據(jù)結(jié)構(gòu)的世界- ES6版

    摘要：?jiǎn)捂湵砼c雙向鏈表單鏈表是表示一系列節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)節(jié)點(diǎn)指向列表中的下一個(gè)節(jié)點(diǎn)。且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。1. 什么是數(shù)據(jù)結(jié)構(gòu)？ 數(shù)據(jù)結(jié)構(gòu)是在計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)的一種特殊方式，使得數(shù)據(jù)可以高效地被訪問和修改。更確切地說，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)值的集合，表示數(shù)據(jù)之間的關(guān)系，也包括了作用在數(shù)據(jù)上...

    Lucky_Boy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<