為什么鏈表無法知道前一個(gè)節(jié)點(diǎn)？如果你知道鏈表的頭指針，你可以從頭指針開始向后遍歷。記錄下一個(gè)節(jié)點(diǎn)地址和上一個(gè)節(jié)點(diǎn)地址。如果當(dāng)前節(jié)點(diǎn)地址與指定的節(jié)點(diǎn)地址相同，則找到前一個(gè)節(jié)點(diǎn)。為什么鏈表的每個(gè)節(jié)點(diǎn)中都恰

為什么鏈表無法知道前一個(gè)節(jié)點(diǎn)？

如果你知道鏈表的頭指針，你可以從頭指針開始向后遍歷。記錄下一個(gè)節(jié)點(diǎn)地址和上一個(gè)節(jié)點(diǎn)地址。如果當(dāng)前節(jié)點(diǎn)地址與指定的節(jié)點(diǎn)地址相同，則找到前一個(gè)節(jié)點(diǎn)。

為什么鏈表的每個(gè)節(jié)點(diǎn)中都恰好包含一個(gè)指針？

鏈表的每個(gè)節(jié)點(diǎn)恰好包含一個(gè)指針是錯(cuò)誤的。

鏈表包括單鏈表和雙鏈表，雙鏈表實(shí)際上是單鏈表的改進(jìn)。

鏈表中的每個(gè)節(jié)點(diǎn)可以包含多個(gè)指針字段，分別存儲(chǔ)多個(gè)指針。例如，雙向鏈表中的一個(gè)節(jié)點(diǎn)可以包含兩個(gè)指針字段，分別存儲(chǔ)指向其直接前任和直接繼任者的指針。

如何判斷兩個(gè)鏈表是否相交，以及交點(diǎn)？

方法一:直接判斷第一個(gè)鏈表的每個(gè)節(jié)點(diǎn)是否在第二個(gè)鏈表中，時(shí)間復(fù)雜度為O(l

順序存儲(chǔ)的二叉樹是如何創(chuàng)建和遍歷的？

首先，簡單介紹一下什么是a "二叉樹 "。二叉樹是n個(gè)節(jié)點(diǎn)的有限集合，其定義是遞歸的:

(1)n0時(shí)，為空樹；

(2)n1時(shí)，只有一個(gè)節(jié)點(diǎn)，稱為根節(jié)點(diǎn)；

(ngt1時(shí)，除根節(jié)點(diǎn)外的其他節(jié)點(diǎn)可以分成兩個(gè)不相交的子集，稱為左右子樹，左右子樹本質(zhì)上也是二叉樹。

圖1二叉樹

根據(jù)二叉樹的結(jié)構(gòu)和定義，二叉樹的特征可以概括為:

(1)非空二叉樹的第一層最多有2∧(i-1)個(gè)節(jié)點(diǎn)；

(2)深度為k的二叉樹最多有2∧k-1個(gè)節(jié)點(diǎn)。

二叉樹二叉樹的存儲(chǔ)結(jié)構(gòu)是非線性結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多有一個(gè) "前任 "，但它可以有多個(gè) "接班人 "。它可以采用順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

1.順序存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)是用一組連續(xù)的存儲(chǔ)單元來存儲(chǔ)二叉樹的節(jié)點(diǎn)。二叉樹的所有節(jié)點(diǎn)必須排列成適當(dāng)?shù)男蛄?，?jié)點(diǎn)在這個(gè)序列中的相互位置可以反映節(jié)點(diǎn)之間的邏輯關(guān)系。

要介紹順序存儲(chǔ)結(jié)構(gòu)，首先要了解一個(gè)概念——完全二叉樹。如果深度為k，當(dāng)k和n滿足2∧(k-1)≦n≦2∧k-1時(shí)，一棵有n個(gè)節(jié)點(diǎn)的二叉樹稱為完全二叉樹。

對(duì)于二叉樹，如果不是完全二叉樹，先添加一些不存在的空節(jié)點(diǎn)使之成為完全二叉樹，然后將樹中的節(jié)點(diǎn)按照從上到下，從左到右的順序存儲(chǔ)在數(shù)組中。

以圖1為例，補(bǔ)充成如圖2所示的完整二叉樹。

圖2完成后的二叉樹

其順序存儲(chǔ)狀態(tài)為:

a B C D E∧H∧F G I顯然，當(dāng)一棵不完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，需要添加許多空節(jié)點(diǎn)，因?yàn)檫@樣會(huì)造成很大的空間浪費(fèi)。

2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用鏈?zhǔn)奖硎镜亩鏄涔?jié)點(diǎn)之間的邏輯關(guān)系。

通常的方法是鏈表中的每個(gè)節(jié)點(diǎn)由三個(gè)域組成:

左指針字段數(shù)據(jù)字段右指針字段，即Lchild數(shù)據(jù)Rchild，其中:數(shù)據(jù)字段存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)信息；Lchild和Rchild分別存儲(chǔ)左右分支的指針。當(dāng)分支不存在時(shí)，相應(yīng)的指針字段為空(用符號(hào)∧ NULL表示)。與圖1中的節(jié)點(diǎn)C一樣，因?yàn)樗淖蠓种Р淮嬖?，所以它的Lchild值為NULL。

三、二叉樹的遍歷算法二叉樹常見的遍歷方法有:前序遍歷、中間遍歷、后繼遍歷和順序遍歷。

1.前序遍歷

首先訪問根節(jié)點(diǎn)，然后是左邊的子樹，最后是右邊的子樹。

圖1中前序遍歷的結(jié)果是:

a-gt b-gtD-gtE-gtF-gtG-gtC-gtH-gtI

2.中序遍歷

首先訪問左邊的子樹，然后是根節(jié)點(diǎn)，最后是右邊的子樹。

圖1中中間序列遍歷的結(jié)果是:

d-gtB-gtF-gtE-gtG-gtA-gtC-gtI-gtH

3.后續(xù)遍歷

首先訪問左邊的子樹，然后是右邊的子樹，最后是根節(jié)點(diǎn)。

圖1中后續(xù)遍歷的結(jié)果是:

d-gtgtF-gtG-gtE-gti-gtH-gt b-gtC-gtA

4.序列遍歷

從頂層節(jié)點(diǎn)開始，依次從左到右遍歷，然后到第二層，繼續(xù)從左到右遍歷，…直到遍歷完所有節(jié)點(diǎn)。

圖1中的序列遍歷結(jié)果如下:

a-gt b-gtC-gt D-gtE-gtH-gtF-gtG-gtI