数据结构实验报告树形数据结构实验.doc

实验报告书

课程名： 数据结构
题 目： 树形数据结构实验（1）
班 级：
学 号：
姓 名：

评语：

成绩： 指导教师：

批阅时间： 年 月 日

35 / 37
一、目的与要求
1）熟练掌握二叉树的二叉链表表示创建算法与实现；
2）熟练掌握栈的前序、中序和后序递归遍历算法与实现；
3）熟练掌握前序、中序和后序遍历线索二叉树的基本算法与实现;
4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
5）认真书写实验报告,并按时提交。
二、实验内容或题目
1) 创建二叉树：广义表式创建和先序创建；
2) 遍历二叉树：先，中，后，层序遍历，广义表式遍历，凹凸式遍历；
3) 二叉树属性：深度，宽度，结点数，叶子结点数
4) 二叉树路径：叶子结点到根结点的路径；
5）二叉树线索：中序线索二叉树；
6）二叉树置空：清空二叉树。
三、实验步骤与源程序
1)头文件Btree.h
#include <iostream.h>
#include <iomanip.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/**********************************对象--二叉数**************** ****************/
typedef char ElemType; // 定义元素类型
#define MAXSIZE 100 // 确定二叉树的最大结点数
/******************************二叉数的结点类定义******************************/
class BTreeNode
{
private:
int ltag,rtag; // 线索标记
BTreeNode *left; // 左子树指针
BTreeNode *right; // 右子树指针
public:
ElemType data; // 数据域
// 构造函数
BTreeNode()
{
ltag=0;
rtag=0;
left=NULL;
right=NULL;
}
// 带参数初始化的构造函数
BTreeNode(ElemType item,int ltag1,int rtag1,BTreeNode *left1,BTreeNode *right1)
{
data=item;
ltag=ltag1;
rtag=rtag1;
left=left1;
right=right1;
}
BTreeNode *&Left() // 返回结点的左孩子
{
return left;
}
// 返回结点的右孩子
BTreeNode *&Right()
{
return right;
}
friend class BinaryTree; // 二叉树类为二叉树结点类的友元类
};

/**********************************二叉数的类定义*******************************/

class BinaryTree
{
private:
BTreeNode *root;
public:
//构造函数.初始化二叉树为空
BinaryTree() { root=NULL; }
// 判断二叉树是否为空
bool BTreeEmpty() { return root==NULL; }

/****************************创建二叉数的相关成员函数***********************/

// 按照二叉树的广义表表示创建二叉树
void CreateBTree1();
// 递归创建二叉树,被函数CreateBTree1调用
void Create1(BTreeNode *&BT);
// 按一定次序输入二叉树中结点的值(一个字符),空格表示空树
void CreateBTree2(int make);
// 递归先序创建二叉树,被函数CreateBTree2调用
void Greate2(BTreeNode*&BT,int mark);
// 复制二叉树
void BTreeCopy(BTreeNode *&root,BTreeNode *&BT);

/****************************遍历二叉数的相关成员函数***********************/

// 按任一种遍历次序输出二叉树中的所有结点
void TraverseBTree(int mark);
// 用于遍历的递归函数,被函数TraverseBTree调用
void Traverse(BTreeNode *&BT,int mark);
// 先序遍历的递归函数
void PreOrder(BTreeNode *&BT);
// 先序遍历的非递归函数一
void PreOrder_N1(BTreeNode *&BT);
// 先序遍历的非递归函数二
void PreOrder_N2(BTreeNode *&BT);
// 中序遍历的递归函数
void InOrder(BTreeNode *&BT);
// 中序遍历的非递归函数一
void InOrder_N1(BTreeNode *&BT);
// 中序遍历的非递归函数二
void InOrder_N2(BTreeNode *&BT);
// 后序遍历的递归函数
void PostOrder(BTreeNode *&BT);
// 后序遍历的非递归函数一
void PostOrder_N1(BTreeNode *&BT);
// 后序遍历的递归函数
void PostOrder_N2(BTreeNode *&BT);
// 层序遍历的非递归函数
void LayerOrder(BTreeNode *&BT);
// 按照二叉树的广义表表示输出整个二叉树
void GPrintBTree();
// 广义表形式输出整个二叉树的递归函数,被函数Print调用
void GPrint(BTreeNode *&BT);
// 以凹凸表示法输出二叉树
void OPrintTree();

/**********************************二叉树的属性*****************************/
/****************计算二叉数深度,宽度,叶子,结点的相关成员函数****************/

// 求二叉树的深度
int BTreeDepth();
// 用于求二叉树深度的递归函数,被BTreeDepth调用
int Depth(BTreeNode *&BT);
// 求二叉树的宽度
int BTreeWidth();
// 求二叉树中所有结点数
int BTreeCount();
// 用于求二叉树所有结点数的递归函数,被函数BTreeCount调用
int Count(BTreeNode *&BT);
// 求二叉树中所有叶子结点数
int BTreeLeafCount();
// 用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用
int LeafCount(BTreeNode *&BT);
// 输出二叉树的所有叶子结点
void BTreeLeafPrint();
// 用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用
void LeafPrint(BTreeNode *&BT);

/***********************二叉树中从根结点到叶子结点的路径相关函数****************/
// 输出从根结点到叶子结点的路径,以及最长路径
void BTreePath();
// 输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用
void PathLeaf(BTreeNode *&BT,ElemType path[],int pathlen);
// 求最长路径的递归函数,被函数BTreePaht调用
void BTreeLongpath(BTreeNode *&BT,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen);
// 非递归方法输出从根结点到叶子结点的路径
void BTreePath_N1();

// 返回data域为x的结点指针
void BTreeFind(ElemType x);
// 返回data域为x的结点指针的递归函数,被函数BTreeFind调用
BTreeNode *FindNode(BTreeNode *&BT,ElemType x);

/*************************************线索二叉树****************************/

// 线索化二叉树
void CreateThread();
// 中序线索化二叉树的递归函数,被函数CreateThread调用
void InOrderThread(BTreeNode *&BT,BTreeNode *&pre);
// 中序线索化二叉树中实现中序遍历,被函数CreateThread调用
void ThInOrder(BTreeNode *&BT);

/****************************销毁二叉数的相关成员函数***********************/

// 置空二叉树
void BTreeClear();
// 用于清除二叉树的递归函数,被函数BTreeClear和~BinaryTree调用
void Clear(BTreeNode *&BT);
// 析构函数,清除二叉树
~BinaryTree();
};

/******************************创建二叉数的相关成员函数*************************/

// 按照二叉树的广义表表示创建二叉树
void BinaryTree::CreateBTree1()
{
cout<<"输入广义表形式的二叉树:"<<endl;
root=NULL; // 给树根指针置空
Create1(root);
}
// 递归创建二叉树,被函数CreateBTree1调用
void BinaryTree::Create1(BTreeNode *&BT)
{
BTreeNode *stack[MAXSIZE],*p=NULL;
int k,top=-1;
char ch;
while((ch=getchar())!='#')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1; // 即将建立左结点
break;
case ')':
top--;
break;
case ',':
k=2; // 即将建立右结点
break;
default:
if(!(p=new BTreeNode))
{
cout<<"\n堆内存分配失败\n";
exit(1);
}
p->data=ch;
p->left=p->right=NULL;
if(BT==NULL) // p指向二叉树的根结点,建立根结点
BT=p;
else // 已经建立根结点
{
if(k==1) // 建立左结点
stack[top]->left=p;
else // 建立右结点
stack[top]->right=p;
}
}//switch(ch)
}//while
}

// 按一定次序输入二叉树中结点的值(一个字符),空格表示空树
void BinaryTree::CreateBTree2(int mark)
{
switch(mark)
{
case 1:
puts("按先序输入二叉树:");
break;
case 2:
puts("按中序输入二叉树:");
break;
case 3:
puts("按后序输入二叉树:");
break;
}
root=NULL; // 给树根指针置空
BTreeNode *&p=root; // 定义p为指向二叉树结点的指针
Greate2(p,mark);
}
// 递归创建二叉树,被函数CreateBTree2调用
void BinaryTree::Greate2(BTreeNode *&BT,int mark)
{
char ch;
ch=getchar();
switch(mark)
{
case 1: // 先序创建
if(ch==' ')
BT=NULL;
else
{
if(!(BT=new BTreeNode))
{
cout<<"\n堆内存分配失败\n";
exit(1);
}
BT->data=ch;
Greate2(BT->left,mark);
Greate2(BT->right,mark);
}
break;
case 2:
break;
case 3:
break;
}
}

// 复制二叉树
void BinaryTree::BTreeCopy(BTreeNode *&root,BTreeNode *&BT)
{
if(root)
{
if(!(BT=new BTreeNode))
{
exit(1);
}
BT->data=root->data;
BTreeCopy(root->left,BT->left);
BTreeCopy(root->right,BT->right);
}
else
BT=NULL;
}

/*******************************遍历二叉数的相关成员函数************************/

// 按任一种遍历次序输出二叉树中的所有结点
void BinaryTree::TraverseBTree(int mark)
{
srand(time(NULL)); // 产生随机种子数,用来选择相同顺序遍历的不同算法
Traverse(root,mark);
cout<<endl;
}
// 用于遍历的递归函数,被函数TraverseBTree调用
void BinaryTree::Traverse(BTreeNode *&BT,int mark)
{
int option;
switch(mark)
{
case 1: // 先序遍历
{
option=rand()%3+1;
switch(option) // 随机选择一种先序算法
{
case 1:
PreOrder(BT);
break;
case 2:
PreOrder_N1(BT);
break;
case 3:
PreOrder_N2(BT);
break;
}
break;
}
case 2: // 中序遍历
{
option = rand()%3 + 1;
switch(option) // 随机选择一种中序算法
{
case 1:
InOrder(BT);
break;
case 2:
InOrder_N1(BT);
break;
case 3:
InOrder_N2(BT);
break;
}
break;
}
case 3: // 后序遍历
{
option=rand()%3+1;
switch(option) // 随机选择一种先序算法
{
case 1:
PostOrder(BT);
break;
case 2:
PostOrder_N1(BT);
break;
case 3:
PostOrder_N2(BT);
break;
}
break;
}
case 4: // 层序遍历
{
LayerOrder(BT);
break;
}
default:
cout<<"mark的值无效!遍历失败!"<<endl;
}
}

// 先序遍历的递归函数
void BinaryTree::PreOrder(BTreeNode *&BT)
{
if(BT!=NULL)
{
cout<<BT->data<<' ';
PreOrder(BT->left);
PreOrder(BT->right);
}
}

// 先序遍历的非递归函数一
void BinaryTree::PreOrder_N1(BTreeNode *&BT)
{
BTreeNode *p;
struct
{
BTreeNode *pt;
int tag;
}stack[MAXSIZE];
int top=-1;
top++;
stack[top].pt=BT;
stack[top].tag=1;
while(top>-1) // 栈不空时循环
{
if(stack[top].tag==1) // 不能直接访问
{
p=stack[top].pt;
top--;
if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历
{
top++;
stack[top].pt=p->right; // 右孩子入栈
stack[top].tag=1;
top++;
stack[top].pt=p->left; // 左孩子入栈
stack[top].tag=1;
top++;
stack[top].pt=p; // 根结点入栈
stack[top].tag=0; // 可以直接访问
}
}
if(stack[top].tag==0) // 可以直接访问
{
cout<<stack[top].pt->data<<' ';
top--;
}
}
}

// 先序遍历的非递归函数二
void BinaryTree::PreOrder_N2(BTreeNode *&BT)
{
BTreeNode *stack[MAXSIZE],*p;
int top = -1;
if(BT!=NULL)
{
top++; // 根结点入栈
stack[top] = BT;
while(top>-1) // 栈不空时循环
{
p=stack[top];
top--;
cout<<p->data<<" ";
if(p->right != NULL) // 右孩子入栈
{
top++;
stack[top] = p->right;
}
if(p->left != NULL) // 左孩子入栈
{
top++;
stack[top] = p->left;
}
}//while
}//if(root!=NULL)
}

// 中序遍历的递归函数
void BinaryTree::InOrder(BTreeNode *&BT)
{
if(BT!=NULL)
{
InOrder(BT->left);
cout<<BT->data<<' ';
InOrder(BT->right);
}
}

// 中序遍历的非递归函数一
void BinaryTree::InOrder_N1(BTreeNode *&BT)
{
BTreeNode *p;
struct
{
BTreeNode *pt;
int tag;
}stack[MAXSIZE];
int top = -1;
top++;
stack[top].pt = BT;
stack[top].tag = 1;
while(top>-1) // 栈不空时循环
{
if(stack[top].tag == 1) // 不能直接访问
{
p = stack[top].pt;
top--;
if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历
{
top++;
stack[top].pt=p->right; // 右孩子入栈
stack[top].tag = 1;
top++;
stack[top].pt = p; // 根结点入栈
stack[top].tag = 0; // 可以直接访问
top++;
stack[top].pt =p->left; // 左孩子入栈
stack[top].tag = 1;

}
}
if(stack[top].tag == 0) // 可以直接访问
{
cout<<stack[top].pt->data<<' ';
top--;
}
}
}

// 中序遍历的非递归函数二
void BinaryTree::InOrder_N2(BTreeNode *&BT)
{
BTreeNode *stack[MAXSIZE],*p;
int top = -1;
if(BT != NULL)
{
p = BT;
while(top > -1||p != NULL)
{
while(p != NULL) // 所有左结点入栈
{
top++;
stack[top] = p;
p = p->left;
}
if(top > -1)
{
p = stack[top];
top--;
cout<<p->data<<" ";
p = p->right;
}
}
}//if
}

// 后序遍历的递归函数
void BinaryTree::PostOrder(BTreeNode *&BT)
{
if(BT!=NULL)
{
PostOrder(BT->left);
PostOrder(BT->right);
cout<<BT->data<<' ';
}
}

// 后序遍历的非递归函数一
void BinaryTree::PostOrder_N1(BTreeNode *&BT)
{
BTreeNode *p;
struct
{
BTreeNode *pt;
int tag;
}stack[MAXSIZE];
int top = -1;
top++;
stack[top].pt = BT;
stack[top].tag = 1;
while(top>-1) // 栈不空时循环
{
if(stack[top].tag == 1) // 不能直接访问
{
p = stack[top].pt;
top--;
if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历
{
top++;
stack[top].pt = p; // 根结点入栈
stack[top].tag = 0; // 可以直接访问
top++;
stack[top].pt=p->right; // 右孩子入栈
stack[top].tag = 1;
top++;
stack[top].pt =p->left; // 左孩子入栈
stack[top].tag = 1;

}
}
if(stack[top].tag == 0) // 可以直接访问
{
cout<<stack[top].pt->data<<' ';
top--;
}
}
}

// 后序遍历的非递归函数二
void BinaryTree::PostOrder_N2(BTreeNode *&BT)
{
BTreeNode *stack[MAXSIZE],*p,*q;
q=BT;
int top = -1,flag;
if(q != NULL)
{
do
{
while(q != NULL) // 所有左结点入栈
{
top++;
stack[top] = q;
q = q->left;
}
p=NULL; // p指向当前结点的前一个已访问的结点
flag=1; // 设置q的访问标记为已访问过
while(top > -1&&flag)
{
q = stack[top]; // 取出当前栈顶元素
if(q->right == p) // 当右孩子不存在或已被访问时,则访问
{
cout<<q->data<<" ";
top--;
p = q; // p指向刚被访问的结点
}
else
{
q = q->right; // 指向右孩子
flag = 0; // 设置未被访问的标记
}
}
}while(top>-1);
}//if
}

// 层序遍历的非递归函数
void BinaryTree::LayerOrder(BTreeNode *&BT)
{
BTreeNode *Queue[MAXSIZE]; // 定义存储二叉树结点指针的数组空间作为队列使用
int front=0,rear=0; // 定义队首指针和队尾指针,初始均置0表示空队
BTreeNode *p;
if(BT!=NULL)
{
rear=(rear+1)%MAXSIZE; // 后移队尾指针
Queue[rear]=BT; // 将树根结点指针进队
}
while(front!=rear) // 当队列非空时执行循环
{
front=(front+1)%MAXSIZE; // 后移队首指针
p=Queue[front]; // 删除队首结点的值
cout<<p->data<<' '; // 输出队首结点的值
if(p->left!=NULL) // 若结点存在左孩子,则左孩子结点指针进队
{
rear=(rear+1)%MAXSIZE;
Queue[rear]=p->left;
}
if(p->right!=NULL) // 若结点存在右孩子,则右孩子结点指针进队
{
rear=(rear+1)%MAXSIZE;
Queue[rear]=p->right;
}
}
}

// 按照二叉树的广义表表示输出整个二叉树
void BinaryTree::GPrintBTree()
{
GPrint(root);
cout<<endl;
}
// 广义表形式输出整个二叉树的递归函数,被函数Print调用
void BinaryTree::GPrint(BTreeNode *&BT)
{
if(BT==NULL)
return; // 树为空时返回
else // 否则执行如下操作
{

cout<<BT->data; // 输出根结点的值
if(BT->left!=NULL||BT->right!=NULL)
{
cout<<'('; // 输出左括号
GPrint(BT->left); // 输出左子树
if(BT->right!=NULL)
cout<<','; // 若右子树不为空则输出逗号分隔符
GPrint(BT->right); // 输出右子树
cout<<')'; // 输出右括号
}
}
}

// 以凹凸表示法输出二叉树
void BinaryTree::OPrintTree()
{
cout<<endl;
BTreeNode *stack[MAXSIZE],*p;
int level[MAXSIZE][2],top=-1,n,i,width=4;
int maxwidth=40;
char type[20];
char *pre_type=type;
if(root!=NULL)
{
top++; // 根结点入栈
stack[top]=root;
level[top][0]=width;
level[top][1]=2; // 2表示是根
while(top>-1)
{
p=stack[top]; // 退栈并凹入显示该结点值
n=level[top][0];
switch(level[top][1])
{
case 0:
pre_type="左结点";
break;
case 1:
pre_type="右结点";
break;
case 2:
pre_type="根结点";
}
for(i=1;i<=n;i++) // n为显示场宽,字符以右对齐显示
cout<<" ";
cout<<" "<<p->data<<"("<<pre_type<<")";
for(i=n+1;i<=maxwidth;i+=2)
cout<<"--";
cout<<endl;
top--;
if(p->right!=NULL)
{
top++; // 将右子树树根结点入栈
stack[top]=p->right;
level[top][0]=n+width; // 显示场宽增加width
level[top][1]=1; // 1表示右子树
}
if(p->left!=NULL)
{
top++; // 将左子树树根结点入栈
stack[top]=p->left;
level[top][0]=n+width; // 显示场宽增加width
level[top][1]=0; // 0表示左子树
}
}//while
}//if
}

/******************计算二叉数深度,宽度,叶子,结点的相关成员函数******************/

// 求二叉树的深度
int BinaryTree::BTreeDepth()
{
return Depth(root);
}
// 用于求二叉树深度的递归函数,被BTreeDepth调用
int BinaryTree::Depth(BTreeNode *&BT)
{
if(BT==NULL)
return 0; // 对于空树,返回0并结束递归
else
{
int dep_left=Depth(BT->left); // 计算左子树的深度
int dep_right=Depth(BT->right); // 计算右子树的深度
if(dep_left>dep_right) // 返回树的深度
return dep_left+1;
else
return dep_right+1;
}