1.定义头文件加结构体变量
2.创建一棵树
3.初始化栈
4.头插法入栈
5.判断栈是否为空
6.出栈操作
7.先序遍历
8.中序遍历
9.后序遍历
10.主函数调用
11.运行结果：
今天本篇文章将会讲解c语言二叉树的非递归算法并加附代码。
非递归其实就是非递归遍历，非递归运用了 栈 的思想，包括了先中后3种方式遍历，费话不多说，开整。
1.定义头文件加结构体变量
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct TreeNode
{
char data;
struct TreeNode* lchild;
struct TreeNode* rchild;
int flag;
}TreeNode;
typedef struct StackNode
{
TreeNode* data;
struct StackNode* next;
}StackNode;
注：这里定义的flag会在后序遍历中用到。（用来标记结点是否被访问过）
2.创建一棵树
void creatTree(TreeNode** T,int* index,char* data)
{
char ch;
ch = data[*index];
(*index)++;
if (ch == '#')
*T = NULL;
else
{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->data = ch;
(*T)->flag = 0;
creatTree(&((*T)->lchild), index, data);
creatTree(&((*T)->rchild), index, data);
}
}
注：此处不再详细解释，如果不懂可以参考本站另一篇文章http://t.csdn.cn/jX4cd
3.初始化栈
StackNode* initStack()
{
StackNode* s = (StackNode*)malloc(sizeof(StackNode));
s->data = NULL;
s->next = NULL;
return s;
}
注：把栈置为空（初始化）
4.头插法入栈
void headpush(TreeNode* data, StackNode* s)
{
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
node->data = data;
node->next = s->next;
s->next = node;
}
注：入栈（头插法），即对指针进行操作。
5.判断栈是否为空
int is_empty(StackNode* s)
{
if (s->next == NULL)
return 1;
else
return 0;
}
6.出栈操作
StackNode* pop(StackNode* s)
{
if (is_empty(s))
return NULL;
else
{
StackNode* node = s->next;
s->next = node->next;
return node;
}
}
注：出栈之前要先判断一下是否为空栈，不为空再进行出栈，因为出的是栈顶元素直接指针断开即可。
下面重点来了：非递归先序、中序，后序遍历。
7.先序遍历
void preOrder(TreeNode* t)
{
TreeNode* node = t;
StackNode* s = initStack();
while (node || !is_empty(s))
{
if (node) //判断node是否为空
{
printf("%c ", node->data);
headpush(node, s);
node = node->lchild;
}
else
{
node = pop(s)->data;
node = node->rchild;
}
}
}
注：先序遍历：根左右，先打印根 ，然后入栈，找根的左孩子，然后判断左孩子是否为空，两种情况：1为空：那就会进入else语句，出栈，找它的右孩子，再进行判断。2不为空：就先打印，再入栈，再找它的左孩子，从而再进行判断。一直往复循环，直到不满足while条件时遍历结束。
8.中序遍历
void inOrder(TreeNode* t)
{
TreeNode* node = t;
StackNode* s = initStack();
while (node || !is_empty(s))
{
if (node)
{
headpush(node, s);
node = node->lchild;
}
else
{
node = pop(s)->data;
printf("%c ", node->data);
node = node->rchild;
}
}
}
注：与先序遍历一样，就是打印语句转移到了else语句，基本思路一致。
9.后序遍历
StackNode* getTop(StackNode* s)
{
if (is_empty(s))
return NULL;
else
{
StackNode* node = s->next;
return node;
}
}
//先获取栈顶元素，因为不需要出栈，所以重新写了一个函数
void postOrder(TreeNode* t)
{
TreeNode* node = t;
StackNode* s = initStack();
while (node || !is_empty(s))
{
if (node)
{
headpush(node, s);
node = node->lchild;
}
else
{
TreeNode* top = getTop(s)->data;
if (top->rchild && top->rchild->flag == 0)
{
top = top->rchild;
headpush(top, s);
node = top->lchild;
}
else
{
top = pop(s)->data;
printf("%c ", top->data);
top->flag = 1;
}
}
}
}
注：所有遍历操作，基本上整体大的框架没有改变。
如果没有flag作为标记，会陷入死循环。
10.主函数调用
int main()
{
int index = 0;
TreeNode* t;
char data[100];
gets_s(data);
creatTree(&t, &index, data);
preOrder(t);
printf("\n");
inOrder(t);
printf("\n");
postOrder(t);
return 0;
}
11.运行结果：
ab##c##
a b c //先序
b a c //中序
b c a //后序
D:\VS\二叉树非递归\x64\Debug\二叉树非递归.exe (进程 12216)已退出，代码为 0。
————————————————
