数据结构上机实验报告-二叉树.docx

《数据结构上机实验报告-二叉树.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构上机实验报告二叉树问题陈冠豪二O一O年5月26号 建立一棵二叉树，要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历。 实验目的实现代码:#ifndefTREE_H#defineTREE_H#include#include#include#include#includeusingnamespacestd;typedefintElemType;typedefstructtreeT{ElemTypekey;structtreeT*left;struc

2、ttreeT*right;}treeT,*pTreeT;staticvoidvisit(pTreeTroot){if(NULL!=root){printf("%d",root->key);}}staticpTreeTBT_MakeNode(ElemTypetarget){pTreeTpNode=(pTreeT)malloc(sizeof(treeT));assert(NULL!=pNode);pNode->key=target;pNode->left=NULL;pNode->right=NULL;returnpNode;}pTreeTBT_I

3、nsert(ElemTypetarget,pTreeT*ppTree){pTreeTNode;assert(NULL!=ppTree);Node=*ppTree;if(NULL==Node){return*ppTree=BT_MakeNode(target);}if(Node->key==target)//不允许出现相同的元素{returnNULL;}elseif(Node->key>target)//向左{returnBT_Insert(target,&Node->left);}else{returnBT_Insert(target,&Node

4、->right);}}voidBT_PreOrder(pTreeTroot){if(NULL!=root){visit(root);BT_PreOrder(root->left);BT_PreOrder(root->right);}}voidBT_PreOrderNoRec(pTreeTroot){stacks;while((NULL!=root)

5、

6、!s.empty()){if(NULL!=root){visit(root);s.push(root);root=root->left;}else{root=s.top();s.po

7、p();root=root->right;}}}voidBT_InOrder(pTreeTroot){if(NULL!=root){BT_InOrder(root->left);visit(root);BT_InOrder(root->right);}}voidBT_InOrderNoRec(pTreeTroot){stacks;while((NULL!=root)

8、

9、!s.empty()){if(NULL!=root){s.push(root);root=root->left;}else{root=s.top();visit(r

10、oot);s.pop();root=root->right;}}}voidBT_PostOrder(pTreeTroot){if(NULL!=root){BT_PostOrder(root->left);BT_PostOrder(root->right);visit(root);}}voidBT_PostOrderNoRec(pTreeTroot){}voidBT_LevelOrder(pTreeTroot){queueq;treeT*treePtr;assert(NULL!=root);q.push(root);while(!q

11、.empty()){treePtr=q.front();q.pop();visit(treePtr);if(NULL!=treePtr->left){q.push(treePtr->left);}if(NULL!=treePtr->right){q.push(treePtr->right);}}}#endif#include#include#include#defineMAX_CNT5#defineBASE100voidmain(intargc,char*argv[]){inti;charte

12、mp;pTreeTroot=NULL;srand((unsigned)time(NULL));printf("请输入元素：A.自动生