数据结构实验五(二叉树的建立及遍历)题目和源程序

《数据结构实验五(二叉树的建立及遍历)题目和源程序》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验5：二叉树的建立及遍历（第十三周星期三7、8节）一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2.编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。四、思考与提高1．如何计

2、算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?/*----------------------------------------*05-1_递归遍历二叉树.cpp--递归遍历二叉树的相关操作*对递归遍历二叉树的每个基本操作都用单独的函数来实现*水上飘2009年写----------------------------------------*///ds05.cpp:Definestheentrypointfortheconsoleapplication.//#inclu

3、de"stdafx.h"#includetypedefcharElemType;usingnamespacestd;typedefstructBiTNode{ElemTypedata;//左右孩子指针BiTNode*lchild,*rchild;}BiTNode,*BiTree;//动态输入字符按先序创建二叉树voidCreateBiTree(BiTree&T){charch;ch=cin.get();if(ch==''){T=NULL;}else{if(ch==''){cout<<"输入未结束前不要输入回车，""要结束分支请输入空格！"<

4、{//生成根结点T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)cout<<"内存分配失败！"<data=ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}}}//输出e的值ElemTypePrintElement(ElemTypee){cout<data);//遍历左孩子Pre

5、OrderTraverse(T->lchild);//遍历右孩子PreOrderTraverse(T->rchild);}}//中序遍历voidInOrderTraverse(BiTreeT){if(T!=NULL){//遍历左孩子InOrderTraverse(T->lchild);//打印结点的值PrintElement(T->data);//遍历右孩子InOrderTraverse(T->rchild);}}//后序遍历voidPostOrderTraverse(BiTreeT){if(T!=NULL){//遍历左孩子PostOrderTraverse(T->lchild);//

6、遍历右孩子PostOrderTraverse(T->rchild);//打印结点的值PrintElement(T->data);}}//按任一种遍历次序输出二叉树中的所有结点voidTraverseBiTree(BiTreeT,intmark){if(mark==1){//先序遍历PreOrderTraverse(T);cout<

7、结束！"<>mark;if(mark>0&&mark<4){TraverseBiTree(T,mark);ChoiceMark(T);}elsecout<<"此操作已跳过！"<