问题分析：递归方法的创建二叉树，是基于系统栈的方式进行函数的调用，从而实现二叉树的创建。我们可以通过自己去构造栈的数据结构实现问题的解决。

要点：（1）灵活的运用栈的数据结构实现树内部的逻辑关系。（2）要设置特殊的二叉链表结构，多一个flag变量用来记录，如：flag=0左子树没有设置；flag=1左子树设置，右子树没有设置；flag=2出栈条件。

[问题描述]

任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。要求：使用非递归算法的算法实现。

[输入]

一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照先序序列的顺序输入该结点的内容。对下图，其输入序列为ABD..EH...CF.I..G..，再输入数字K。

[输出]

  进行遍历后得到的序列

[存储结构]

采用二叉链表存储。

[算法的基本思想]

采用栈的存储结构实现非递归的方法先序序列创建二叉树，再使用队列的存储结构实现非递归的层次遍历

#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define MAXSIZE 10
typedef struct BTNode{
	char a;
	int flag; //flag=0左子树没有设置；flag=1左子树设置，右子树没有设置；flag=2出栈条件 
	struct BTNode *lchild;
	struct BTNode *rchild;
}BTNode, *node;

node createBTNode(node p){
	//创建二叉树，非递归算法 
	BTNode *stack[MAXSIZE];  //定义栈 
	int top = -1;  //初始化栈
	p = (node)malloc(sizeof(BTNode));  //创建根节点 
	char x;
	scanf("%c", &x);
	p->a = x;
	p->flag = 0;
	stack[++top] = p;  //根结点进栈 
	while(top != -1){
		char x;
		scanf("%c", &x);
		if(x == '.'){
			//“.”空结点的表示方式 
			if(stack[top]->flag == 0){
				stack[top]->flag = 1;
				stack[top]->lchild = NULL;
			}
			else if(stack[top]->flag == 1){
				stack[top]->flag = 2;
				stack[top]->rchild = NULL;
			}
		}
		else{
			node q = (node)malloc(sizeof(BTNode));
			q->a = x;
			q->flag = 0;
			if(stack[top]->flag == 0){
				//先插左子树 
				stack[top]->lchild = q;
				stack[top]->flag = 1;
				stack[++top] = q;
			}
			else if(stack[top]->flag == 1){
				//判断是否满足插入右子树的条件 
				stack[top]->rchild = q;
				stack[top]->flag = 2;
				stack[++top] = q;
			}
		}
		while(stack[top]->flag == 2){
			//判断是否满足出栈条件，满足则连续出栈 
			top--;
		}
	}
	return p;
}

void showBTNode(node p){
	//使用非递归，层次遍历进行实现
	BTNode *queue[MAXSIZE];
	int front = 0;
	int rear = 0;
	queue[rear++] = p; //根结点入队 
	while(front != rear){
		if(queue[front]->lchild != NULL){
			queue[rear++] = queue[front]->lchild;
		}
		if(queue[front]->rchild != NULL){
			queue[rear++] = queue[front]->rchild;
		}
		printf("%c", queue[front]->a);
		front++;
	}
} 

int main(){
	node p = createBTNode(p);
	printf("层次遍历结果为："); 
	showBTNode(p);
}

 结构演示：