树的应用算法与数据结构

《算法与数据结构》实验报告（一）实验题目：树的应用1、实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。2、实验内容:二叉树后序遍历的非递归算法。3、实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。设根指针为root，则可能有以下两种情况：⑴若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。二叉树后序遍历的非递归算法伪代码如下：设计分析在后序遍历中，在输出一个结点之前，要两次经历该结点。第一次是从该结点出发沿其左孩子指针遍历其左子树，第二次是沿其右孩子指针遍历其右子树。只有右子树遍历完成之后，才能访问该结点。因此，一个结点要分两次进栈，只有第二次出栈时，才能访问该结点。也就是说，在后序遍历中要区分是从左子树返回还是从右子树返回，在结点入栈时，必须同时压入一个标记，用该标记指明返回的情况。所以基本思路1.从根开始，不断将左子树指针压栈，直到指针为空为止；1第一次出栈，只遍历完左子树，该结点不能访问2第二次出栈，遍历完右子树，该结点可以访问flag＝1.栈s初始化；2.循环直到root为空且栈s为空2.1当root非空时循环2.1.1将root连同标志flag=1入栈；2.1.2继续遍历root的左子树；2.2当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;2.3若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；2.看栈顶元素如果它没有右孩子，或者它的右孩子刚被访问过，访问该结点，弹栈；转到2；否则它的右孩子不空且未被访问过，则必须将它的右孩子继续压栈；转到1；3.栈空，则结束。源程序代码#includeiostream.htypedefstructnode{chardata;structnode*lchild,*rchild;}BiTreeNode;classBiTree{public:voidCreatBtree(BiTreeNode*&root,char*str)//创建树定义根节点指针{BiTreeNode*st[100],*p=NULL;inttop=-1,k=0,j=0;chart;root=NULL;t=str[j];while(t!=NULL){switch(t){case'(':{top++;st[top]=p;k=1;break;}case')':{top--;break;}case',':{k=2;break;}default:{p=newBiTreeNode;p-data=t;p-lchild=p-rchild=NULL;}if(root==NULL)root=p;else{switch(k){case1:{st[top]-lchild=p;break;}case2:{st[top]-rchild=p;break;}}}}j++;t=str[j];}}voidPostOrder(node*pnode){inttop=0;node*p;structstacknode{node*d;charflag;};stacknode*s;s=newstacknode[100];p=pnode;while(p!=NULL||top!=0){if(p!=NULL){top++;s[top].d=p;s[top].flag=1;p=p-lchild;}elseif(s[top].flag){s[top].flag=0;p=s[top].d-rchild;}else{p=s[top].d;top--;coutp-dataendl;p=NULL;}}delete[]s;}};voidmain(){BiTreeNode*ss;intt=0;charp[100];cout***********后序遍历二叉树********endl;cout输入存放的树节点：;do{cinp;}while(t);BiTreea;a.CreatBtree(ss,p);cout后序遍历序列为:endl;a.PostOrder(ss);}测试用例实验总结后序遍历的非递归算法比其他两种遍历要复杂一些，在先序遍历中，每遇到一个结点即可输出；在中序遍历中，结点在出栈时就输出，但在后序遍历中，在输出一个结点之前，要两次经历该结点。第一次是从该结点出发沿其左孩子指针遍历其左子树，第二次是沿其右孩子指针遍历其右子树。只有右子树遍历完成之后，才能访问该结点。这一次实验是用后序遍历的非递归算法来做的。对于创建树以及遍历二叉树用程序来运行我都不是很熟悉，刚开始都不去知道怎么输入二叉树，都是翻着课本写的，程序段有点复杂还可以精简，但我总是出错，这是在同学的帮助下才调试成功的。