1 #include<stdio.h>
2 #include<conio.h>
3 #include<malloc.h>
4 typedef char datatype;
5 typedef struct node{
6 datatype data;
7 struct node *lchild,*rchild;
8 }bitree; //二叉链树数据结构定义
9 void Preorder(bitree *p) //先序遍历算法
10 {
11 bitree *Stack[100]; //用一个“栈数组”存放二叉树节点bitree指针,假定最多能盛放100个bitree节点
12 bitree *s=p; //s节点为当前节点
13 int top=-1;
14 while(top!=-1||s!=NULL)
{
while(s!=NULL)
{
16 if(top==99)
{ //栈满,上溢出提示
17 printf("overflow");
18 return;
19 }
20 else
{
21 top++; //当前节点入栈,并且访问(打印内容)
22 Stack[top]=s;
23 printf("%c",s->data);
24 s=s->lchild; //先序要求先访问左孩子,为空时跳出循环
25 }
26 }
27 s=Stack[top]; //s回到当前空左孩子的双亲节点
28 top--; //退栈
29 s=s->rchild; //遍历右孩子
30 }
31 }
32 bitree *CreatTree(){ //建立二叉链树的函数,从左到右,从上到下依次赋值,空值给‘@’,退出在结尾给‘@’
33 char ch;
34 bitree *Q[100]; //建立一个“队列数组”存放bitree指针节点
35 int front,rear;
36 bitree *root,*s; //root是根节点,s还是代表当前建立的节点
37 root=NULL; //头结点置空
38 front=1,rear=0;
39 while((ch=getchar())!='#') //定义输入‘#’符号表示停止输入节点元素,建立结束
40 {
41 s=NULL;
42 if(ch!='@'){ //定义输入‘@’符号表示输入的树节点为空
43 s=(bitree*)malloc(sizeof(bitree));
44 s->data=ch;
45 s->lchild=NULL;
46 s->rchild=NULL;
47 }
48 rear++; //当前节点建立完成后入队
49 Q[rear]=s;
50 if(rear==1)
51 root=s;
52 else{
53 if(s&&Q[front]){
54 if(rear%2==0) //左孩子节点编号为偶数
55 Q[front]->lchild=s;
56 else //右孩子节点编号为奇数
57 Q[front]->rchild=s;
58 }
59 if(rear%2==1) //双亲节点右孩子建立结束后,双亲节点出队,建立下一位紧邻的双亲节点的孩子
60 front++;
61 }
62 }
63 return root; //函数返回建立完成的二叉链树的根节点指针
64 }
65 int main()
66 {
67 bitree *root;
68 root=CreatTree();
69 Preorder(root);
70 return 0;
71 }