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

实验5：二叉树的建立及遍历 （第十三周星期三7、8节） 一 、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二 、实验要求 1．认真阅读和掌握和本实验相关的教材内容生成二叉树，并/*---------------------------------------- * 05-1_递归遍历二叉树.cpp -- 递归遍历二叉树的相关操作 * 对递归遍历二叉树的每个基本操作都用单独的函数来实现 * 水上飘 2009年写 ----------------------------------------*/ // ds05.cpp : Defines the entry point for the console application. // #include stdafx.h #include iostream typedef char ElemType; using namespace std; typedef struct BiTNode { ElemType data; //左右孩子指针 BiTNode *lchild, *rchild; }BiTNode, *BiTree; //动态输入字符按先序创建二叉树 void CreateBiTree(BiTree T) { char ch; 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的值 ElemType PrintElement(ElemType e) { cout e ; return e; } //先序遍历 void PreOrderTraverse(BiTree T) { if (T != NULL) { //打印结点的值 PrintElement(T-data); //遍历左孩子 PreOrderTraverse(T-lchild); //遍历右孩子 PreOrderTraverse(T-rchild); } } //中序遍历 void InOrderTraverse(BiTree T) { if (T != NULL) { //遍历左孩子 InOrderTraverse(T-lchild); //打印结点的值 PrintElement(T-data); //遍历右孩子 InOrderTraverse(T-rchild); } } //后序遍历 void PostOrderTraverse(BiTree T) { if (T != NULL) { //遍历左孩子 PostOrderTraverse(T-lchild); //遍历右孩子 PostOrderTraverse(T-rchild); //打印结点的值 PrintElement(T-data); } } //按任一种遍历次序输出二叉树中的所有结点 void TraverseBiTree(BiTree T, int mark) { if(mark == 1) { //先序遍历 PreOrderTraverse(T); cout endl; } else if(mark == 2) { //中序遍历 InOrderTraverse(T); cout endl; } else if(mark == 3) { //后序遍历 PostOrderTraverse(T); cout endl; } else cout 选择遍历结束！ endl; } //输入值并执行选择遍历函数 void ChoiceMark(BiTree T) { int mark = 1; cout 请输入，先序遍历为1，中序为2，后序为3，跳过此操作为0：; cin mark; if(mark 0 mark 4) { TraverseB