2022年数据结构试验树的建立于运算可用 .pdf
实验报告实验名称：数据结构实验四实验内容：树的建立与运算实验仪器：计算机学院：计算机学院班级：B 软件工程学号：XXXXX 姓名：XXXX 成绩：指导教师：XXX 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -实验四树的建立与运算问题描述生成一棵以二叉链表存储的二叉树bt（不少于15 个结点）。分别用递归和非递归方法前序遍历bt，并以缩格形式打印bt 上各结点的信息。编写算法，交换 bt 上所有结点的左、右子树，并以缩格形式打印出交换前后的bt 结点信息。程序代码#includestdafx.h#includestdio.h#includestdlib.h#includeconio.h usingnamespace System;struct tnode int data;tnode*left;tnode*right;int lw;int ld;struct Q_node tnode*data;Q_node*next;class queue Q_node*head;public:queue()head=NULL;void In(tnode*d)Q_node*t=(Q_node*)malloc(sizeof(Q_node);t-next=NULL;t-data=d;if (NULL=head)head=t;else Q_node*p=head;for (;p-next;p=p-next);p-next=t;tnode*Out()tnode*res=head-data;Q_node*p=head;head=head-next;free(p);return res;int HasNext()if (head)return 1;elsereturn 0;tnode*root;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -int CreateTree(tnode*r)(*r)=(tnode*)malloc(sizeof(tnode);(*r)-left=NULL;(*r)-right=NULL;return 1;void CreateEmptyNode(tnode*n)CreateTree(n);int Insert(tnode*r,int d)tnode*newnode;CreateEmptyNode(&newnode);newnode-data=d;int NotFinded=1;tnode*p=r;while(NotFinded)if (d=p-data&p-right=NULL)p-right=newnode;NotFinded=0;elseif (ddata&p-left=NULL)p-left=newnode;NotFinded=0;elseif (d=p-data)p=p-right;else p=p-left;return 1;int Retree(int LBorder,tnode*node,int level)node-ld=level;if (NULL=node-left)node-lw=LBorder;else node-lw=Retree(LBorder,node-left,level+1)+2;int r_child_width=node-lw;if (NULL!=node-right)r_child_width=Retree(node-lw+2,node-right,level+1);return r_child_width;void PrintTree(tnode*r)queue que;que.In(r);int level=r-ld;int pos=0;char line72;for (int i=0;ild level)level+;printf(n);printf(%sn,line);pos=0;for (int i=0;i71;i+)linei=;line71=0;for (int i=pos;ilw;i+)printf();printf(%2d,temp-data,temp-lw,pos);pos=temp-lw+2;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -if (temp-left)linetemp-lw+1=+;for(int i=temp-lw;i2+temp-left-lw;i-)linei=-;linetemp-left-lw+2=/;que.In(temp-left);if (temp-right)linetemp-lw+1=+;for(int i=temp-lw+2;iright-lw;i+)linei=-;linetemp-right-lw=;que.In(temp-right);void Reloadtree(tnode*node)tnode*temp;temp=node-left;node-left=node-right;node-right=temp;if (NULL!=node-left)Reloadtree(node-left);if (NULL!=node-right)Reloadtree(node-right);int main()int datas=25,18,12,2,17,26,10,0,21,11,15,31,1,9,22,37,9,45,16,33,-1;CreateTree(&root);root-data=datas0;for (int i=1;datasi!=-1;i+)Insert(root,datasi);Retree(0,root,0);PrintTree(root);Reloadtree(root);Retree(0,root,0);printf(n);PrintTree(root);free(root);while(!kbhit();return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -运行结果名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -
