问题分析：递归方法的创建二叉树，是基于系统栈的方式进行函数的调用，从而实现二叉树的创建。我们可以通过自己去构造栈的数据结构实现问题的解决。栈可以起到回溯的作用，使用先序遍历的插入，先一直往左子树插，当到了结束标志：本题中的 . 时开始回溯，往上一个的右子树插，同时可以在二叉链表中加入flag标记元素，方便代码对左右子树的判断。
要点：（1）灵活的运用栈的数据结构实现树内部的逻辑关系。（2）要设置特殊的二叉链表结构，多一个flag变量用来记录，如：flag=0左子树没有设置；flag=1左子树设置，右子树没有设置；flag=2出栈条件。（3）通常在没有重复结点的情况下，需要同时知道先序+中序，或者后序+中序才可以唯一确定一颗树（通过先序或后序确定根节点，通过中序判断左右子树），但是在本题中通过一个特殊的先序遍历，确定空结点的位置来确定唯一树。所以我们在定义一个树节点后，不要着急设置空树，根据 . 判断空树位置。
[问题描述]
任意给定一棵二叉树。试设计一个程序，在计算机中构造该二叉树，并对它进行遍历。要求：使用非递归算法的算法实现。
[输入]
一棵二叉树的结点若无子树，则可将其子树看作“.”，输入时，按照先序序列的顺序输入该结点的内容。对下图，其输入序列为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); }
结构演示：
