二叉树的广义表创建及中序遍历、后序遍历、层次遍历的非递归算法（C语言）

徐建岗网络管理

2019-11-02

广义表创建二叉树
关于用广义表的形式表示二叉树的形式如下

①广义表中的一个字母代表一个结点的数据信息。
②每个根结点作为由子树构成的表的名字放在义表的前面。
③每个结点的左子树与右子树之间用逗号分开。若结点只有右子树面无左子树，则该逗号不能省略。
④在整个广义表的末尾加一个特殊符号(如“@”)作为结束标志。

下面先用自然语言描述算法如下。
依次从广义表中取得-个元素，并对取得的元素做如下相应的处理。

①若当前取得的元素为字母，则按如下规则建立一个新的(链)结点。
a)若该结点为二叉树的根结点，则将该结点的地址送T。
b)若该结点不是二叉树的根结点，则将该结点作为左孩子(若标志flag为1)或者右子若标志flag为2)链接到其双亲结点上(此时双亲结点的地址在栈顶位置)。

②若当前取得的元素为左括号“(”，则表明一个子表开始，将标志flag置为1，同时将面那个结点的地址进栈。

③若当前取得的元素为右括号“)”,则表明一个子表结束，做退栈操作。

④若当前取得的元素为逗号，则表明以左孩子为根的子树处理完毕,接着应该处理孩子为根的子树，将标志flag置为2。

如此处理广义表中的每一个元素，直到取得广义表的结束符号“@”为止。

二叉树的中序遍历（非递归）
算法的核心思想是:
当P所指的结点不为空时.则将该结点所在链结点的地址进栈，然后再将”指向该结点的左孩子结点:当P所指的结点为空时则从堆栈中退出栈项元素(某个结宜的地址)送p.并访问该结点，然后再将p指向该结点的右孩子结点。重复上述过程，直到P为NULL.并且堆栈也为空，遍历结束。

二叉树的后序遍历（非递归）
下面再讨论后序遍历的非递归算法：

在对二又树进行后序遍历的过程中，当指针p指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈;当其左子树遍历完毕之后，再次搜索到该结点时(该结点的地址通过退栈得到),还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈。只有当该结点的右子树被遍历后回到该结点，才访问该结点。为了标明某结点是否可以被访问，引人一个标志变量flag,
并有
1、flag=0表示该结点暂不访问
2、flag =1表示该结点可以访问
标志flag的值随同进栈结点的地址起进栈和出栈。因此，算法中设置了两个空间足够的堆栈，其中,STACK1[0… M- 1 ]存放进栈结点的地址,STACK2[0… M- 1]存放相应的标志flag的值，两个堆栈使用同一栈顶指针top,top的初值为一1。

二叉树的按层次遍历
下面测试的算法中使用了一个顺序存储结构队列QUEUE[0. . M- 1],(不妨假设队列的空间足够大).front与rear分别为队头指针和队尾指针。遍历进行之前先把二叉树根结点的存储地址进队.然后依次从队列中退出一个元素(结点的存储地址);每退出一个元素，先访问该元素所指的结点.然后依次把该结点的左孩子结点(若存在的话)与右孩子结点(若存在的话)的地址依次进队。如此重复下去，直到队列为空。此时，访问结点的次序就是按层次遍历该二叉树的次序。

有关中序遍历，后序遍历，层次遍历的非递归算法和二叉树的广义表创建一起测试

#include<stdio.h>
#include<stdlib.h>
#define M 100

typedef struct BTREE {
char data;
struct BTREE *lchild, *rchild;
}BT, *LBTREE;

LBTREE Creat()
{
LBTREE STACK[M], p = NULL, T = NULL;
int flag, top = -1;
char ch;
while (1)
{
scanf_s("%c", &ch);
switch (ch)
{
case ‘(‘:    //左括号则下一个读取字符入栈
STACK[++top] = p;
flag = 1;
break;
case ‘)‘:    //右括号则栈顶元素出栈
top--;
break;
case ‘,‘:
flag = 2;
break;
case ‘@‘:    //返回T，表示创建完毕
return T;
default:    //读到字母时
p = (LBTREE)malloc(sizeof(BT));
p->data = ch;
p->lchild = NULL;
p->rchild = NULL;
if (T == NULL)
T = p;
else if (flag == 1)
STACK[top]->lchild = p;
else if (flag == 2)
STACK[top]->rchild = p;
}
}
}

void INORDER(LBTREE T)    //中序遍历非递归
{
LBTREE STACK[M], p = T;
int top = -1;
if (T != NULL)
{
do {
while (p != NULL)    //这里不可以是 (p=p->lchild)!=NULL
{
STACK[++top] = p;
p = p->lchild;
}
p = STACK[top--];    //出栈
printf("%c", STACK[top + 1]->data);
p = p->rchild;
} while (!(p == NULL && top == -1));
}
}

void LAYERORDER(LBTREE T)    //按层次遍历
{
LBTREE QUEUE[M], p;
int front, rear;
if (T != NULL)    //队列
{
QUEUE[0] = T;
front = -1;
rear = 0;
while (front < rear)
{
p = QUEUE[++front];
printf("% c", p->data);
if (p->lchild != NULL)
QUEUE[++rear] = p->lchild;
if (p->rchild != NULL)
QUEUE[++rear] = p->rchild;

}
}
}

void POSTORED(LBTREE T)    //后序遍历的非递归算法
{
LBTREE STACK1[M];    //创建了两个栈，一个用来存放结点的地址
int STACK2[M], flag, top = -1;    //另一个用来存放数字，1：可以读取，0：不可读取
LBTREE p = T;
if (T != NULL)
{
do {
while (p != NULL)
{
STACK1[++top] = p;
STACK2[top] = 0;
p = p->lchild;
}
p = STACK1[top];
flag = STACK2[top--];
if (flag == 0)
{
STACK1[++top] = p;
STACK2[top] = 1;
p = p->rchild;
}
else
{
printf("%c", p->data);
p = NULL;
}
} while (!(p == NULL && top == -1));
}
}


void Distroyb(LBTREE T)    //销毁二叉树（同样使用递归的方式）
{
if (T != NULL)
{
Distroyb(T->lchild);
Distroyb(T->rchild);
free(T);
}
}


void main(void)
{
LBTREE T = NULL;
puts("输入二叉树数据");    
T=Creat(T);

puts("按层次遍历输出：");
LAYERORDER(T);
puts("");

puts("非递归中序遍历：");
INORDER(T);
puts("");

puts("非递归后续遍历：");
POSTORED(T);

Distroyb(T);    //销毁二叉树
}

输入:
A(B(D,E(G)),C(F(,H)))@
以下是结果：

二叉树的广义表创建及中序遍历、后序遍历、层次遍历的非递归算法（C语言）