elemtype data;
struct btnode *lchild, *rchild, *parent;
} btnode, *bintree;
例：用二叉鍊錶儲存n個結點的二叉樹(n>0)，共有(n+1)個空指標域；採用三叉鍊錶儲存，共有(n+2)個空指標域。
①空樹：bt==null ②左右子樹均空：bt->lchild==null and bt->rchild==null
③右子樹為空：bt->rchild==null ④左子樹為空：bt->lchild==null
⑤左右子樹均非空。
前兩種常作為遞迴結束條件，後三者常需要遞迴。
常見有四種遍歷方式
按層次遍歷，先序遍歷，中序遍歷，後序遍歷。
按層次遍歷：「從上至下，從左至右」，利用佇列。
先序遍歷：dlr；中序遍歷：ldr；後序遍歷lrd。
例：寫出a+b*(c-d)-e/f的字首、中綴和字尾表示式。
畫出二叉樹，分別進行前序、中序、後序遍歷即可得到。
字首表示式：- + a * b - c d / e f
中綴表示式：a + b * c - d - e / f
字尾表示式：a b c d - * + e f / -
先序遍歷演算法
void preorder ( bintree bt )
}中序遍歷演算法
void inorder ( bintree bt )
}後序遍歷
void postorder ( bintree bt )
}非遞迴遍歷二叉樹
一般借助棧實現。設想一指標沿二叉樹中序順序移動，每當向上層移動時就要出棧。
(a) 中序非遞迴遍歷
指標p從根開始，首先沿著左子樹向下移動，同時入棧儲存；當到達空子樹後需要退棧訪問結點，然後移動到右子樹上去。
void inorder ( bintree bt, visitfunc visit )
else
}}(b) 先序非遞迴遍歷
按照中序遍歷的順序，將訪問結點的位置放在第一次指向該結點時。
void preorder ( bintree bt, visitfunc visit )
else
}}或者，由於訪問過的結點便可以棄之不用，只要能訪問其左右子樹即可，寫出如下演算法。
void preorder ( bintree bt, visitfunc visit )
}}(c) 後序非遞迴遍歷
後序遍歷時，分別從左子樹和右子樹共兩次返回根結點，只有從右子樹返回時才訪問根結點，所以增加乙個棧標記到達結點的次序。
void postorder ( bintree bt, visitfunc visit )
else else
}}}注：後序非遞迴遍歷的過程中，棧中保留的是當前結點的所有祖先。這是和先序及中序遍歷不同的。在某些和祖先有關的演算法中，此演算法很有價值。
寫出遍歷序列（前、中、後序）
根據遍歷序列畫出二叉樹
(a) 已知前序和中序序列，唯一確定二叉樹。
例：前序：abdegcfh，中序：dbgeafhc，畫出二叉樹。
分析：前序序列的第乙個是根，這是解題的突破口。
步驟：①前序序列的第乙個是根 ②在中序序列中標出根，分成左右子樹 ③在前序序列中標出左右子樹(根據結點個數即可) ④分別對左右子樹的前序和中序序列重複以上步驟直至完成。
(b) 已知後序和中序序列，唯一確定二叉樹。
例：後序：dgebhfca，中序：dbgeafhc，畫出二叉樹。
分析：後序序列的最後乙個是根，這是解題的突破口。
步驟：①後序序列的最後乙個是根 ②在中序序列中標出根，分成左右子樹 ③在後序序列中標出左右子樹(根據結點個數即可) ④分別對左右子樹的後序和中序序列重複以上步驟直至完成。
(c) 已知前序和後序序列，不存在度為1的結點時能唯一確定二叉樹。
例：前序：abdec，後序：debca，畫出二叉樹。又前序ab，後序ba則不能唯一確定二叉樹。
注：對於不存在度為1的結點的二叉樹，首先確定根結點，然後總可以將其餘結點序列劃分成左右子樹，以此類推即可確定二叉樹。
說明：畫出二叉樹後可以進行遍歷以便驗證。
編寫演算法
思路：按五種形態(①--⑤)分析，適度簡化。
例：求二叉樹結點的個數。
分析：① 0; ② 1; ③ l+1; ④ 1+r; ⑤ 1+l+r。
簡化：② 1+l=0+r=0 ③ 1+l+r=0 ④ 1+l=0+r ⑤ 1+l+r 可合併成⑤一種情況。
int nodecount ( bintree bt )
例：求二叉樹葉子結點的個數。
分析：① 0; ② 1; ③ l; ④ r; ⑤ l+r。簡化：③④⑤可合併成⑤。
int leafcount ( bintree bt )
例：求二叉樹的深度。
分析：① 0; ② 1; ③ 1+l; ④ 1+r; ⑤ 1+max(l,r)。簡化：②③④⑤可合併成⑤。
int depth ( bintree bt )
線索n個結點的二叉鍊錶中有n+1個空指標，可以利用其指向前驅或後繼結點，叫線索，同時需附加乙個標誌，區分是子樹還是線索。
lchild 有左子樹，則指向左子樹，標誌ltag == 0；
沒有左子樹，可作為前驅線索，標誌ltag == 1。
rchild 有右子樹，則指向右子樹，標誌rtag == 0；
沒有右子樹，可作為後繼線索，標誌rtag == 1。
線索化二叉樹
利用空指標作為線索指向前驅或後繼。左邊空指標可以作為前驅線索，右邊空指標可以作為後繼線索，可以全線索化或部分線索化。
表 6.1 線索化二叉樹的型別
畫出線索二叉樹
思路：先寫出遍歷序列，再畫線索。
步驟： 標出必要的空指標（前驅左指標；後繼右指標，要點：「不要多標，也不要少標」）。
資料結構複習指導
1.資料結構是指 a a.資料元素的組織形式 b.資料型別 c.資料儲存結構d.資料定義 2.資料在計算機儲存器內表示時，實體地址與邏輯位址不相同的，稱之為 c a.儲存結構b.邏輯結構 c.鏈式儲存結構d.順序儲存結構 3.樹形結構是資料元素之間存在一種 d a.一對一關係 b.多對多關係 c.多...
《資料結構》複習指導
自學考試 資料結構 複習指導 第一章 緒論 一 概念 資料結構 是一門研究程式設計中計算機操作的物件以及它們之間的關係和運算的一門學科。資料 是描述額觀事物的數 字元以及所有能輸入到計算機中被電腦程式加工處理的資訊的集合。資料元素 資料元素是資料的基本單位。乙個資料項或多個資料項 域 資料項是資料的...
2019資料結構複習指導
考試題型 選擇題 24 填空題 20 解析題 10 運算題 10 簡答題 10 演算法填空 10 演算法設計 14 第一章緒論 1 資料結構的凡個方面，什麼是邏輯結構，什麼是儲存結構。常見的運算有哪些。答 資料元素之間的邏輯關係，即資料的邏輯結構。資料元素及其關係在計算機儲存器中的儲存方式，即資料的...