实验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 <iostream>
typedef char ElemType;
using namespace std;
typedef struct BiTNode {
ElemType data;
//左右孩子指针
BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//动态输入字符按先序创建二叉树
void CreateBiTree(BiTree &T) {
char ch;
ch = ();
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) {
TraverseBiTree(T, mark);
ChoiceMark(T);
}
else cout << "此操作已跳过！" << endl;
}
//求二叉树的深度
int BiTreeDepth(BiTNode *T) {
if (T == NULL) {
//对于空树，返回0并结束递归
return 0;
}
else {
//计算左子树的深度
int dep1 = BiTreeDepth(T->lchild);
//计算右子树的深度
int dep2 = BiTreeDepth(T->rchild);
//返回树的深度
if(dep1 > dep2)
return dep1 + 1;
else
return 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 <iostream>
#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; //栈顶指针
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论