树的应用算与数据结构.doc

《树的应用算与数据结构.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法与数据结构》实验报告（一）实验题目：树的应用1、实验目的：（1）针对问题的实际要求，正确应用树形结构组织和存储数据；（2）掌握二叉树的存储方法。（3）掌握二叉树的各种遍历方法。2、实验内容:二叉树后序遍历的非递归算法。3、实验说明：二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。1第一次出栈，只遍历完左子树，该结点不能访问2第二次出栈，遍历完右子树，该结点可以访问flag＝设根指针为roo

2、t，则可能有以下两种情况：⑴若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；⑵若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。二叉树后序遍历的非递归算法伪代码如下：1.栈s初始化；2.循环直到root为空且栈s为空2.1当root

3、非空时循环2.1.1将root连同标志flag=1入栈；2.1.2继续遍历root的左子树；2.2当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;2.3若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；设计分析在后序遍历中，在输出一个结点之前，要两次经历该结点。第一次是从该结点出发沿其左孩子指针遍历其左子树，第二次是沿其右孩子指针遍历其右子树。只有右子树遍历完成之后，才能访问该结点。因此，一个结点要分两次进栈，只有第二次出栈时，才能访问该结点。也就是说，在后序遍历中要区分是从左子

4、树返回还是从右子树返回，在结点入栈时，必须同时压入一个标记，用该标记指明返回的情况。所以基本思路1.从根开始，不断将左子树指针压栈，直到指针为空为止；2.看栈顶元素如果它没有右孩子，或者它的右孩子刚被访问过，访问该结点，弹栈；转到2；否则它的右孩子不空且未被访问过，则必须将它的右孩子继续压栈；转到1；3.栈空，则结束。源程序代码#includetypedefstructnode{chardata;structnode*lchild,*rchild;}BiTreeNode;

5、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;}defa

6、ult:{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;}

7、;stacknode*s;s=newstacknode[100];p=pnode;while(p!=NULL

8、

9、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--;cout<data<

10、iTreeNode*ss;intt=0;charp[100];cout<<"***********后序遍历二叉树********"<>p;}while(t);BiTreea;a.CreatBtree(ss,p);cout<<"后序遍历序列为:"<