為什么鏈表無法知道前一個節點？

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

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

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

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

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

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

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

順序存儲的二叉樹是如何創建和遍歷的？

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

(1)n0時，為空樹；

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

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

圖1二叉樹

根據二叉樹的結構和定義，二叉樹的特征可以概括為:

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

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

二叉樹二叉樹的存儲結構是非線性結構，每個節點最多有一個"前任"，但它可以有多個"接班人"。它可以采用順序存儲結構和鏈式存儲結構。

1.順序存儲結構

二叉樹的順序存儲是用一組連續的存儲單元來存儲二叉樹的節點。二叉樹的所有節點必須排列成適當的序列，節點在這個序列中的相互位置可以反映節點之間的邏輯關系。

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

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

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

圖2完成后的二叉樹

其順序存儲狀態為:

aBCDE∧H∧FGI顯然，當一棵不完全二叉樹采用順序存儲結構時，需要添加許多空節點，因為這樣會造成很大的空間浪費。

2.鏈式存儲結構

二叉樹的鏈式存儲結構是指用鏈式表示的二叉樹節點之間的邏輯關系。

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

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

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

1.前序遍歷

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

圖1中前序遍歷的結果是:

a-gtb-gtD-gtE-gtF-gtG-gtC-gtH-gtI

2.中序遍歷

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

圖1中中間序列遍歷的結果是:

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

3.后續遍歷

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

圖1中后續遍歷的結果是:

d-gtgtF-gtG-gtE-gti-gtH-gtb-gtC-gtA

4.序列遍歷

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

圖1中的序列遍歷結果如下:

a-gtb-gtC-gtD-gtE-gtH-gtF-gtG-gtI