//////////////////////////////////////////// //二叉树的遍历算法 递归算法 // //Author:Wang Yong // //Date: 2010.8.19 // //////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> typedef char ElemType; /////////////////////////////////////////// //定义树的结点类型 typedef struct BNode { ElemType data; struct BNode *lchild,*rchild; }; /////////////////////////////////////////// //二叉树的创建 BNode *CreatBitTree() { BNode *p; char c; scanf("%c",&c); if(c == '#') p = NULL; //截止二叉树的建立 else { p = (BNode *) malloc(sizeof(BNode)); //申请结点空间 p->data = c; p->lchild = CreatBitTree(); p->rchild = CreatBitTree(); } return p; } //////////////////////////////////////////// //二叉树的先序遍历 void PreOrderTraverse(BNode *p) { if(p != NULL) { printf("%c*",p->data); PreOrderTraverse(p->lchild); PreOrderTraverse(p->rchild); } } ///////////////////////////////////////////// //二叉树的中序遍历 void InOrderTraverse(BNode *p) { if(p != NULL) { InOrderTraverse(p->lchild); printf("%c*",p->data); InOrderTraverse(p->rchild); } } ////////////////////////////////////////////// //二叉树的后序遍历 void PostOrderTraverse(BNode *p) { if(p != NULL) { PostOrderTraverse(p->lchild); PostOrderTraverse(p->rchild); printf("%c*",p->data); } } ///////////////////////////////////////////// int main() { BNode *tree; tree = CreatBitTree(); PreOrderTraverse(tree); printf("\n"); InOrderTraverse(tree); printf("\n"); PostOrderTraverse(tree); printf("\n"); return 0; }