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

实验5：二叉树的建立及遍历（第十三周星期三7、8节）一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2.编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。四、思考与提高1．如何计算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?/*----------------------------------------*05-1_递归遍历二叉树.cpp--递归遍历二叉树的相关操作*对递归遍历二叉树的每个基本操作都用单独的函数来实现*水上飘2009年写----------------------------------------*///ds05.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includeiostreamtypedefcharElemType;usingnamespacestd;typedefstructBiTNode{ElemTypedata;//左右孩子指针BiTNode*lchild,*rchild;}BiTNode,*BiTree;//动态输入字符按先序创建二叉树voidCreateBiTree(BiTree&T){charch;ch=cin.get();if(ch==''){T=NULL;}else{if(ch=='\n'){cout输入未结束前不要输入回车，要结束分支请输入空格！endl;}else{//生成根结点T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)cout内存分配失败！endl;T-data=ch;//构造左子树CreateBiTree(T-lchild);//构造右子树CreateBiTree(T-rchild);}}}//输出e的值ElemTypePrintElement(ElemTypee){coute;returne;}//先序遍历voidPreOrderTraverse(BiTreeT){if(T!=NULL){//打印结点的值PrintElement(T-data);//遍历左孩子PreOrderTraverse(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);//遍历右孩子PostOrderTraverse(T-rchild);//打印结点的值PrintElement(T-data);}}//按任一种遍历次序输出二叉树中的所有结点voidTraverseBiTree(BiTreeT,intmark){if(mark==1){//先序遍历PreOrderTraverse(T);coutendl;}elseif(mark==2){//中序遍历InOrderTraverse(T);coutendl;}elseif(mark==3){//后序遍历PostOrderTraverse(T);coutendl;}elsecout选择遍历结束！endl;}//输入值并执行选择遍历函数voidChoiceMark(BiTreeT){intmark=1;cout请输入，先序遍历为1，中序为2，后序为3，跳过此操作为0：;cinmark;if(mark0&&mark4){TraverseBiTree(T,mark);ChoiceMark(T);}elsecout此操作已跳过！endl;}//求二叉树的深度intBiTreeDepth(BiTNode*T){if(T==NULL){//对于空树，返回0并结束递归return0;}else{//计算左子树的深度intdep1=BiTreeDepth(T-lchild);//计算右子树的深度intdep2=BiTreeDepth(T-rchild);//返回树的深度if(dep1dep2)returndep1+1;elsereturndep2+1;}}int_tmain(intargc,_TCHAR*argv[]){BiTNode*bt;bt=NULL;//将树根指针置空cout输入规则：endl要生成新结点，输入一个字符，不要生成新结点的左孩子，输入一个空格，左右孩子都不要，输入两个空格，要结束，输入多个空格（越多越好）,再回车！endl按先序输入：;CreateBiTree(bt);cout树的深度为：BiTreeDepth(bt)endl;ChoiceMark(bt);return0;}/*----------------------------------------*05-2_构造二叉树.cpp--构造二叉树的相关操作*对构造二叉树的每个基本操作都用单独的函数来实现*水上飘2009年写----------------------------------------*///ds05-2.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includeiostream#defineSTACK_INIT_SIZE100//栈的存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefcharElemType;//元素类型usingnamespacestd;typedefstructBiTNode{ElemTypedata;//结点值BiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;typedefstruct{BiTree*base;//在栈构造之前和销毁之后，base的值为空BiTree*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;//构造一个空栈voidInitStack(SqStack&s){s.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!s.base)cout存储分配失败！endl;s.top=s.base;s.stacksize=STACK_INIT_SIZE;}//插入元素e为新的栈顶元素voidPush(SqStack&s,BiTreee){//栈满，追加存储空间if((s.top-s.base)=s.stacksize){s.base=(BiTree*)malloc((STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BiTree));if(!s.base)cout存储分配失败！endl;s.top=s.base+s.stacksize;s.stacksize+=STACK_INIT_SIZE;}*s.top++=e;}//若栈不空，则删除s的栈顶元素，并返回其值BiTreePop(SqStack&s){if(s.top==s.base)cout栈为空，无法删除栈顶元素！endl;s.top--;return*s.top;}//按先序输入字符创建二叉树voidCreateBiTree(BiTree&T){charch;//接受输入的字符ch=cin.get();if(ch==''){//分支结束T=NULL;}//if''endelseif(ch=='\n'){cout输入未结束前不要输入回车，要结束分支请输入空格！（接着输入）endl;}//if'\n'endelse{//生成根结点T=(BiTNode*)malloc(sizeof(BiTree));if(!T)cout内存分配失败！endl;T-data=ch;//构造左子树CreateBiTree(T-lchild);//构造右子树CreateBiTree(T-rchild);}//Createend}//输出e的值，并返回ElemTypePrintElement(ElemTypee){coute;returne;}//中序遍历二叉树的非递归函数voidInOrderTraverse(BiTreep,SqStack&S){cout中序遍历结果：;while(S.top!=S.base||p!=NULL){if(p!=NULL){Push(S,p);p=p-lchild;}//ifNULLendelse{BiTreebi=Pop(S);if(!PrintElement(bi-data))cout输出其值未成功！endl;p=bi-rchild;}//elseend}//whileendcoutendl;}int_tmain(intargc,_TCHAR*argv[]){BiTNode*bt;SqStackS;InitStack(S);bt=NULL;//将树根指针置空cout老师要求的二叉树序列（‘空’表示空格）：12空空346空空空5空空，再回车！endl请按先序输入一个二叉树序列（可另输入，但要为先序），无左右孩子则分别输入空格。endl开始输入：;CreateBiTree(bt);InOrderTraverse(bt,S);return0;}