一、引言
二叉树是一种非常重要的非线性数据结构，在信号处理、移动通讯等应用中均有重要的应用。
在二叉树的应用中，首先要建立二叉树。本文针对二叉树的先序建立过程给出了详细的实现过程，包括非递归算法和递归算法两种不同的实现模式。所谓的先序法，就是按照先序遍历二叉树的流程创建二叉树。使用的二叉树数据如下图所示。本文给出了C语言版本的先序创建二叉树的非递归算法。
二、二叉树的创建-先序法
按照算法的具体实现细节，要求对原二叉树的结点进行补充空结点。具体补充结果下图所示，其中黄色结点是二叉树的结点，蓝色结点是扩充的结点，仅仅是为了算法实现方便实现而已。最终创建的二叉树还是如上图所示，遍历也是根据上图进行遍历。
1、算法的基本思路（有点复杂，可以参考后面的详细步骤理解）：
为了能够确定新读入的结点链接到当前结点（双亲）的左子树还是右子树，引入了链接标志flag，其初始值为假。flag值为真，则表示需将新读入的结点s插入当前结点（双亲）p的右子树，否则插入p的左子树。
具体步骤主要包括如下三步：
（1） 如果新读入的数据非空，当flag值为假时，将新读入的结点链接到当前结点（双亲）p的左子树，同时当前结点（双亲）p入栈（作为待插入的右子树的双亲结点），然后把新读入的结点作为当前结点（双亲）p。当flag值为真时，将新读入的结点链接到当前结点（双亲）p的右子树，并将flag置为假；
（2） 如果新读入的数据为空，且flag为真，则栈顶元素出栈；
（3） 如果新读入的数据为空，且flag为假，则继续读入数据，此时数据若非空，则建立新结点s，并链接到当前结点的右子树，同时将当前结点（双亲）p指向s；若为空数据，则栈顶结点出栈给p，同时flag值置为1，表示左子树已经处理完毕，再读入新结点则放到双亲的右子树。若栈为空，则结束二叉树的创建。
2、创建二叉树的详细步骤示例：
有图有真相。
按照图（2）所示，使用先序法创建二叉树，需要读入的数据依次为：
（1）读入a，二叉树、栈的状态、flag的值：
（2）读入b，二叉树、栈的状态、flag的值：
（3）读入d，二叉树、栈的状态、flag的值：
（4）读入一个？，二叉树、栈和flag值都没有发生改变
（5）再读入一个？，二叉树、栈的状态、flag的值：
（6）读入e，二叉树、栈的状态、flag的值：
（7）读入g，二叉树、栈的状态、flag的值：
（8）读入一个？，二叉树、栈和flag值都没有发生改变
（9）再读入一个？，二叉树没变，指针p位置变了，栈顶元素出栈
（10）再读入一个？，二叉树不变、栈顶元素出栈，flag值仍为1
（11）读入c，二叉树、栈的状态、flag的值：
（12）读入一个？，二叉树、栈和flag值都没有发生改变
（13）读入f，二叉树、栈的状态、flag的值：
（14）读入一个？，二叉树、栈和flag值都没有发生改变
（15）读入h，二叉树、栈的状态、flag的值：
（16）读入一个？，二叉树、栈和flag值都没有发生改变
（17）再读入一个？，由于此时栈已经为空，所以创建二叉树的过程结束。
三、创建二叉树的代码：
注：在只有创建二叉树的前提下检验创建结果是否正确，可以在创建的过程中增加打印结点与双亲之间关系的语句。
1）宏定义及结点存储结构
#include"stdio.h"
#include"malloc.h"
//根据结点数据的类型定义空数据为‘？’或者 0
#ifdef CHAR
#define NULLKEY '?'
#else
#define NULLKEY 0
#endif
//根据字符型数据或者整型数据定义结点数据类型
#ifdef CHAR
typedef char datatype;
#else
typedef int datatype;
#endif
#define MAX_NODE 100
//定义存储结点的结构体类型
typedef struct node
{
datatype data;
struct node *Lchild;
struct node *Rchild;
}BiTree;
2）创建二叉树的函数
/************************************************************************
//先序创建二叉树：非递归算法。
//输入参数：无
//返回值： 树根
//说明：1.所有的叶子结点、分支不完整的结点，都要进行扩充，扩充方式为：
字符型结点：扩充‘？’
整型结点： 扩充‘0’，也可根据实际情况调整
2.在输入数据时，应该按照扩充后的二叉树的先序遍历序列进行输入
3.示例
a b d ? ? e g ? ? ? c ? f ? h ? ?
1 2 4 0 0 5 3 0 0 0 6 0 7 0 8 0 0
************************************************************************/
BiTree *CreatBiTtreePreorder() {
BiTree *T, *s, *p, *stack[MAX_NODE];
datatype x;
int top = 0;
int flag = 0;
#ifdef CHAR
printf( "\n请输入字符，以 ? 作为每个节点的结束标志:" );
scanf( "%c",&x );
getchar();//过滤空格或者换行符
#else
printf( "\n请输入正整数以0作为结束标志:" );
scanf( "%d",&x );
#endif
//创建树根
if( x == NULLKEY ) {
T = NULL;
return T;
}
T = ( struct node * )malloc( sizeof(BiTree) );
T->data = x;
T->Lchild = NULL;
T->Rchild = NULL;
p = T;
while( 1 )
{
#ifdef CHAR
scanf( "%c",&x );
getchar();//过滤空格或者换行符
#else
scanf( "%d",&x );
#endif
//（1）如果新读入的数据非空
if( x != NULLKEY ) {
s = ( struct node * )malloc( sizeof(BiTree) );
s->data = x;
s->Lchild = NULL;
s->Rchild = NULL;
if( flag == 1 ) {//flag为真，则链接到右子树
p->Rchild = s;
flag = 0;
#ifdef CHAR
printf( " %c is %c \' R \n", x, p->data );
#else
printf( " %d is %d \' R \n", x, p->data );
#endif
}
else {//flag为假，则链接到左子树
p->Lchild = s;
stack[ top++ ] = p;//双亲压栈
#ifdef CHAR
printf( " %c is %c \' L \n", x, p->data );
#else
printf( " %d is %d \' L \n", x, p->data );
#endif
}
p = s;
}
//（2）如果新读入数据为空，且flag为真，则弹栈
else if( x == NULLKEY && flag == 1 ) {
if( top > 0 )
{
p = stack[ --top ];//弹栈
}
else
break;
}
//（3）如果新读入数据为空，且flag为假，则继续读入结点数据
else {
#ifdef CHAR
scanf( "%c",&x );
getchar();//过滤空格或者换行符
#else
scanf( "%d",&x );
#endif
//第一次读入数据为空，第二次非空，链接到右子树
if( x != NULLKEY ) {
s = ( struct node * )malloc( sizeof(BiTree) );
s->data = x;
s->Lchild = NULL;
s->Rchild = NULL;
p->Rchild = s;
#ifdef CHAR
printf( " %c is %c \' R \n", x, p->data );
#else
printf( " %d is %d \' R \n", x, p->data );
#endif
p = s;
}
//第一次读入数据为空，第二次为空，栈非空则弹栈，且flag置为真
else {
if( top > 0 )
{
p = stack[ --top ];
flag = 1;
}
else// 栈空则结束创建
break;
}
}
}
return( T );
}
3）主函数及运行结果
int main()
{
BiTree *bintree;
bintree = CreatBiTtreePreorder();
return 0;
}
