目錄

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

二、二叉樹(shù)的遍歷

---

?

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

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

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉樹(shù)每個(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;

二、二叉樹(shù)的遍歷

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

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

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

4、遍歷方式：

（1）前序遍歷

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

?

（2）中序遍歷

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

?

?

（3）后序遍歷

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

?

（4）層序遍歷

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

?