二叉樹存儲結構的類型定義：
＃define MAX_SIZE 100
typedef telemtype sqbitree[MAX_SIZE];用一組地址連續的存儲單元依次“自上而下、自左至右”存儲完全二叉樹的數據元素。
對於完全二叉樹上編號為i的結點元素存儲在一維數組的下標值為i-1的分量中，如圖6-6(c)所示。
對於一般的二叉樹，將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組中，
設計不同的結點結構可構成不同的鏈式存儲結構。
(1) 結點的類型及其定義
① 二叉鏈表結點。有三個域：一個數據域，兩個分別指向左右子結點的指針域
typedef struct BTNode
{ ElemType data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ; ② 三叉鏈表結點。除二叉鏈表的三個域外，再增加一個指針域，用來指向結點的父結點
typedef struct BTNode_3
{ ElemType data ;
struct BTNode_3 *Lchild , *Rchild , *parent ;
}BTNode_3 ; 遍歷二叉樹(Traversing Binary Tree)：是指按指定的次序（規律）依次訪問二叉樹中所有結點，使得每個結點被訪問一次且僅被訪問一次。
訪問：指對結點做某種處理。如：輸出信息、修改結點的值等。
次序（規律）：二叉樹是一種非線性結構，每個結點都可能有左、右兩棵子樹，所以在訪問完一個結點之後，下一個被訪問的結點面臨著不同的選擇。因此，需要尋找一種次序（規律），使二叉樹上的結點能排列在一個線性隊列上，從而便於遍歷。
二叉樹的基本組成：根結點、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。
若以L、D、R分別表示遍歷左子樹、遍歷根結點和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。 若規定先左後右，則只有前三種情況三種情況，分別是：
DLR——先(根)序遍歷。
LDR——中(根)序遍歷。
LRD——後(根)序遍歷。
已知二叉樹，寫出先序序列、中序序列、後序序列
已知先序序列和中序序列，確定二叉樹
已知後序序列和中序序列，確定二叉樹
對於二叉樹的遍歷，分別討論遞歸遍歷算法和非遞歸遍歷算法。
遞歸遍歷算法具有非常清晰的結構，但初學者往往難以接受或懷疑，不敢使用。實際上，遞歸算法是由系統通過使用堆棧來實現控制的。
非遞歸算法中的控制是由設計者定義和使用堆棧來實現的。
1 遞歸算法
算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
⑴ 訪問根結點；
⑵ 先序遍歷左子樹(遞歸調用本算法)；
⑶ 先序遍歷右子樹(遞歸調用本算法)。
先序遍歷的遞歸算法
void PreorderTraverse(BTNode *T)
{ if (T==NULL)
return;
visit(T->data) ; /* 訪問根結點 */
PreorderTraverse(T->Lchild) ; //再先序遍歷左子樹
PreorderTraverse(T->Rchild) ; //再先序遍歷右子樹
}
說明：1、visit()函數是訪問結點的數據域，其要求視具體問題而定,可以是最簡單的打印輸出。
2、樹采用二叉鏈表的存儲結構，用指針變量T來指向。
2 非遞歸算法
設T是指向二叉樹根結點的指針變量，非遞歸算法是：
若二叉樹為空，則返回；否則，令p=T；
⑴ 訪問p所指向的結點；
⑵ q=p->Rchild ，若q不為空，則q進棧；
⑶ p=p->Lchild ，若p不為空，轉(1)，否則轉(4)；
⑷ 退棧到p ，轉(1)，直到棧空為止。
算法實現：
#define MAX_STACK_SIZE 50
void PreorderTraverse( BTNode *T)
{ BTNode *Stack[MAX_STACK_SIZE ] ,*p=T, *q ;
int top=0 ;
if (T==NULL) printf(“ Binary Tree is Empty!\n”) ;
else { do
{ visit( p-> data ) ; q=p->Rchild ;
if ( q!=NULL ) stack[top++]=q ;
p=p->Lchild ;
if (p==NULL&& top!=0)
{top-- ；p=stack[top] ; }
}
while (p!=NULL) ;
}
}
