用c语言实现了叉树的数据定义.docVIP

用c语言实现了二叉树的数据定义，二叉树的构建、销毁，以及先序、中序、后序的递归算法，非递归算法正在研究中。 /*--------------------------------------------------------------------------------------------*/ // 二叉树的二叉链表存储结构C语言实现。 // 实现了利用先序序列创建一棵二叉树，先序、中序、后序遍历算法的递归 // 和非递归算法。 // 版本： v1.0 // 环境：Visual C++ 6.0 // 作者： sunnyrain // 日期： 2007-8-24 /*--------------------------------------------------------------------------------------------*/ //BiTree.h struct BiTNode //采用二叉链表存储结构 { char data; struct BiTNode* lchild; struct BiTNode* rchild; }BiTNode; struct BiTNode* CreateBiTree(); int DestroyBiTree(struct BiTNode* T); int visit(char elem); //递归遍历算法 int PreOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem)); int InOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem)); int PostOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem)); //非递归遍历算法 void PreOrderTraverse(struct BiTNode* T, int (*visit)(char elem)); void InOrderTraverse(struct BiTNode* T, int (*visit)(char elem)); void PostOrderTraverse(struct BiTNode* T, int (*visit)(char elem)); //stack.h 堆栈数据结构，用于非递归算法中的附加空间 #define STACK_SIZE 256 struct stack { struct BiTNode* elem[STACK_SIZE]; int top; //top总是指向栈顶元素的上一个元素 int bottom; //恒0 }; void initStack(struct stack* s); struct BiTNode* getTop(struct stack* s); struct BiTNode* pop(struct stack* s); void push(struct stack* s,struct BiTNode* p); int isEmpty(struct stack* s); //stack.c 堆栈的实现 #includestdio.h #includestring.h #include stack.h //初始化堆栈为0，栈指针为0 void initStack(struct stack* s) { memset(s-elem,0,STACK_SIZE); s-top = s-bottom = 0; } //获取栈顶元素，栈顶指针不变 struct BiTNode* getTop(struct stack* s) { return s-elem[s-top-1]; } //弹出返回栈顶元素 struct BiTNode* pop(struct stack* s) { if(s-top == s-bottom) //若栈空 { printf(Stack is empty!\n); return 0; } --s-top; return s-elem[s-top]; } //将pB指针压入栈中 void push(struct sta