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

.实验5：二叉树的建立及遍历（第十三周星期三7、8节）一 、实验目的1学会实现二叉树结点结构和对二叉树的基本操作。2掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二 、实验要求1认真阅读和掌握和本实验相关的教材内容。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。 三、实验内容1编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。 四、思考与提高 1如何计算二叉链表存储的二叉树中度数为1的结点数？ 2已知有棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径? /*- * 05-1_递归遍历二叉树.cpp - 递归遍历二叉树的相关操作 * 对递归遍历二叉树的每个基本操作都用单独的函数来实现 * 水上飘 2009年写 -*/ ds05.cpp : Defines the entry point for the console application./#include stdafx.h#include 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 内存分配失败！ data = ch;/构造左子树CreateBiTree(T-lchild);/构造右子树CreateBiTree(T-rchild);/输出e的值ElemType PrintElement(ElemType e) cout e 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 mark;if(mark 0 & mark 4) TraverseBiTree(T, mark);ChoiceMark(T);else cout 此操作已跳过！ lchild);/计算右子树的深度int dep2 = BiTreeDepth(T-rchild);/返回树的深度if(dep1 dep2)return dep1 + 1;elsereturn dep2 + 1;int _tmain(int argc, _TCHAR* argv)BiTNode *bt;bt = NULL; /将树根指针置空cout 输入规则： endl 要生成新结点，输入一个字符，不要生成新结点的左孩子，输入一个空格，左右孩子都不要，输入两个空格，要结束，输入多个空格（越多越好）,再回车！ endl 按先序输入：;CreateBiTree(bt);cout 树的深度为： BiTreeDepth(bt) endl;ChoiceMark(bt);return 0;/*- * 05-2_构造二叉树.cpp - 构造二叉树的相关操作 * 对构造二叉树的每个基本操作都用单独的函数来实现 * 水上飘 2009年写 -*/ ds05-2.cpp : Defines the entry point for the console application./#include stdafx.h#include #define STACK_INIT_SIZE 100 /栈的存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef char ElemType; /元素类型using namespace std;typedef struct BiTNode ElemType data; /结点值BiTNode *lchild, *rchild; /左右孩子指针BiTNode, *BiTree;typedef struct BiTree *base; /在栈构造之前和销毁之后，base的值为空BiTree *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/构造一个空栈void InitStack(SqStack &s) s.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree);if(!s.base)cout 存储分配失败！ = 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的栈顶元素，并返回其值BiTree Pop(SqStack &s) if(s.top = s.base)cout 栈为空，无法删除栈顶元素！ endl;s.top-;return *s.top;/按先序输入字符创建二叉树void CreateBiTree(BiTree &T) char ch;/接受输入的字符ch = cin.get();if(ch = ) /分支结束T = NULL; /if endelse if(ch = n) cout 输入未结束前不要输入回车，要结束分支请输入空格！（接着输入） endl; /ifnendelse /生成根结点T = (BiTNode * )malloc(sizeof(BiTree);if(!T)cout 内存分配失败！ data = ch;/构造左子树CreateBiTree(T-lchild);/构造右子树CreateBiTree(T-rchild); /Create end/输出e的值，并返回ElemType PrintElement(ElemType e) cout e ;return e;/中序遍历二叉树的非递归函数void InOrderTraverse(BiTree p, SqStack &S) cout lchild; /if NULL endelse BiTree bi = Pop(S);if(!PrintElement(bi-data)cout 输出其值未成功！ rchild; /else end /while endcout endl;int _tmain(int argc, _TCHAR* argv)BiTNode *bt;