2022年用c语言实现了二叉树的数据定义 .pdf

《2022年用c语言实现了二叉树的数据定义 .pdf》由会员分享，可在线阅读，更多相关《2022年用c语言实现了二叉树的数据定义 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、用 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(

2、);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*

3、T,int(*visit)(char elem);void InOrderTraverse(struct BiTNode*T,int(*visit)(char elem);void PostOrderTraverse(struct BiTNode*T,int(*visit)(char elem);名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -/stack.h 堆栈数据结构，用于非递归算法中的附加空间#define STACK_SIZE 256 struct stack struct BiTNode*elemSTACK_SIZE;int top;/top 总是指向栈顶元

4、素的上一个元素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 堆栈的实现#include#include#include stack.h/初始化堆栈为0，栈指针为0 void initStack(struct stack*s)memset(s-el

5、em,0,STACK_SIZE);s-top=s-bottom=0;/获取栈顶元素，栈顶指针不变struct BiTNode*getTop(struct stack*s)return s-elems-top-1;/弹出&返回栈顶元素struct BiTNode*pop(struct stack*s)if(s-top=s-bottom)/若栈空 printf(Stack is empty!n);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -s-top;return s-elems-top;/将 pB 指针压入栈中void push(struct sta

6、ck*s,struct BiTNode*pB)if(s-topelems-top=pB;+s-top;else printf(Stack is full!n);/判断栈是否为空，空返回非0 int isEmpty(struct stack*s)return s-top=s-bottom;/BiTree.c 二叉树创建、销毁、递归算法实现#include#include#include BiTree.h#include stack.h struct BiTNode*CreateBiTree()/采用先序递归方法创建一棵二叉树 struct BiTNode*T;char ch,tmp;printf

7、(please input the value of the node:n);scanf(%c,&ch);tmp=getchar();/忽略回车符if(ch=&)/输入&符号表示此节点为空 printf(Null BiTreeNode Created!n);T=NULL;return NULL;T=(struct BiTNode*)malloc(sizeof(BiTNode);/为当前节点分配内存名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -if(!T)printf(Allocate memory failed!n);return NULL;T-data=ch;/为当

8、前节点赋值T-lchild=CreateBiTree();/递归创建左子树T-rchild=CreateBiTree();/递归创建右子树return T;/销毁二叉树,销毁成功返回0，错误返回1 int DestroyBiTree(struct BiTNode*T)if(T)struct BiTNode*lchild=T-lchild;struct BiTNode*rchild=T-rchild;free(T);if(0=DestroyBiTree(lchild)if(0=DestroyBiTree(rchild)return 0;else return 1;return 0;/访问节点元素

9、int visit(char elem)if(elem=&)return 1;printf(%c,elem);return 0;/先序遍历递归算法,返回值为0 表示遍历成功，1 为失败int PreOrderTraverse_R(struct BiTNode*T,int(*visit)(char elem)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -if(T)if(0!=visit(T-data)/访问根节点return 1;if(T-lchild)if(0!=InOrderTraverse_R(T-lchild,visit)/递归遍历左子树return 1;if(

10、T-rchild)if(0!=InOrderTraverse_R(T-rchild,visit)/递归遍历右子树return 1;return 0;/中序遍历递归算法,返回值为0 表示遍历成功，1 为失败int InOrderTraverse_R(struct BiTNode*T,int(*visit)(char elem)if(T)if(T-lchild)if(0!=InOrderTraverse_R(T-lchild,visit)/递归遍历左子树return 1;if(0!=visit(T-data)/访问根节点return 1;if(T-rchild)if(0!=InOrderTrave

11、rse_R(T-rchild,visit)/递归遍历右子树return 1;return 0;/后序遍历递归算法,返回 0 表示遍历成功，1 为失败名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -int PostOrderTraverse_R(struct BiTNode*T,int(*visit)(char elem)if(T)if(T-lchild)if(0!=PostOrderTraverse_R(T-lchild,visit)/递归遍历左子树return 1;if(T-rchild)if(0!=PostOrderTraverse_R(T-rchild,visit

12、)/递归遍历右子树return 1;if(0!=visit(T-data)/访问根节点return 1;return 0;/先序遍历非递归算法void PreOrderTraverse(struct BiTNode*T,int(*visit)(char elem)struct stack ss;struct BiTNode*p=T;initStack(&ss);while(p|!isEmpty(&ss)if(p)visit(p-data);push(&ss,p);p=p-lchild;else p=getTop(&ss);pop(&ss);p=p-rchild;名师资料总结-精品资料欢迎下载-

13、名师精心整理-第 6 页，共 8 页 -/中序遍历非递归算法void InOrderTraverse(struct BiTNode*T,int(*visit)(char elem)struct stack ss;struct BiTNode*p;initStack(&ss);push(&ss,T);while(!isEmpty(&ss)while(p=getTop(&ss)push(&ss,p-lchild);/向左走到尽头p=pop(&ss);/空指针退栈if(!isEmpty(&ss)p=pop(&ss);visit(p-data);/访问节点push(&ss,p-rchild);/向右一

14、步 /后序遍历非递归算法void PostOrderTraverse(struct BiTNode*T,int(*visit)(char elem)struct stack ss;struct BiTNode*p=T;struct BiTNode*q;initStack(&ss);/初始化空栈while(p|!isEmpty(&ss)if(p)push(&ss,p);p=p-lchild;else p=getTop(&ss);if(p)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -push(&ss,NULL);p=p-rchild;else pop(&ss);q=po

15、p(&ss);visit(q-data);/main.c 测试主程序#include#include BiTree.h int main()struct BiTNode*bt=0;bt=CreateBiTree(bt);printf(先序遍历序列：n);PreOrderTraverse_R(bt,visit);printf(n 中序遍历序列：n);InOrderTraverse_R(bt,visit);printf(n 后序遍历序列：n);PostOrderTraverse_R(bt,visit);printf(n 非递归先序遍历序列：n);PreOrderTraverse(bt,visit);printf(n 非递归中序遍历序列：n);InOrderTraverse(bt,visit);printf(n 非递归后序遍历序列：n);PostOrderTraverse(bt,visit);DestroyBiTree(bt);return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -