数据结构与算法 (二叉树)

《数据结构与算法 (二叉树)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（实验报告）姓名：吴衡学号：1061130127实验四二叉树的建立和遍历一、实验目的1、设计数据结构和算法，实现按层次构造二叉树的算法2、掌握树的前根序、中根序和后根序遍历算法二、实验内容1、实验题目按层次（从上到下，从左到右的顺序）输入树的结点，如果该结点为空，则用一个特定的值替代（比如0或者.）。例如下面的图中，输入为ebfad.g..c（当然为了方便输入，也可以用＃结束字符串的输入）要求构造一棵如下的二叉树，当二叉树构造成功后，需要对其进行先序遍历，后序遍历，中序遍历。实现代码：/

2、/Binary_tree.h#ifndefBINARY_TREE_H_#defineBINARY_TREE_H_#include#include#includeusingnamespacestd;structBinary_node{chardata;//datamembersBinary_node*left;Binary_node*right;};typedefstruct{inttag;Binary_node*t;}Elem;classBinary_t

3、ree{public:Binary_tree();//构造函数，里面将root=NULL;//通过队列中保存的数据，构造树voidbuildTree(void);//遍历二叉树voidpreorder(void);voidinorder(void);voidpostorder(void);private:Binary_node*root;//树根};#endif;//Binary_tree.cpp#include"Binary_tree.h"#includeusingnamespa

4、cestd;Binary_tree::Binary_tree(){}voidBinary_tree::buildTree(){charnodeData;charexp[]={'e','b','f','a','d','.','g','.','.','c','#'};queuetreeDataQueue;queuetreeNodeQueue;queuetreeFatherQueue;Binary_node*pTreeNode;Binary

5、_node*pfather;Binary_node*pLchild;Binary_node*pRchild;/*do{cin>>nodeData;if(nodeData!='#')treeDataQueue.push(nodeData);elsebreak;}while(1);*/inti=0;while(exp[i]!='#'){treeDataQueue.push(exp[i++]);}while(!treeDataQueue.empty()){nodeData=treeDataQueue.fro

6、nt();treeDataQueue.pop();if(nodeData!='.'){pTreeNode=newBinary_node();pTreeNode->data=nodeData;pTreeNode->left=NULL;pTreeNode->right=NULL;}elsepTreeNode=NULL;treeNodeQueue.push(pTreeNode);}pTreeNode=treeNodeQueue.front();treeNodeQueue.pop();root=pTreeNo

7、de;treeFatherQueue.push(pTreeNode);while(!treeNodeQueue.empty()){pfather=treeFatherQueue.front();treeFatherQueue.pop();pLchild=treeNodeQueue.front();treeNodeQueue.pop();if(pLchild!=NULL){pfather->left=pLchild;treeFatherQueue.push(pLchild);}if(!treeNodeQ

8、ueue.empty()){pRchild=treeNodeQueue.front();treeNodeQueue.pop();if(pRchild!=NULL){pfather->right=pRchild;treeFatherQueue.push(pRchild);}}}}voidBinary_tree::preorder(){stacks;Binary_node*c;if(root==NULL)return;s.push