[数据结构][二叉链表]二叉树链式存储结构的二叉链表实现

二叉链表的链式数据结构为：

typedef struct BTreeNode
{
DataType data;
struct BTreeNode * lchild;
struct BTreeNode * rchild;
}*BTree,BTreeNode;

在对二叉树进行非递归遍历的时候需要用到栈来保存结点或者删除结点操作，以便可以进行顺序打印。这里没有用到栈，而是用了和栈存储结构类似的数组来模拟。

下面以下面的一颗二叉树为例，对其进行基本的操作：

1，先序序列：-+a*b-cd/ef

2，中序序列：a+b*c-d-e/f

3，后序序列：abcd-*+ef/-

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define OK 1
#define ERROR -1
typedef char DataType;
typedef int Status;
typedef struct BTreeNode
{
DataType data;
struct BTreeNode * lchild;
struct BTreeNode * rchild;
}*BTree,BTreeNode;

//创建二叉树
Status CreateTree(BTree &bt)
{
char c ;

 scanf("%c",&c);
getchar();
//当输入的是#表示结点为空
if(c == '#') 
bt = NULL;
else
{
bt = (BTreeNode*)malloc(sizeof(BTreeNode)); //给新的结点开辟空间
if(!bt)
exit(0);

bt->data = c;//将输入的值作为结点值，第一次输入为根结点
CreateTree(bt->lchild);//递归调用，将左节点作为新树的"根结点"重新进行创建子树
CreateTree(bt->rchild);//递归调用，将右节点作为新树的"根结点"重新进行创建子树
}

return OK;
}

Status visit(DataType e)
{
printf("%c",e);
return OK;
}
//先序遍历二叉树
Status PreOrderTraverse(BTree bt,Status (*visit)(DataType e))
{
if(bt)
{
if(visit(bt->data))
{
if(PreOrderTraverse(bt->lchild,visit))
{
if(PreOrderTraverse(bt->rchild,visit))
return OK;
}
}
}
return ERROR;
}

//中序遍历二叉树
Status InOrderTraverse(BTree bt,Status (*visit)(DataType e))
{
if(bt)
{
if(InOrderTraverse(bt->lchild,visit))
{
if(visit(bt->data))
{
if(InOrderTraverse(bt->rchild,visit))
return OK;
}
}
}
return ERROR;
}

//后序遍历二叉树
Status PostOrderTraverse(BTree bt,Status (*visit)(DataType e))
{
if(bt)
{
if(PostOrderTraverse(bt->lchild,visit))
{
if(PostOrderTraverse(bt->rchild,visit))
{
if(visit(bt->data))
return OK;
}
}
}
return ERROR;
}

//层次遍历二叉树
Status LevelOrderTraverse(BTree bt,Status (*visit)(DataType e))
{
BTree b[100];
int front=0,rear=1;

b[0] = bt;
while(front < rear)
{
if(b[front])
{
visit(b[front]->data);
b[rear++] = b[front]->lchild;
b[rear++] = b[front]->rchild;
front++;
}
else{
front++;
}
}

return OK;
}

//非递归先序遍历
Status PreOderTraverseWithNoRecursion(BTree bt,Status (*visit)(DataType e))
{
BTree p,stack[100];
int top = 0;
p = bt;
if(bt != NULL)
{
top = 1;
stack[top] = p;

while(top > 0)
{
p = stack[top];
top--;
visit(p->data);

if(p->rchild != NULL)
{
top ++;
stack[top] = p->rchild;
}
if(p->lchild != NULL)
{
top++ ;
stack[top] = p->lchild;
}
}
}
return OK;
}

//非递归中序遍历
Status InOderTraverseWithNoRecursion(BTree bt,Status (*visit)(DataType e))
{
BTree p,stack[100];
int top = 0;
p = bt;

do{
while(p!=NULL)
{
top++;
stack[top] = p;
p = p->lchild;
}
if(top>0)
{
p = stack[top];
top--;
visit(p->data);
p=p->rchild;
}
}while(p!=NULL || top!=0);

return OK;
}

//非递归后遍历
Status PostOrderTraverseWithNoRecursion(BTree bt,Status (*visit)(DataType e))
{
BTree p,stack[100];
int top = -1;
int flag[100];
p = bt;

while(p !=NULL || top != -1)
{
while(p)
{
top++;
stack[top] = p;
flag[top] = 0;
p = p->lchild;
}

while(top>=0 && flag[top] == 1)
{
p = stack[top];
visit(p->data);
top--;
}

if(top>=0)
{
p = stack[top];
flag[top] =1;
p = p->rchild;
}
else
{
p = NULL;
}
}

return OK;
}


int main()
{

BTree bt;
printf("以先序顺序输入结点值:\n");
CreateTree(bt);
printf("\n先序递归调用\n");
PreOrderTraverse(bt,visit);
printf("\n中序递归调用\n");
InOrderTraverse(bt,visit);
printf("\n后序递归调用\n");
PostOrderTraverse(bt,visit);
printf("\n层次非递归调用\n");
LevelOrderTraverse(bt,visit);
printf("\n先序非递归调用\n");
PreOderTraverseWithNoRecursion(bt,visit);
printf("\n中序非递归调用\n");
InOderTraverseWithNoRecursion(bt,visit);
printf("\n后序非递归调用\n");
PostOrderTraverseWithNoRecursion(bt,visit);
printf("\n");
return 0;
}

运算结果