用二叉链表做为存储结构，先序遍历算法可描述为:

void InOrder(BinTree T)

{ //算法里①~⑥是为了说明执行过程加入的标号

① if(T) { // 如果二叉树非空

② printf("%c"，T->data); // 访问结点 ③ InOrder(T->lchild); ④ InOrder(T->rchild); ⑤ }

⑥ } // InOrder

void createBiTree(BiTree *bt){

char ch;

ch = getchar();

if(ch == '.')

*bt = NULL;

else{

*bt = (BiTree)malloc(sizeof(BiTNode));//向内存申请节点空间

(*bt)->data = ch;

createBiTree(&((*bt)->LChild));//生成左子树

createBiTree(&((*bt)->RChild));//生成右子树

}

}/*createBiTree*/

/*==================打印二叉树=============*/

void printTree(BiTree bt,int nLayer){

int i;

if(bt == NULL)

return ;

printTree(bt ->RChild,nLayer+1);

for(i=0;i<nLayer;i++)

printf(" ");

printf("%c\n",bt->data);

printTree(bt->LChild,nLayer+1);

}

图一:

(a)1 2 4 . . 6 . . 3 . 5 . 7 . 8 . .

(b)1 2 4 . . 5 . . 3 6 . . 7 . . 运行结果:

图二:

(a)7 3 1 . . 2 . . 9 . 10 . 8 . 4 . .

(b)7 3 1 . . 5 4 . . . 11 10 . . 15 . .

运行结果: