二元树的走访资料结构.PDFVIP

二元樹的走訪 資料結構 鍾宜玲 二元樹的走訪 資料讀取一遍的結果有DLR, DRL, LDR, LRD, RDL及RLD 若限制節點的左子樹比右子樹先走訪：  DLR前序 (preorder) D  LDR中序(inorder)  LRD後序 (postorder) L R 恰與運算式的前序 (prefix) 、中序(infix) 及後序 (postfix) 互相對應。 運算式的二元樹表示法 + 前序: + - + A * B C D / E F - / 中序: A + B * C – D + E / F + D E F 後序: A B C * + D – E F / + A * B C 例 寫出下面二棵二元樹的前序、中序、後序走訪順序。 (1) A (2) + B C * E D E F / D A - G B C 解： (1)前 序: ABDEGCF (2)前 序: +*/A-BCDE 中序 : DBGEACF 中序 : A/B-C*D+E 後序 : DGEBFCA 後序 : ABC-/D*E+ 後序走訪函數POST( ) 若二元樹的節點定義如下： typedef struct tnode{ char data; struct tnode *left; struct tnode *right; } TNODE; 則後序法的函數post( ) 可製作如下： void post(TNODE *p) { if( p != NULL ) { post( p-left ); /*走訪左子樹*/ post( p-right ); /*走訪右子樹*/ printf (“%c”, p-data); /*走訪樹根節點*/ } } 二元樹走訪的中序及前序的程式。 中序 前序： void inorder(TNODE *p) void preorder(TNODE *p) { { if (p!=NULL) { if (p!=NULL){ printf(”%c”, p-