实验叉树.docVIP

实验4　二叉树 班级：　姓名：　学号：　机号： 一、实验目的 掌握树形结构的特点，二叉树的遍历算法. 二、实验内容 1.输出二叉树的前序、中序和后序遍历的结果 2.输出二叉树的深度，最大元，最小元。 3.二叉树的中序线索化。 三、操作提示 打开D:\A\BiTree\BiTree.dsw文件。下面在该文件中完成。 1.实现中序遍历 S1：在CBiTreeView类中添加一个函数用于实现中序遍历。 如下图所示。打开ClassView视图，右击名为CBiTreeView的视图类，从快捷菜单中选择Add Member Function 按下图所示输入函数类型和函数名及参数等，完成后单击“确定按钮” S2：输入函数内容 int CBiTreeView::InOrderTraverse(BiTree T) { CDC *pDC=GetDC();//定义指针用于调用输出函数 CString str; if(T) { InOrderTraverse(T-lchild);//中序遍历左子树 str.Format(%d,T-data);//将结点数据转换为字符串 pDC-TextOut(count*30,300+county*20,str);//输出结点数据 count++; //改变输出位置 InOrderTraverse(T-rchild);//中序遍历右子树 return 1; } return 0; } S3：添加菜单项用于调用中序遍历算法 S31：如下图所示。打开资源视图：ResourcesView，单击+号展开资源树，单击Menu前面的＋号展开Menu，然后双击其中的IDR_MAINFRAME S32：单击“二叉树”，双击“初始化二叉树”下的空白框 S33：输入菜单ID和菜单名，完成后关闭对话框。如下图所示 S34：为菜单项添加消息映射 按Ctrl+W,在打开的对话框中按下图所示进行操作 S35：输入下面红色代码 void CBiTreeView::OnInorder() { InOrderTraverse(Tree); county++; count=1; } 2.实现先序遍历 方法与第1点中序遍历相同，只在添加函数名时将代表中序的In改为Pre，添加菜单项时要将IN改为PRE，遍历算法中遍历右子树的位置改在遍历左子树后面（遍历子树时的函数名也必须作相应改为） 3.实现后序遍历 方法与2类似，将Pre改为Post 4.输出二叉树的深度（注意要通过1的方法添加函数，不能直接将函数直接复制） int CBiTreeView::Depth(BiTree T) { int depthval,depthLeft,depthRight; if ( !T)depthval = 0; else { depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval=1+(depthLeft depthRight?depthLeft:depthRight); } return depthval; } void CBiTreeView::OnBitreedepth() { CDC *pDC=GetDC();//定义指针用于调用输出函数 CString str; str.Format(%d,Depth(Tree)); pDC-TextOut(count*30,300+county*20,str); } 输出树的最大值和最小值函数 void CBiTreeView::maxmin(BiTree T,int max,int min) { // 返回二叉树的最大值和最小值 if (T) { if(T-data*max) *max=T-data; if(T-data*min) *min=T-data; maxmin(T-lchild,max,min); maxmin(T-rchild,max,min); } } 5.中序线索化与中序遍历 中序线索化：算法6.6 int CBiTreeView::InOrderThreading(BiTree Thrt, BiTree T) { if (!(Thrt = (BiTree)malloc(sizeof(BiTNode)))) return 0; Thrt-LTag = 0; Thrt-RTag =1; // 建头结点 Thrt-rchild = Thrt; // 右指针回指 if (!T) Thrt-l