目錄

一、二叉樹的存儲(chǔ)結(jié)構(gòu)

二、二叉樹的遍歷

---

?

一、二叉樹的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的各個(gè)結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉樹每個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子，所以它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

lchild

data

rchild

定義代碼：

typedef struct Bitnode
{ElemType data;struct Bitnode * lchild ,* rchild;
}Bitnode ,*Bitree;

二、二叉樹的遍歷

1、二叉樹的遍歷（traversing binary tree）是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。

2、二叉樹的遍歷次序不同于線性結(jié)構(gòu)，線性結(jié)構(gòu)最多也就是分為順序、循環(huán)、雙向等簡單的遍歷方式。

3、樹的結(jié)點(diǎn)之間不存在唯一的前驅(qū)和后繼的關(guān)系，在訪問一個(gè)結(jié)點(diǎn)后，下一個(gè)被訪問的結(jié)點(diǎn)面臨著不同的選擇。

4、遍歷方式：

（1）前序遍歷

? ? ? ? 若二叉樹為空，則空操作返回，否則先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，在前序遍歷右子樹。

?

（2）中序遍歷

? ? ? ? 若樹為空，則空操作返回，否則從根結(jié)點(diǎn)開始（注意：并不是先訪問根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問根結(jié)點(diǎn)，最后訪問中序遍歷右子樹

?

?

（3）后序遍歷

? ? ? ? 若樹為空，則空操作返回，否則從左到右先從葉子后結(jié)點(diǎn)的方式遍歷訪問左右子樹，最后訪問根結(jié)點(diǎn)。?

?

（4）層序遍歷

? ? ? ? ?若樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點(diǎn)開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。

?