1.数据类型定义
在代码中为了清楚的表示一些错误和函数运行状态，我们预先定义一些变量来表示这些状态。在head.h头文件中有如下定义：
//定义数据结构中要用到的一些变量和类型 #ifndef HEAD_H #define HEAD_H #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <math.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //分配内存出错 typedef int Status; //函数返回值类型 typedef int ElemType; //用户定义的数据类型 #endif2.非递归过程中需要用到栈
LinkStack.h代码如下:
#ifndef LINKSTACK_H
#define LINKSTACK_H
#include "head.h"
//可用栈类型Stack的相关定义：
typedef struct SElemType {
pBiNode root; //二叉树结点的指针类型
int tag; // 0..1
}SElemType,*pType; //栈的元素类型
typedef SElemType Type;
typedef struct Node{
Type data;
struct Node* next;
}Node,*pNode;
typedef struct Stack{
pNode base;
pNode top;
int length;
}Stack,*pStack;
//初始化栈
Status InitStack(pStack &S){
S=(pStack)malloc(sizeof(Stack));
if(!S) return OVERFLOW;
S->length=0;
S->base=(pNode)malloc(sizeof(Node));
if(!S->base) return OVERFLOW;
S->top=(pNode)malloc(sizeof(Node));
if(!S->top) return OVERFLOW;
S->top->next=S->base;
return OK;
}
Status freeStack(pStack &S){
free(S);
S=NULL;
return OK;
}
//清空栈
Status ClearStack(pStack &S){
if(S==NULL) return ERROR;
pNode p=S->top;
while(p->next!=S->base){
pNode q=p;
p=p->next;
free(q);
q=NULL;
}
S->top=p;
S->length=0;
return OK;
}
//销毁栈
Status DestroyStack(pStack S){
if(S==NULL) return ERROR;
ClearStack(S);
free(S->base);
S->base=NULL;
free(S->top);
S->top=NULL;
freeStack(S);
S==NULL;
return OK;
}
//栈是否为空
Status StackEmpty(pStack S){
return S->length<=0;
}
//栈长度
int StackLength(pStack S){
return S->length;
}
//得到栈顶数据级e
Status GetTop(pStack S,Type *e){
*e=S->top->next->data;
return OK;
}
//入栈
Status Push(pStack &S,Type* e){
if(S->length==0){
S->base->data=*e;
}
else{
pNode p=S->top;
p->data=*e;
pNode q=(pNode)malloc(sizeof(Node));
q->next=p;
S->top=q;
}
S->length++;
return OK;
}
//出栈
Status Pop(pStack S,Type *e){
if (S->length<=0) return ERROR;
if(S->length==1){
*e=S->base->data;
S->length--;
}else{
pNode p=S->top;
S->top=p->next;
*e=S->top->data;
free(p);
S->length--;
}
return OK;
}
Status print(Type e){
printf("%d
",e);
return OK;
}
//用vistit遍历栈
Status StackTraverse(pStack S,Status(*visit)(Type)){
pNode p=S->top;
do
{
p=p->next;
(*visit)(p->data);
} while (p!=S->base);
return OK;
}
Status printStack(pStack S){
if (S==NULL ||S->length==0) return ERROR;
StackTraverse(S,print);
return OK;
}
#endif
3.二叉树头文件
BiTree.h代码如下:
#ifndef BITREE_H
#define BITREE_H
#include "head.h"
typedef struct BiNode{
ElemType data;
struct BiNode *left,*right;
}BiNode,*pBiNode;
Status InsertRight(pBiNode &root,ElemType e);
Status InsertLeft(pBiNode &root,ElemType e);
Status InitBiTree(pBiNode &tree){
tree=(pBiNode)malloc(sizeof(BiNode));
if(!tree) return OVERFLOW;
tree->data=-999999;
tree->left=NULL;
tree->right=NULL;
return OK;
}
Status BiTreeEmpty(pBiNode root){
if(root==NULL) return ERROR;
return root->left==root->right && root->data==-999999;
}
Status HasNoNode(pBiNode root){
if(root==NULL) return ERROR;
return root->left==root->right ;
}
Status CreatTreeNode(pBiNode &node,ElemType e){
node=(pBiNode)malloc(sizeof(BiNode));
if(!node) return OVERFLOW;
node->data=e;
node->left=NULL;
node->right=NULL;
return OK;
}
Status InsertRight(pBiNode &root,ElemType e){
if(root->right==NULL){
if(e>root->data){
pBiNode p;
CreatTreeNode(p,e);
root->right=p;
return OK;
}else{
pBiNode p;
CreatTreeNode(p,e);
root->left=p;
return OK;
}
}else{
e>root->data? InsertRight(root->right,e):InsertLeft(root,e);
}
}
Status InsertLeft(pBiNode &root,ElemType e){
if(root->left==NULL){
if(e>root->data){
pBiNode p;
CreatTreeNode(p,e);
root->right=p;
return OK;
}else{
pBiNode p;
CreatTreeNode(p,e);
root->left=p;
return OK;
}
}else{
e<=root->data?InsertLeft(root->left,e):InsertRight(root,e);
}
}
Status InsertTree(pBiNode &root,ElemType e){
if(BiTreeEmpty(root)){
root->data=e;
return true;
}
if(e>root->data){
InsertRight(root,e);
}else{
InsertLeft(root,e);
}
}
Status CreateBiTree(pBiNode &root,ElemType *a,int n){
for (int i=0;i<n;i++)
{
InsertTree(root,a[i]);
}
return true;
}
Status print(ElemType e ){
printf("%d ",e);
return true;
}
Status PreOrderTraverse(pBiNode root,Status(*p)(int)){
if(root){
(*p)(root->data);
PreOrderTraverse(root->left,p);
PreOrderTraverse(root->right,p);
}
return OK;
}
Status MiddleOrderTraverse(pBiNode root,Status(*p)(int)){
if(root){
MiddleOrderTraverse(root->left,p);
(*p)(root->data);
MiddleOrderTraverse(root->right,p);
}
return OK;
}
Status AfterOrderTraverse(pBiNode root,Status(*p)(int)){
if(root){
AfterOrderTraverse(root->left,p);
AfterOrderTraverse(root->right,p);
(*p)(root->data);
}
return OK;
}
Status ClearBiTree(pBiNode &root){
if(root){
ClearBiTree(root->left);
ClearBiTree(root->right);
free(root);
root==NULL;
}
return OK;
}
#endif
4.测试代码
#include "BiTree.h"
#include "LinkStack.h"
//非北递归后序
void PostOrder(pBiNode root){
pStack s;
InitStack(s);
pType p,t;
p=(pType)malloc(sizeof(SElemType));
t=(pType)malloc(sizeof(SElemType));
p->root=root;
while(p->root ||!StackEmpty(s))
{
while(p->root)
{
p->tag= 0;
Push(s,p);
//printf("%d ",p->root->data);
p->root=p->root->left;
}
GetTop(s,t);
while(t->tag && !StackEmpty(s))
{
Pop(s,p);
printf("%d ",p->root->data);
GetTop(s,t);
}
if(!StackEmpty(s)){
GetTop(s,t);
t->tag=1;
Pop(s,p);
Push(s,t);
GetTop(s,p);
p->root=p->root->right;
}else{
break;
}
}
}
void main(){
ElemType a[14]={100,50,200,40,30,45,60,55,61,200,150,300,250,400};
pBiNode root;
InitBiTree(root);
CreateBiTree(root,a,14);
printf("前序：");
PreOrderTraverse(root,print);
printf("
中序：");
MiddleOrderTraverse(root,print);
printf("
后序：");
AfterOrderTraverse(root,print);
printf("
非递归后序：");
PostOrder(root);
printf("
");
ClearBiTree(root);
}
插入的二叉树为:
