数据结构实验报告树形数据结构实验.docx
- 文档编号:17500473
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:59
- 大小:122.04KB
数据结构实验报告树形数据结构实验.docx
《数据结构实验报告树形数据结构实验.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告树形数据结构实验.docx(59页珍藏版)》请在冰点文库上搜索。
数据结构实验报告树形数据结构实验
实验报告书
课程名:
数据结构
题目:
树形数据结构实验
(1)
班级:
学号:
姓名:
一、目的与要求
1)熟练掌握二叉树的二叉链表表示创建算法与实现;
2)熟练掌握栈的前序、中序和后序递归遍历算法与实现;
3)熟练掌握前序、中序和后序遍历线索二叉树的基本算法与实现;
4)按照实验题目要求独立正确地完成实验内容(提交程序清单及相关实验数据与运行结果);
5)认真书写实验报告,并按时提交。
二、实验内容或题目
1)创建二叉树:
广义表式创建和先序创建;
2)遍历二叉树:
先,中,后,层序遍历,广义表式遍历,凹凸式遍历;
3)二叉树属性:
深度,宽度,结点数,叶子结点数
4)二叉树路径:
叶子结点到根结点的路径;
5)二叉树线索:
中序线索二叉树;
6)二叉树置空:
清空二叉树。
三、实验步骤与源程序
1)头文件Btree.h
#include
#include
#include
#include
#include
/**********************************对象--二叉数********************************/
typedefcharElemType;//定义元素类型
#defineMAXSIZE100//确定二叉树的最大结点数
/******************************二叉数的结点类定义******************************/
classBTreeNode
{
private:
intltag,rtag;//线索标记
BTreeNode*left;//左子树指针
BTreeNode*right;//右子树指针
public:
ElemTypedata;//数据域
//构造函数
BTreeNode()
{
ltag=0;
rtag=0;
left=NULL;
right=NULL;
}
//带参数初始化的构造函数
BTreeNode(ElemTypeitem,intltag1,intrtag1,BTreeNode*left1,BTreeNode*right1)
{
data=item;
ltag=ltag1;
rtag=rtag1;
left=left1;
right=right1;
}
BTreeNode*&Left()//返回结点的左孩子
{
returnleft;
}
//返回结点的右孩子
BTreeNode*&Right()
{
returnright;
}
friendclassBinaryTree;//二叉树类为二叉树结点类的友元类
};
/**********************************二叉数的类定义*******************************/
classBinaryTree
{
private:
BTreeNode*root;
public:
//构造函数.初始化二叉树为空
BinaryTree(){root=NULL;}
//判断二叉树是否为空
boolBTreeEmpty(){returnroot==NULL;}
/****************************创建二叉数的相关成员函数***********************/
//按照二叉树的广义表表示创建二叉树
voidCreateBTree1();
//递归创建二叉树,被函数CreateBTree1调用
voidCreate1(BTreeNode*&BT);
//按一定次序输入二叉树中结点的值(一个字符),空格表示空树
voidCreateBTree2(intmake);
//递归先序创建二叉树,被函数CreateBTree2调用
voidGreate2(BTreeNode*&BT,intmark);
//复制二叉树
voidBTreeCopy(BTreeNode*&root,BTreeNode*&BT);
/****************************遍历二叉数的相关成员函数***********************/
//按任一种遍历次序输出二叉树中的所有结点
voidTraverseBTree(intmark);
//用于遍历的递归函数,被函数TraverseBTree调用
voidTraverse(BTreeNode*&BT,intmark);
//先序遍历的递归函数
voidPreOrder(BTreeNode*&BT);
//先序遍历的非递归函数一
voidPreOrder_N1(BTreeNode*&BT);
//先序遍历的非递归函数二
voidPreOrder_N2(BTreeNode*&BT);
//中序遍历的递归函数
voidInOrder(BTreeNode*&BT);
//中序遍历的非递归函数一
voidInOrder_N1(BTreeNode*&BT);
//中序遍历的非递归函数二
voidInOrder_N2(BTreeNode*&BT);
//后序遍历的递归函数
voidPostOrder(BTreeNode*&BT);
//后序遍历的非递归函数一
voidPostOrder_N1(BTreeNode*&BT);
//后序遍历的递归函数
voidPostOrder_N2(BTreeNode*&BT);
//层序遍历的非递归函数
voidLayerOrder(BTreeNode*&BT);
//按照二叉树的广义表表示输出整个二叉树
voidGPrintBTree();
//广义表形式输出整个二叉树的递归函数,被函数Print调用
voidGPrint(BTreeNode*&BT);
//以凹凸表示法输出二叉树
voidOPrintTree();
/**********************************二叉树的属性*****************************/
/****************计算二叉数深度,宽度,叶子,结点的相关成员函数****************/
//求二叉树的深度
intBTreeDepth();
//用于求二叉树深度的递归函数,被BTreeDepth调用
intDepth(BTreeNode*&BT);
//求二叉树的宽度
intBTreeWidth();
//求二叉树中所有结点数
intBTreeCount();
//用于求二叉树所有结点数的递归函数,被函数BTreeCount调用
intCount(BTreeNode*&BT);
//求二叉树中所有叶子结点数
intBTreeLeafCount();
//用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用
intLeafCount(BTreeNode*&BT);
//输出二叉树的所有叶子结点
voidBTreeLeafPrint();
//用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用
voidLeafPrint(BTreeNode*&BT);
/***********************二叉树中从根结点到叶子结点的路径相关函数****************/
//输出从根结点到叶子结点的路径,以及最长路径
voidBTreePath();
//输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用
voidPathLeaf(BTreeNode*&BT,ElemTypepath[],intpathlen);
//求最长路径的递归函数,被函数BTreePaht调用
voidBTreeLongpath(BTreeNode*&BT,ElemTypepath[],intpathlen,ElemTypelongpath[],int&longpathlen);
//非递归方法输出从根结点到叶子结点的路径
voidBTreePath_N1();
//返回data域为x的结点指针
voidBTreeFind(ElemTypex);
//返回data域为x的结点指针的递归函数,被函数BTreeFind调用
BTreeNode*FindNode(BTreeNode*&BT,ElemTypex);
/*************************************线索二叉树****************************/
//线索化二叉树
voidCreateThread();
//中序线索化二叉树的递归函数,被函数CreateThread调用
voidInOrderThread(BTreeNode*&BT,BTreeNode*&pre);
//中序线索化二叉树中实现中序遍历,被函数CreateThread调用
voidThInOrder(BTreeNode*&BT);
/****************************销毁二叉数的相关成员函数***********************/
//置空二叉树
voidBTreeClear();
//用于清除二叉树的递归函数,被函数BTreeClear和~BinaryTree调用
voidClear(BTreeNode*&BT);
//析构函数,清除二叉树
~BinaryTree();
};
/******************************创建二叉数的相关成员函数*************************/
//按照二叉树的广义表表示创建二叉树
voidBinaryTree:
:
CreateBTree1()
{
cout<<"输入广义表形式的二叉树:
"< root=NULL;//给树根指针置空 Create1(root); } //递归创建二叉树,被函数CreateBTree1调用 voidBinaryTree: : Create1(BTreeNode*&BT) { BTreeNode*stack[MAXSIZE],*p=NULL; intk,top=-1; charch; while((ch=getchar())! ='#') { switch(ch) { case'(': top++; stack[top]=p; k=1;//即将建立左结点 break; case')': top--; break; case',': k=2;//即将建立右结点 break; default: if(! (p=newBTreeNode)) { 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 } //按一定次序输入二叉树中结点的值(一个字符),空格表示空树 voidBinaryTree: : CreateBTree2(intmark) { switch(mark) { case1: puts("按先序输入二叉树: "); break; case2: puts("按中序输入二叉树: "); break; case3: puts("按后序输入二叉树: "); break; } root=NULL;//给树根指针置空 BTreeNode*&p=root;//定义p为指向二叉树结点的指针 Greate2(p,mark); } //递归创建二叉树,被函数CreateBTree2调用 voidBinaryTree: : Greate2(BTreeNode*&BT,intmark) { charch; ch=getchar(); switch(mark) { case1: //先序创建 if(ch=='') BT=NULL; else { if(! (BT=newBTreeNode)) { cout<<"\n堆内存分配失败\n"; exit (1); } BT->data=ch; Greate2(BT->left,mark); Greate2(BT->right,mark); } break; case2: break; case3: break; } } //复制二叉树 voidBinaryTree: : BTreeCopy(BTreeNode*&root,BTreeNode*&BT) { if(root) { if(! (BT=newBTreeNode)) { exit (1); } BT->data=root->data; BTreeCopy(root->left,BT->left); BTreeCopy(root->right,BT->right); } else BT=NULL; } /*******************************遍历二叉数的相关成员函数************************/ //按任一种遍历次序输出二叉树中的所有结点 voidBinaryTree: : TraverseBTree(intmark) { srand(time(NULL));//产生随机种子数,用来选择相同顺序遍历的不同算法 Traverse(root,mark); cout< } //用于遍历的递归函数,被函数TraverseBTree调用 voidBinaryTree: : Traverse(BTreeNode*&BT,intmark) { intoption; switch(mark) { case1: //先序遍历 { option=rand()%3+1; switch(option)//随机选择一种先序算法 { case1: PreOrder(BT); break; case2: PreOrder_N1(BT); break; case3: PreOrder_N2(BT); break; } break; } case2: //中序遍历 { option=rand()%3+1; switch(option)//随机选择一种中序算法 { case1: InOrder(BT); break; case2: InOrder_N1(BT); break; case3: InOrder_N2(BT); break; } break; } case3: //后序遍历 { option=rand()%3+1; switch(option)//随机选择一种先序算法 { case1: PostOrder(BT); break; case2: PostOrder_N1(BT); break; case3: PostOrder_N2(BT); break; } break; } case4: //层序遍历 { LayerOrder(BT); break; } default: cout<<"mark的值无效! 遍历失败! "< } } //先序遍历的递归函数 voidBinaryTree: : PreOrder(BTreeNode*&BT) { if(BT! =NULL) { cout< PreOrder(BT->left); PreOrder(BT->right); } } //先序遍历的非递归函数一 voidBinaryTree: : PreOrder_N1(BTreeNode*&BT) { BTreeNode*p; struct { BTreeNode*pt; inttag; }stack[MAXSIZE]; inttop=-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< top--; } } } //先序遍历的非递归函数二 voidBinaryTree: : PreOrder_N2(BTreeNode*&BT) { BTreeNode*stack[MAXSIZE],*p; inttop=-1; if(BT! =NULL) { top++;//根结点入栈 stack[top]=BT; while(top>-1)//栈不空时循环 { p=stack[top]; top--; cout< if(p->right! =NULL)//右孩子入栈 { top++; stack[top]=p->right; } if(p->left! =NULL)//左孩子入栈 { top++; stack[top]=p->left; } }//while }//if(root! =NULL) } //中序遍历的递归函数 voidBinaryTree: : InOrder(BTreeNode*&BT) { if(BT! =NULL) { InOrder(BT->left); cout< InOrder(BT->right); } } //中序遍历的非递归函数一 voidBinaryTree: : InOrder_N1(BTreeNode*&BT) { BTreeNode*p; struct { BTreeNode*pt; inttag; }stack[MAXSIZE]; inttop=-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< top--; } } } //中序遍历的非递归函数二 voidBinaryTree: : InOrder_N2(BTreeNode*&BT) { BTreeNode*stack[MAXSIZE],*p; inttop=-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[to
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 树形