递归太墙大了。好好体会吧。路还很长。
头文件（VS下编译）：
/* 说明：该头文件中，包含了常用的、基本的定义，符号，宏定义，类型定义，常用的头文件等等， 所以其他cpp只需要加入这个头文件，然后再加一个自己类型的.h文件就OK了 */ #include "stdafx.h" #include<stdio.h> #include<malloc.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //函数返回值 //栈相关的宏： #define STACK_INIT_SIZE 100 // 栈的初始大小 #define STACK_INCREMENT 10 // 每次增加的空间大小 //
#include"Basic_Symbol.h"
//树的相关定义：
#define MAX_TREE_SIZE 100 //二叉树的最大节点数
typedef int TELemType;
typedef struct BiTNode //定义树的节点类型
{
TELemType data;
struct BiTNode *lchild,*rchild; //左右孩子指针
}TNode,*BiTree; //树的定义，每一个节点都是一棵树的意思吗？
typedef BiTree ElemType; //为树的节点类型
typedef struct
{
ElemType *base; //在构造栈之前和销毁之后，base的值为NULL
ElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}ZJC_Stack;
/*函数声明*/
Status InitStack(ZJC_Stack &S);
ElemType GetTop(ZJC_Stack S,ElemType &e);
Status Push(ZJC_Stack &S,ElemType e);
Status Pop(ZJC_Stack &S,ElemType &e);
Status StackEmpty(ZJC_Stack S);
Status CreatBiTree(BiTree &T,int sort);
Status PrintElement(TELemType e);
Status InOrderTraverse(BiTree T,Status(* Visit)(TELemType e));
Status PreOrderTraverse(BiTree T,Status(* Visit)(TELemType e)); //先序遍历
//栈的初始化
Status InitStack(ZJC_Stack &S)
{
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); //分配内存空间
if(!S.base)
exit(OVERFLOW);
else //否则分配成功
{
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
}
//获得栈顶元素
ElemType GetTop(ZJC_Stack S,ElemType &e)
{
if(S.top == S.base )
exit(ERROR);
return (e = *(S.top - 1));
}
//压栈
Status Push(ZJC_Stack &S,ElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.stacksize += STACK_INCREMENT;
S.top = S.base + S.stacksize;
}
*S.top++ = e;
return OK;
}
//出栈函数
Status Pop(ZJC_Stack &S,ElemType &e)
{
if(S.top == S.base ) //空栈，返回错误
return ERROR;
else //不是空栈
{
e = * --S.top;
return OK;
}
}
//判断栈是否为空
Status StackEmpty(ZJC_Stack S)
{
if( (S.base - S.top) != 0 ) //栈为空的条件事，两个指针地址相同
return FALSE; //不为空返回0
else return TRUE; //为空返回1
}
/*------------------------以下是树的基本操作--------------------*/
Status CreatBiTree(BiTree &T,int sort) //构造二叉链表表示的二叉树
{ //参数sort表示是标记，知道目前是建立根还是子树，0：根；1：左子树，2：右子树
TELemType c;
if(sort == 0)
printf("创建主根节点,请输入...");
else if(sort == 1)
printf("创建左根节点点,请输入...");
else if(sort == 2)
printf("创建右根节点点,请输入...");
scanf_s("%d",&c);
if(c == 0)
T = NULL;
else
{
if( !(T = (BiTNode*)malloc(sizeof(BiTNode))) )
exit(OVERFLOW);
T->data = c;
CreatBiTree(T->lchild,1);
CreatBiTree(T->rchild,2);
}
printf("\n树的构建完成....");
return OK;
}
Status PrintElement(TELemType e)
{
printf("\n被访问的元素为：%d",e);
return OK;
}
Status PreOrderTraverse(BiTree T,Status(* Visit)(TELemType e)) //先序遍历
{
printf("\n先序遍历 ：");
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
{
//printf("ddddddddddddd");
}
return OK;
return ERROR;
}
else
{
printf("\n子树（树）为空！");
return ERROR;
}
}
Status InOrderTraverse(BiTree T,Status(* Visit)(TELemType e)) //中序遍历，不仅仅是调一下if条件句的顺序喔！！想想为什么吧~
{
printf("\n中序遍历开始 ：");
BiTree p;
ZJC_Stack S;
InitStack(S);
Push(S,T);
while( !StackEmpty(S))
{
while( GetTop(S,p) && p)
Push(S,p->lchild);
Pop(S,p);
if( !StackEmpty(S) )
{
Pop(S,p);
if( !Visit(p->data))return ERROR;
Push(S,p->rchild);
}
}
printf("\n");
return OK;
}
//后序遍历二叉树
主测试程序：
#include"stdafx.h"
#include"Tree_Stack.h"
//入口测试函数
int _tmain(int argc, _TCHAR* argv[])
{
BiTree T;
CreatBiTree(T,0);
PreOrderTraverse(T,PrintElement); //先序遍历
InOrderTraverse(T,PrintElement); //中序遍历
}
测试函数：
#include"stdafx.h"
#include"Tree_Stack.h"
//入口测试函数
int _tmain(int argc, _TCHAR* argv[])
{
BiTree T;
CreatBiTree(T,0);
PreOrderTraverse(T,PrintElement); //先序遍历
InOrderTraverse(T,PrintElement); //中序遍历
}
算法基础（五）：二叉树（基础）,布布扣,bubuko.com
原文：http://blog.csdn.net/zjc_game_coder/article/details/20299881