用C语言编写二叉树的建立与遍历.doc_第1页
用C语言编写二叉树的建立与遍历.doc_第2页
用C语言编写二叉树的建立与遍历.doc_第3页
用C语言编写二叉树的建立与遍历.doc_第4页
用C语言编写二叉树的建立与遍历.doc_第5页
已阅读5页,还剩50页未读 继续免费阅读

VIP免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

用C语言编写二叉树的建立与遍历1对题目要有需求分析在需求分析中,将题目中要求的功能进行叙述分析,并且设计解决此问题的数据存储结构,设计或叙述解决此问题的算法。给出实现功能的一组或多组测试数据,程序调试后,将按照此测试数据进行测试的结果列出来。如果程序不能正常运行,写出实现此算法中遇到的问题和改进方法;2对题目要有相应的源程序源程序要按照写程序的规则来编写。要结构清晰,重点函数的重点变量,重点功能部分要加上清晰的程序注释。(注释量占总代码的四分之一)程序能够运行,要有基本的容错功能。尽量避免出现操作错误时出现死循环;3最后提供的主程序可以象一个应用系统一样有主窗口,通过主菜单和分级菜单调用课程设计中要求完成的各个功能模块,调用后可以返回到主菜单,继续选择其他功能进行其他功能的选择。二叉树的建立与遍历问题描述建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。基本要求从键盘接受输入,以二叉链表作为存储结构,建立二叉树,并对其进行遍历(先序、中序、后序),将遍历结果打印输出。以下是我的数据结构实验的作业:肯定好用,里面还包括了统计树的深度和叶子数!记住每次做完一个遍历还要重新输入你的树哦!#include stdio.h#include string.h#define NULL 0typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree Create(BiTree T)char ch;ch=getchar();if(ch=#)T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)printf(Error!);T-data=ch;T-lchild=Create(T-lchild);T-rchild=Create(T-rchild);return T;void Preorder(BiTree T)if(T)printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);int Sumleaf(BiTree T)int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)sum+;m=Sumleaf(T-lchild);sum+=m;n=Sumleaf(T-rchild);sum+=n;return sum;void zhongxu(BiTree T)if(T)zhongxu(T-lchild);printf(%c,T-data);zhongxu(T-rchild);void houxu(BiTree T)if(T)houxu(T-lchild);houxu(T-rchild);printf(%c,T-data);int Depth(BiTree T)int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);depr=Depth(T-rchild);dep=1+(depldepr?depl:depr);return dep;main()BiTree T;int sum,dep;T=Create(T);Preorder(T);printf(n);zhongxu(T);printf(n);houxu(T);printf(n);sum=Sumleaf(T);printf(%d,sum);dep=Depth(T);printf(n%d,dep);在Turbo C的环境下,先按Ctrl+F9运行程序,此时就是建立二叉树的过程,例如输入序列ABC#DE#G#F#(其中的“#”表示空,并且输入过程中不要加回车,因为回车也有对应的ASCII码,是要算字符的,但是输入完之后可以按回车退出),然后再按ALT+F5显示用户界面,这时候就能够看到结果了。另外你必须会手动建立一棵二叉树,保证你输入的序列能构成一棵二叉树,否则你怎么输入,按最后按多少回车程序也不会结束!下面是我举的例子的二叉树的图形表示(画的不好,别见笑),如果可能,把你想建立的二叉树也发上来!使用标准C语言编写创建有序二叉树的算法 最佳答案 #include#include#define NULL 0#define maxsize 100#define LEN sizeof(struct student)typedef struct studentstruct student *lchild,*rchild;char data; *STU;STU stree_creat(char *s,int k)STU p;if(sk=0|kmaxsize) return NULL;else p=(STU)malloc(LEN); p-data=sk; p-lchild=stree_creat(s,2*k+1); p-rchild=stree_creat(s,2*k+2); return p; void print(STU p) STU hmaxsize=NULL; int top=0,base=0; htop=p; printf(The chengci order:nn); while(hbase!=NULL) printf(%c,hbase-data); h+top=hbase-lchild; h+top=hbase-rchild; base+; printf(nSuccess.nn!);/*前序遍历*/void Preorder(STU p)if(p) printf(%c,p-data); Preorder(p-lchild); Preorder(p-rchild);/*中序遍历*/void Inorder(STU p)if(p) Inorder(p-lchild); printf(%c,p-data); Inorder(p-rchild);/*后序遍历*/void Postorder(STU p)if(p) Postorder(p-lchild); Postorder(p-rchild); printf(%c,p-data);/*交换该二叉树中所有结点左右孩子的非递归算法*/void conver(char a,int m)int i,j,h=1,k=2;char t;for(i=1;i=(int)(log(m+1)+1);i+) for(j=0;jpow(2,i-1);j+) t=ah+j;ah+j=ak-j;ak-j=t; h=2*h+1; k=2*k+2; main()STU root=NULL;int i=0,j=0,h=0;char amaxsize=0;clrscr();/*用一个数组存放一连串的字符串*/gets(a);while(a!=0)i+;/*建立二叉树*/root=stree_creat(a,0);printf(n);/*输出数组中的内容*/print(root);/*前序遍历*/printf(Preorder Traversal.n);Preorder(root);printf(n);/*中序遍历*/printf(nInorder Traversal.n);Inorder(root);printf(n);/*后序遍历*/printf(nPostorder Traversal.n);Postorder(root);追问F:1.c(26) : warning C4013: printf undefined; assuming extern returning intF:1.c(80) : warning C4013: clrscr undefined; assuming extern returning intF:1.c(82) : warning C4013: gets undefined; assuming extern returning int编译时没错,连接时有问题,是怎么回事啊?分享给你的朋友吧: i贴吧 新浪微博 腾讯微博 QQ空间 人人网 豆瓣 MSN 对我有帮助0回答时间:2011-6-7 17:46 | 我来评论 二叉树遍历及C语言实现 二叉树遍历及C语言实现已知中序和前序序列,或者已知中序和后序序列,都能够构造一棵二叉树。在本例中,本人用C语言写程序解答了下面两个算法题:(1)给出一棵二叉树的中序与后序遍历序列,求出它的先序遍历序列。(2)给出一棵二叉树的中序与先序遍历序列,求出它的后序遍历序列。知识点扼要回顾:所谓二叉树的遍历,是指按一定的顺序对二叉树中的每个结点均访问一次,且仅访问一。按照根结点访问位置的不同,通常把二叉树的遍历分为六种:TLR(根左右), TRL(根右左), LTR(左根右)RTL(右根左), LRT(左右根), RLT(右左根)其中,TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。前序遍历的规律是:输出根结点,输出左子树,输出右子树;中序遍历的规律是:输出左子树,输出根结点,输出右子树;后序遍历的规律是:输出左子树,输出右子树,输出根结点;不多说了,看代码吧:)1. #include2. #include3. 4. usingnamespacestd;5. 6. /存储节点数据,为简便起见,这里选用字符7. typedefcharDATA_TYPE;8. 9. typedefstructtagBINARY_TREE_NODEBINARY_TREE_NODE,*LPBINARY_TREE_NODE;10. 11. structtagBINARY_TREE_NODE12. 13. DATA_TYPEdata;/节点数据14. LPBINARY_TREE_NODEpLeftChild;/左孩子指针15. LPBINARY_TREE_NODEpRightChild;/右孩子指针16. ;17. 18. /19. /函数名称:TreeFromMidPost20. /函数功能:给出一棵二叉树的中序与后序序列,构造这棵二叉树。21. /输入参数:LPBINARY_TREE_NODE&lpNode:二叉树的结点22. /stringmid:存储了二叉树的中序序列的字符串23. /stringpost:存储了二叉树的后序序列的字符串24. /intlm,intrm:二叉树的中序序列在数组mid中的左右边界25. /intlp,intrp:二叉树的后序序列在数组post中的左右边界26. /27. voidTreeFromMidPost(LPBINARY_TREE_NODE&lpNode,stringmid,stringpost,intlm,intrm,intlp,intrp)28. 29. /构造二叉树结点30. lpNode=newBINARY_TREE_NODE;31. lpNode-data=postrp;32. lpNode-pLeftChild=NULL;33. lpNode-pRightChild=NULL;34. 35. intpos=lm;36. 37. while(midpos!=postrp)38. 39. pos+;40. 41. intiLeftChildLen=pos-lm;42. 43. if(poslm)/有左孩子,递归构造左子树44. 45. TreeFromMidPost(lpNode-pLeftChild,mid,post,lm,pos-1,lp,lp+iLeftChildLen-1);46. 47. 48. if(pospRightChild,mid,post,pos+1,rm,lp+iLeftChildLen,rp-1);51. 52. 53. 54. /55. /函数名称:TreeFromMidPre56. /函数功能:给出一棵二叉树的先序与中序序列,构造这棵二叉树。57. /输入参数:BINARY_TREE_NODE&lpNode:二叉树的结点58. /stringmid:存储了二叉树的中序序列的字符串59. /stringpre:存储了二叉树的先序序列的字符串60. /intlm,intrm:二叉树的中序序列在数组mid中的左右边界61. /intlp,intrp:二叉树的先序序列在数组pre中的左右边界62. /63. voidTreeFromMidPre(LPBINARY_TREE_NODE&lpNode,stringmid,stringpre,intlm,intrm,intlp,intrp)64. 65. /构造二叉树结点66. lpNode=newBINARY_TREE_NODE;67. lpNode-data=prelp;68. lpNode-pLeftChild=NULL;69. lpNode-pRightChild=NULL;70. 71. intpos=lm;72. 73. while(midpos!=prelp)74. 75. pos+;76. 77. intiLeftChildLen=pos-lm;78. 79. if(poslm)/有左孩子,递归构造左子树80. 81. TreeFromMidPre(lpNode-pLeftChild,mid,pre,lm,pos-1,lp+1,lp+iLeftChildLen);82. 83. 84. if(pospRightChild,mid,pre,pos+1,rm,lp+iLeftChildLen+1,rp);87. 88. 89. 90. /先序遍历91. voidPreOrder(LPBINARY_TREE_NODEp)92. 93. if(p!=NULL)94. 95. coutdata;/输出该结点96. PreOrder(p-pLeftChild);/遍历左子树97. PreOrder(p-pRightChild);/遍历右子树98. 99. 100. 101. /中序遍历102. voidMidOrder(LPBINARY_TREE_NODEp)103. 104. if(p!=NULL)105. 106. MidOrder(p-pLeftChild);/遍历左子树107. coutdata;/输出该结点108. MidOrder(p-pRightChild);/遍历右子树109. 110. 111. 112. /后序遍历113. voidPostOrder(LPBINARY_TREE_NODEp)114. 115. if(p!=NULL)116. 117. PostOrder(p-pLeftChild);/遍历左子树118. PostOrder(p-pRightChild);/遍历右子树119. coutdata;/输出该结点120. 121. 122. 123. /释放二叉树124. voidRelease(LPBINARY_TREE_NODElpNode)125. 126. if(lpNode!=NULL)127. 128. Release(lpNode-pLeftChild);129. Release(lpNode-pRightChild);130. deletelpNode;131. lpNode=NULL;132. 133. 134. 135. 136. intmain(intargc,char*argv)137. 138. stringpre;/存储先序序列139. stringmid;/存储中序序列140. stringpost;/存储后序序列141. 142. LPBINARY_TREE_NODElpRoot;/二叉树根节点指针143. 144. 145. cout程序已知二叉树的中序与后序序列,求先序序列endl;146. cout请先输入中序序列,回车后输入后序序列:mid;149. cinpost;150. 151. TreeFromMidPost(lpRoot,mid,post,0,mid.size()-1,0,post.size()-1);152. cout先序遍历结果:;153. PreOrder(lpRoot);154. coutendl;155. 156. cout中序遍历结果:;157. MidOrder(lpRoot);158. coutendl;159. 160. cout后序遍历结果:;161. PostOrder(lpRoot);162. coutendl;163. Release(lpRoot);164. coutendl;165. 166. cout程序已知二叉树的中序与先序序列,求后序序列endl;167. cout请先输入先序序列,回车后输入中序序列:pre;169. cinmid;170. 171. TreeFromMidPre(lpRoot,mid,pre,0,mid.size()-1,0,pre.size()-1);172. cout先序遍历结果:;173. PreOrder(lpRoot);174. coutendl;175. 176. cout中序遍历结果:;177. MidOrder(lpRoot);178. coutendl;179. 180. cout后序遍历结果:;181. PostOrder(lpRoot);182. coutendl;183. Release(lpRoot);184. coutendl;185. 186. 187. system(pause);188. return0;189. (1)程序1的输入方式:已知二叉树的中序与后序序列,求先序序列,请先输入中序序列,回车后输入后序序列:例如输入:DGBAECHFGDBEHFCA输出:先序遍历结果:ABDGCEFH中序遍历结果:DGBAECHF后序遍历结果:GDBEHFCA(2)程序2的输入方式:已知二叉树的先序与中序序列,求后序序列,请先输入先序序列,回车后输入中序序列:例如输入:abdefgcdebgfac输出:先序遍历结果:abdefgc中序遍历结果:debgfac后序遍历结果:edgfbca最后请看该程序运行效果图:这是程序1所确定的二叉树图:这是程序2所确定的二叉树图:二叉树非递归遍历题目是1)问题描述:在主程序中提供下列菜单: 1建立树 2前序遍历树 3中序(非递归)遍历树 4后序遍历树 0结束2)实验要求:定义下列过程: CreateTree(): 按从键盘输入的前序序列,创建树 PreOrderTree():前序遍历树(递归) InOrderTree():中序(非递归)遍历树 LaOrderTree(): 后序遍历树(递归)我做得是:求帮忙改错 或者给我一个程序 求啊啊啊 要下课了 啊啊啊啊及时的话有追加啊啊啊啊#include #include #include #define MaxNode 100typedef int ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BTNode;void CreateTree(BTNode *&b,char *str)/建立一个二叉树 BTNode *St100; BTNode *p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=strj; while(ch!=0) switch(ch) case (:top+;Sttop=p;k=1;break; case ):top-;break; case ,:k=2;break; default:p=(BTNode *)malloc(sizeof(BTNode); p-data=ch; p-lchild=p-rchild=NULL; if(b=NULL) b=p; else switch(k) case 1:Sttop-lchild=p;break; case 2:Sttop-rchild=p;break; j+; ch=strj; void PreOrder(BTNode *b)/前序遍历 if(b!=NULL) printf(%c ,b-data); PreOrder(b-lchild); PreOrder(b-rchild); void InOrder(BTNode *b)/中序遍历 BTNode p,stackMaxNode; int top=0; if(b=NULL) return; p=*b; while(!(p = NULL & top = 0) while(p!=NULL) if(toplchild; if(topdata);p=p-rchild; void LaOrder(BTNode *b)/后序遍历 if(b!=NULL) LaOrder(b-lchild); LaOrder(b-rchild); printf(%c ,b-data); void main() int number; BTNode *b=NULL; cout 【1】创建树endlendl; cout 【2】先序遍历树endlendl; cout 【3】中序遍历树endlendl; cout 【4】后序遍历树endlendl; cout 【5】结束endlendlendl; cout请输入您的选择number; while(number!=5) if(number=1) char str100; printf(请输入:); scanf(%s,&str); CreateTree(b,str); printf(树创建成功!n); else if(number=2) if(b=NULL) printf(对不起,您还没有创建树!n); else PreOrder(b); printf(n); else if(number=3) if(b=NULL) printf(对不起,您还没有创建树!n); else InOrder(b); printf(n); else if(number=4) if(b=NULL) printf(对不起,您还没有创建树!n); else LaOrder(b); printf(n); printf(请输入您的选择:n); scanf(%d,&number); 2011-4-28 15:03 最佳答案 中序遍历有问题:改后如下void InOrder(BTNode *b)/中序遍历 BTNode *p,*stackMaxNode; int top=0; if(b=NULL) return; p=b; while(!(p = NULL & top = 0) while(p!=NULL) if(toplchild; if(topdata);p=p-rchild; 二叉树建立过程见下面是关于二叉树的遍历、查找、删除、更新数据的代码(递归算法):#include using namespace std;typedef int T;class bststruct NodeT data;Node* L;Node* R;Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp);Node* root;int num;public:bst():root(NULL),num(0)void clear(Node* t)if(t=NULL) return;clear(t-L);clear(t-R);delete t;bst()clear(root);void clear()clear(root);num = 0;root = NULL;bool empty()return root=NULL;int size()return num;T getRoot()if(empty() throw empty tree;return root-data;void travel(Node* tree)if(tree=NULL) return;travel(tree-L);cout data R);void travel()travel(root);cout L);int rh = height(tree-R);return 1+(lhrh?lh:rh);int height()return height(root);void insert(Node*& tree, const T& d)if(tree=NULL)tree = new Node(d);else if(ddata)insert(tree-L, d);elseinsert(tree-R, d);void insert(const T& d)insert(root, d);num+;Node*& find(Node*& tree, const T& d)if(tree=NULL) return tree;if(tree-data=d) return tree;if(ddata)return find(tree-L, d);elsereturn find(tree-R, d);bool find(const T& d)return find(root, d)!=NULL;bool erase(const T& d)Node*& pt = find(root, d);if(pt=NULL) return false;combine(pt-L, pt-R);Node* p = pt;pt = pt-R;delete p;num-;return true;void combine(Node* lc, Node*& rc)if(lc=NULL) return;if(rc=NULL) rc = lc;else combine(lc, rc-L);bool update(const T& od, const T& nd)Node* p = find(root, od);if(p=NULL) return false;erase(od);insert(nd);return true;int main()bst b;cout n;b.insert(n);if(cin.peek()=n) break;();for(;)cout od nd;if(od=-1&nd=-1) break;b.update(od, nd);();关于二叉树的遍历作者:曹忠明,华清远见嵌入式学院讲师。二叉树遍历就是沿某条搜索路径周游二叉树,对树中的每一个节点访问一次且仅访问一次。由于二叉树的递归性质,遍历算法也是递归的。二叉树的遍历有先序遍历、中序遍历和后序遍历。下面以(图一)中二叉树介绍一下这三种遍历。(图一) 二叉树1、先序遍历先序遍历的遍历规则是(中 前 后),中就是父节点,前就是左孩子,后是右孩子。既先访问当前节点,再访问左子树,最后访问右子树。这个过程是由根节点开始的一个递归的过程。以上面这个二叉树为例。他的遍历过程为:(1)ABC(2)A(BD)(CE)(3)A(B(DF)(C(EGH)算法实现为:PREORDER ( bitree *r)if ( r = =NULL)return ; /*空树返回*/printf ( %c ,r-data ); /*先访问当前节点*/PREORDER ( r-lchild ); /*再访问该节点的左子树*/PREORDER ( r-rchild ); /*最后访问该节点右子树*/2、中序遍历中序遍历的遍历规则是(前 中 后),既访先问左子树,再访问当前节点,最后访问右子树。他的遍历过程为:(1)BAC(2)(DB)A(CE)(3)(DF)B)A(C(GEH)算法实现为:INORDER ( bitree *r)if ( r = = NULL )return ; /*空树返回*/INORDER ( r-lchild ); /*先访问该节点的左子树*/printf ( %c ,r-data ); /*再访问当前节点*/INORDER ( r-rchild ); /*最后访问该节点右子树*/3、后序遍历中序遍历的遍历规则是(前 后 中),既先访问当前节点的左子树,在访问当前节点的右子树,最后访问当前节点。他的遍历过程为:(1)BCA(2)(DB)(EC)A(3)(FD)B)(GHE)C)A算法实现为:POSTORDER ( bitree *r)if ( r = = NULL )return ; /*空树返回*/POSTORDER ( r-lchild ); /*先访问该节点的左子树*/POSTORDER ( r-rchild ); /*再访问该节点右子树*/printf ( %c ,r-data ); /*最后访问当前节点*/由上面一个例子可以看出,这是一个递归的过程,由根节点开始,递归的对各自的孩子结点按规则遍历。“本文由华清远见/index.htm提供”来源:华清远见二叉树遍历2008-11-22 18:26遍历概念:所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。遍历方案:1遍历方案从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:(1)访问结点本身(N),(2)遍历该结点的左子树(L),(3)遍历该结点的右子树(R)。以上三种操作有六种执行次序:NLR、LNR、LRN、NRL、RNL、RLN。注意:前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。2三种遍历的命名根据访问结点操作发生位置命名: NLR:前序遍历(PreorderTraversal亦称

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论