用C语言编写二叉树的建立与遍历.docVIP

用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亦称