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

為什么鏈表無法知道前一個節(jié)點？

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

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

鏈表的每個節(jié)點恰好包含一個指針是錯誤的。

鏈表包括單鏈表和雙鏈表，雙鏈表實際上是單鏈表的改進。

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

如何判斷兩個鏈表是否相交，以及交點？

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

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

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

(1)n0時，為空樹；

(2)n1時，只有一個節(jié)點，稱為根節(jié)點；

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

圖1二叉樹

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

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

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

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

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

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

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

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

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

圖2完成后的二叉樹

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

a B C D E∧H∧F G I顯然，當(dāng)一棵不完全二叉樹采用順序存儲結(jié)構(gòu)時，需要添加許多空節(jié)點，因為這樣會造成很大的空間浪費。

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

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

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

左指針字段數(shù)據(jù)字段右指針字段，即Lchild數(shù)據(jù)Rchild，其中:數(shù)據(jù)字段存儲節(jié)點的數(shù)據(jù)信息；Lchild和Rchild分別存儲左右分支的指針。當(dāng)分支不存在時，相應(yīng)的指針字段為空(用符號∧ NULL表示)。與圖1中的節(jié)點C一樣，因為它的左分支不存在，所以它的Lchild值為NULL。

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

1.前序遍歷

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

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

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

2.中序遍歷

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

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

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

3.后續(xù)遍歷

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

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

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

4.序列遍歷

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

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

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