还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
问题一二叉树遍历
1.问题描述设输入该二叉树的前序序列为ABC##DE#G##F##HI##J#K##(#代表空子树)请编程完成下列任务1请根据此输入来建立该二叉树,并输出该二叉树的前序、中序和后序序列;2按层次遍历的方法来输出该二叉树按层次遍历的序列;3求该二叉树的高度
2.设计描述
(1)二叉树是一种树形结构,遍历就是要让树中的所有节点被且仅被访问一次,即按一定规律排列成一个线性队列二叉(子)树是一种递归定义的结构,包含三个部分根结点(N)、左子树(L)、右子树(R)根据这三个部分的访问次序对二叉树的遍历进行分类,总共有6种遍历方案NLR、LNR、LRN、NRL、RNL和LNR研究二叉树的遍历就是研究这6种具体的遍历方案,显然根据简单的对称性,左子树和右子树的遍历可互换,即NLR与NRL、LNR与RNL、LRN与RLN,分别相类似,因而只需研究NLR、LNR和LRN三种即可,分别称为“先序遍历”、“中序遍历”和“后序遍历”采用递归方式就可以容易的实现二叉树的遍历,算法简单且直观
(2)此外,二叉树的层次遍历即按照二叉树的层次结构进行遍历,按照从上到下,同一层从左到右的次序访问各节点遍历算法可以利用队列来实现,开始时将整个树的根节点入队,然后每从队列中删除一个节点并输出该节点的值时,都将它的非空的左右子树入队,当队列结束时算法结束
(3)计算二叉树高度也是利用递归来实现若一颗二叉树为空,则它的深度为0,否则深度等于左右子树的最大深度加一3.源程序12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#includestdio.h#includestdlib.h#includemalloc.h#defineElemTypecharstructBTreeNode{ElemTypedata;structBTreeNode*left;structBT...。