1. AI技术聚合首页
  2. IT

数据结构实验报告-二叉树的存储结构的实现与应用

扎眼的阳光 • • IT • 阅读 31

实验目的

熟悉二叉树结点的结构和对二叉树的基本操作。

掌握对二叉树每一种操作的具体实现。

学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

在二叉树基本操作的基础上掌握二叉树的应用。

实验要求

1． 独立完成；

2． 程序调试正确，有执行结果。

3． 程序是自己开发的，在运行结果界面上输出显示姓名。

  1. 基础题：

按照教材中关于二叉树的抽象数据类型定义，采用二叉链表存储结构，编程实现二叉树的各种基本操作，并通过主函数调用，简单测试各基本函数的正确性。

比如：二叉树的基本操作可包括：

(1) void InitBT( BTreeNode *&BT ) //初始化二叉树BT

(2) void CreateBT( BTreeNode *&BT, char *a )

//根据字符串a所给出二叉树的描述，建立二叉链表存储结构

(3) int EmptyBT( BTreeNode *BT)

//检查二叉树BT是否为空，空返回1，否则返回0

(4) int DepthBT( BTreeNode *BT) //求二叉树BT的深度并返回该值

(5) int NodeCount(BTreeNode *BT) //求二叉树BT的总结点个数

(6) void PreOrder( BTreeNode *BT) //先序遍历递归算法

(7) void InOrder( BTreeNode *BT) //中序遍历递归算法

(8) void PostOrder( BTreeNode *BT) //后序遍历递归算法

(9) int FindBT( BTreeNode *BT, ElemType x)

//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0

(10)void DestroyBT( BTreeNode *&BT ) //销毁二叉树BT

2．应用题

(1)采用二叉链表存储结构，完成二叉树的层次遍历，先序遍历的非递归算法和中序遍历的非递归算法。

(2)采用二叉链表存储结构，交换二叉树中每个结点的左孩子和右孩子。

(3)哈夫曼编码器
给定n（n=5,n=8,n=15,n=27）个字符在某个系统中出现的概率，以该n个概率做叶子结点的权值，根据Huffman算法，构造一棵哈夫曼树，给n个字符编码

3
【实验内容】1.需求分析

按照上机实验报告模板格式，写出二叉链表存储结构的二叉树的上机实验的需求分析。（不要用上传附件形式）

正确答案：

我的答案：

特性

二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2

子树有左右之分，不能颠倒——有序树

二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念

在树型结构中，二叉树的结构最简单，规律性最强；

可以证明，所有树都能转为唯一对应的二叉树。二叉树也能转换成树或森林。

普通树（多叉树）若不转化为二叉树，则运算很难实现。

4
【实验内容】2.概要设计

按照上机实验报告模板，写出二叉树的抽象数据类型定义ADT，其他模块(如果有)和函数的功能说明，本程序包含的函数列表，函数之间的调用关系。（不要用上传附件形式，调用关系可上传图片）

正确答案：

我的答案：

ADT BinaryTree {

数据对象：D 是具有相同特性的数据元素的集合。

数据关系：

 若D为空集，则称为空树。

  否则: 

  (1) 在D中存在唯一的称为根的数据元素 root；

  (2) 当n > 1时，其余结点可分为2个互不相交的有限集T1、T2，其中每一个子集本身又是一棵符合本定义的二叉树，T1称为根 root 的左子树，T2称为根 root 的右子树。

基本操作：

初始化操作

InitBiTree (&T)操作结果：构造空二叉树 T。

CreateBiTree (&T, definition)初始条件：definition 给出二叉树 T 的定义。

操作结果：按 definition 构造二叉树 T。

结构销毁操作

DestroyBiTree (&T);

初始条件：二叉树 T 存在。

操作结果：销毁二叉树 T 。

Root ( T )

初始条件：二叉树 T 存在。

操作结果：返回二叉树T的根结点。

Value ( T, e )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：返回e的值。

Parent ( T, e )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：若e是T的非根结点，则返回它的双亲，

否则返回“空”。

LeftChild ( T, e )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：返回 e 的左孩子。若 e 无左孩子，

则返回”空”。

RightChild ( T, e )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：返回 e 的右孩子。若 e 无右孩子，

                则返回"空" 。

LeftSibling ( T, e )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：返回 e 的左兄弟。若 e 是其双亲的

                左孩子或无左兄弟，则返回“空”。

RightSibling ( T, e )

初始条件：二叉树 T 存在， e 是 T 中某个结点。

操作结果：返回 e 的右兄弟。若 e 是其双亲的

                右孩子或无右兄弟，则返回"空"。

BiTreeEmpty (T);

初始条件：二叉树 T 存在。

操作结果：若T为空二叉树，则返回 TRUE，否则

返回 FALSE。

BiTreeDepth (T)

初始条件：二叉树 T 存在。

操作结果：返回 T 的深度。

PreOrderTraverse (T)——根左右（先序遍历）

初始条件：二叉树 T 存。

操作结果：先序遍历 T，对每个结点访问一次。

InOrderTraverse (T)——左根右（中序遍历）

初始条件：二叉树 T 存在。

操作结果：中序遍历 T，对每个结点访问一次。

PostOrderTraverse (T)——左右根（后序遍历）

初始条件：二叉树 T 存在。

操作结果：后序遍历 T，对每个结点访问一次。

LevelOrderTraverse (T)——（层次遍历）

初始条件：二叉树 T 存在。

操作结果：层序遍历 T，对每个结点访问一次。

Assign (&T, &e, value )

初始条件：二叉树 T 存在，e 是 T 中某个结点。

操作结果：结点 e 赋值为 value。

ClearBiTree ( &T )

初始条件：二叉树 T 存在。

操作结果：将二叉树 T 清为空树。

InsertChild ( &T, p, LR, c )

初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。

操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成为 c 的右子树。

DeleteChild (&T, p, LR);

初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。

操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。

6
【实验内容】3.详细设计

按照上机实验报告模板，写出二叉链表存储结构的上机实验的详细设计部分：

1）实现概要设计中定义的所有的数据类型；

2）对每个操作对应的各个函数给出详细的伪码。

3）对主程序和其他模块(如果有)也写出详细的伪码；

4）分析各个函数的时间复杂度和空间复杂度。(递归的除外)

二叉树的基本操作

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct binode{
	char data;
	struct binode *rchild,*lchild;
}binode,*bitree;
void init(bitree &B)  //初始化 
{
	B=NULL;
}
bool empty(bitree B)  //判断是否为空树 
{
	if(B==NULL) return true;
	return false;
} 
void creast(bitree &B)  //树的创建 
{
	char a;
	scanf("%c",&a);
	if(a=='#')  B=NULL;
	else 
	{
		B=new binode;
		if(B==NULL) exit(-2);
		B->data=a;
		creast(B->lchild);
		creast(B->rchild);
	}
}
int find1(bitree B,char a)   //判断树中是否有该数有为1无为0 
{
	int i;
	if(B==NULL) return 0;
	else if(B->data==a) return 1;
	else {
		i=find1(B->lchild,a);
		if(i!=1) return i;
		else
		{
			return find1(B->rchild,a);
		}
	}
}
bitree find2(bitree B,char a)  //找到对应节点并返回结点指针 
{
	bitree p;
	if(B==NULL) return 0;
	else if(B->data==a) return B;
	else
	{
		p=find2(B->lchild,a);
		if(p!=NULL) return p;
		else return find2(B->rchild,a);
	}
}
int depth(bitree B)  //输出树的深度 
{
	if(B==NULL) return 0;
	else 
	{
		int depthl=depth(B->lchild);
		int depthr=depth(B->rchild);
		return 1+max(depthl,depthr);
	}
} 
int node(bitree B)  //统计树的节点数 
{
	int sum1=0,sum2=0;
	if(B==NULL) return 0;
	else
	{
		sum1=node(B->lchild);
		sum2=node(B->rchild);
		return sum1+sum2+1;
	}
}
void destory(bitree &B)  //摧毁树 
{
	if(B!=NULL) 
	{
		destory(B->lchild);
		destory(B->rchild);
		delete B;
		B=NULL;
	}
}
void xxbl(bitree B) //先序遍历 
{
	if(B!=NULL)
	{
		cout<<B->data<<" ";
		xxbl(B->lchild);
		xxbl(B->rchild);
	}
}
void zxbl(bitree B)  //中序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	    cout<<B->data<<" ";
		xxbl(B->rchild);
	}
}
void hxbl(bitree B) //后序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	  	xxbl(B->rchild);
	    cout<<B->data<<" ";
 	}
}
void jh(bitree root)  //交换左右子树 
{
    if(root==NULL) return;
    else
    {
        bitree temp=root->lchild;
        root->lchild=root->rchild;
        root->rchild=temp;
        jh(root->lchild);
        jh(root->rchild);
    }
}
int main()
{
	bitree mytree,yourtree;
	init(mytree);
	init(yourtree);
/*	creast(mytree);
	xxbl(mytree);
	cout<<endl;	
	jh(mytree);
	xxbl(mytree);*/
    cout<<"树已初始化"<<endl;
	 cout<<"创建树,'#'结束"<<endl;
	creast(mytree);
	if(empty(mytree)) 
	{
		cout<<"树为空树，重新创建"<<endl;
		creast(mytree);
	}
	else{
		cout<<"二叉树非空"<<endl;
	}
	cout<<"先序遍历：";
	xxbl(mytree);
	cout<<endl;
	cout<<"中序遍历：";
	zxbl(mytree);
	cout<<endl;
	cout<<"后序遍历：";
	hxbl(mytree); 
	cout<<endl;
	cout<<"该树的深度："<<depth(mytree)<<endl;
	cout<<"该树所有结点数为："<<node(mytree)<<endl;
	char a;
	cout<<"输入一个字符进行查找"<<endl;
	cin>>a;
    if(find1(mytree,a)) 
	{
		cout<<"存在该字符"<<endl;
	    bitree p;
	    p=find2(mytree,a);
		cout<<p->data;	    
	}
    else  cout<<"不存在该字符"<<endl;
    destory(mytree);
	cout<<"程序结束摧毁树"<<endl; 
	cout<<"数据结构小二班11号刘志江"<<endl;
	return 0;
}

二叉树的遍历

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct binode{
	char data;
	struct binode *rchild,*lchild;
}binode,*bitree;
void init(bitree &B)  //初始化 
{
	B=NULL;
}
bool empty(bitree B)  //判断是否为空树 
{
	if(B==NULL) return true;
	return false;
} 
void creast(bitree &B)  //树的创建 
{
	char a;
	scanf("%c",&a);
	if(a=='#')  B=NULL;
	else 
	{
		B=new binode;
		if(B==NULL) exit(-2);
		B->data=a;
		creast(B->lchild);
		creast(B->rchild);
	}
}
int find1(bitree B,char a)   //判断树中是否有该数有为1无为0 
{
	int i;
	if(B==NULL) return 0;
	else if(B->data==a) return 1;
	else {
		i=find1(B->lchild,a);
		if(i!=1) return i;
		else
		{
			return find1(B->rchild,a);
		}
	}
}
bitree find2(bitree B,char a)  //找到对应节点并返回结点指针 
{
	bitree p;
	if(B==NULL) return 0;
	else if(B->data==a) return B;
	else
	{
		p=find2(B->lchild,a);
		if(p!=NULL) return p;
		else return find2(B->rchild,a);
	}
}
int depth(bitree B)  //输出树的深度 
{
	if(B==NULL) return 0;
	else 
	{
		int depthl=depth(B->lchild);
		int depthr=depth(B->rchild);
		return 1+max(depthl,depthr);
	}
} 
int node(bitree B)  //统计树的节点数 
{
	int sum1=0,sum2=0;
	if(B==NULL) return 0;
	else
	{
		sum1=node(B->lchild);
		sum2=node(B->rchild);
		return sum1+sum2+1;
	}
}
void destory(bitree &B)  //摧毁树 
{
	if(B!=NULL) 
	{
		destory(B->lchild);
		destory(B->rchild);
		delete B;
		B=NULL;
	}
}
void xxbl(bitree B) //先序遍历 
{
	if(B!=NULL)
	{
		cout<<B->data<<" ";
		xxbl(B->lchild);
		xxbl(B->rchild);
	}
}
void zxbl(bitree B)  //中序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	    cout<<B->data<<" ";
		xxbl(B->rchild);
	}
}
void hxbl(bitree B) //后序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	  	xxbl(B->rchild);
	    cout<<B->data<<" ";
 	}
}
void jh(bitree root)  //交换左右子树 
{
    if(root==NULL) return;
    else
    {
        bitree temp=root->lchild;
        root->lchild=root->rchild;
        root->rchild=temp;
        jh(root->lchild);
        jh(root->rchild);
    }
}
int main()
{
	bitree mytree,yourtree;
	init(mytree);
	init(yourtree);
/*     creast(mytree);
	xxbl(mytree);
	cout<<endl;	
	jh(mytree);
	xxbl(mytree);*/
    cout<<"树已初始化"<<endl;
	 cout<<"创建树,'#'结束"<<endl;
	creast(mytree);
	if(empty(mytree)) 
	{
		cout<<"树为空树，重新创建"<<endl;
		creast(mytree);
	}
	else{
		cout<<"二叉树非空"<<endl;
	}
	cout<<"先序遍历：";
	xxbl(mytree);
	cout<<endl;
	cout<<"中序遍历：";
	zxbl(mytree);
	cout<<endl;
	cout<<"后序遍历：";
	hxbl(mytree); 
	cout<<endl;
	cout<<"该树的深度："<<depth(mytree)<<endl;
	cout<<"该树所有结点数为："<<node(mytree)<<endl;
	char a;
	cout<<"输入一个字符进行查找"<<endl;
	cin>>a;
    if(find1(mytree,a)) 
	{
		cout<<"存在该字符"<<endl;
	    bitree p;
	    p=find2(mytree,a);
		cout<<p->data;	    
	}
    else  cout<<"不存在该字符"<<endl;
    destory(mytree);
	cout<<"程序结束摧毁树"<<endl; 
	cout<<"数据结构小二班11号刘志江"<<endl;
	return 0;
}

二叉树的子树交换

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct binode{
	char data;
	struct binode *rchild,*lchild;
}binode,*bitree;
void init(bitree &B)  //初始化 
{
	B=NULL;
}
bool empty(bitree B)  //判断是否为空树 
{
	if(B==NULL) return true;
	return false;
} 
void creast(bitree &B)  //树的创建 
{
	char a;
	scanf("%c",&a);
	if(a=='#')  B=NULL;
	else 
	{
		B=new binode;
		if(B==NULL) exit(-2);
		B->data=a;
		creast(B->lchild);
		creast(B->rchild);
	}
}
int find1(bitree B,char a)   //判断树中是否有该数有为1无为0 
{
	int i;
	if(B==NULL) return 0;
	else if(B->data==a) return 1;
	else {
		i=find1(B->lchild,a);
		if(i!=1) return i;
		else
		{
			return find1(B->rchild,a);
		}
	}
}
bitree find2(bitree B,char a)  //找到对应节点并返回结点指针 
{
	bitree p;
	if(B==NULL) return 0;
	else if(B->data==a) return B;
	else
	{
		p=find2(B->lchild,a);
		if(p!=NULL) return p;
		else return find2(B->rchild,a);
	}
}
int depth(bitree B)  //输出树的深度 
{
	if(B==NULL) return 0;
	else 
	{
		int depthl=depth(B->lchild);
		int depthr=depth(B->rchild);
		return 1+max(depthl,depthr);
	}
} 
int node(bitree B)  //统计树的节点数 
{
	int sum1=0,sum2=0;
	if(B==NULL) return 0;
	else
	{
		sum1=node(B->lchild);
		sum2=node(B->rchild);
		return sum1+sum2+1;
	}
}
void destory(bitree &B)  //摧毁树 
{
	if(B!=NULL) 
	{
		destory(B->lchild);
		destory(B->rchild);
		delete B;
		B=NULL;
	}
}
void xxbl(bitree B) //先序遍历 
{
	if(B!=NULL)
	{
		cout<<B->data<<" ";
		xxbl(B->lchild);
		xxbl(B->rchild);
	}
}
void zxbl(bitree B)  //中序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	    cout<<B->data<<" ";
		xxbl(B->rchild);
	}
}
void hxbl(bitree B) //后序遍历 
{
	if(B!=NULL)
	{
		xxbl(B->lchild);
	  	xxbl(B->rchild);
	    cout<<B->data<<" ";
 	}
}
void jh(bitree root)  //交换左右子树 
{
    if(root==NULL) return;
    else
    {
        bitree temp=root->lchild;
        root->lchild=root->rchild;
        root->rchild=temp;
        jh(root->lchild);
        jh(root->rchild);
    }
}
int main()
{
	bitree mytree,yourtree;
	init(mytree);
	init(yourtree);
     creast(mytree);
	xxbl(mytree);
	cout<<endl;	
	jh(mytree);
	xxbl(mytree);
    /*cout<<"树已初始化"<<endl;
	 cout<<"创建树,'#'结束"<<endl;
	creast(mytree);
	if(empty(mytree)) 
	{
		cout<<"树为空树，重新创建"<<endl;
		creast(mytree);
	}
	else{
		cout<<"二叉树非空"<<endl;
	}
	cout<<"先序遍历：";
	xxbl(mytree);
	cout<<endl;
	cout<<"中序遍历：";
	zxbl(mytree);
	cout<<endl;
	cout<<"后序遍历：";
	hxbl(mytree); 
	cout<<endl;
	cout<<"该树的深度："<<depth(mytree)<<endl;
	cout<<"该树所有结点数为："<<node(mytree)<<endl;
	char a;
	cout<<"输入一个字符进行查找"<<endl;
	cin>>a;
    if(find1(mytree,a)) 
	{
		cout<<"存在该字符"<<endl;
	    bitree p;
	    p=find2(mytree,a);
		cout<<p->data;	    
	}
    else  cout<<"不存在该字符"<<endl;
    destory(mytree);
	cout<<"程序结束摧毁树"<<endl; */
	cout<<"数据结构小二班11号刘志江"<<endl;
	return 0;
}

哈夫曼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//Huffman树的节点类
typedef struct Node
{
    char value;               //结点的字符值   
    int weight;               //结点字符出现的频度
    Node *lchild,*rchild;     //结点的左右孩子
}Node;

//自定义排序规则，即以vector中node结点weight值升序排序
bool ComNode(Node *p,Node *q)
{
    return p->weight<q->weight;
}

//构造Huffman树，返回根结点指针
Node* BuildHuffmanTree(vector<Node*> vctNode)
{
    while(vctNode.size()>1)                            //vctNode森林中树个数大于1时循环进行合并
    {
        sort(vctNode.begin(),vctNode.end(),ComNode);   //依频度高低对森林中的树进行升序排序

        Node *first=vctNode[0];    //取排完序后vctNode森林中频度最小的树根
        Node *second=vctNode[1];   //取排完序后vctNode森林中频度第二小的树根
        Node *merge=new Node;      //合并上面两个树
        merge->weight=first->weight+second->weight;
        merge->lchild=first;
        merge->rchild=second;

        vector<Node*>::iterator iter;
        iter=vctNode.erase(vctNode.begin(),vctNode.begin()+2);    //从vctNode森林中删除上诉频度最小的两个节点first和second
        vctNode.push_back(merge);                                 //向vctNode森林中添加合并后的merge树
    }
    return vctNode[0];            //返回构造好的根节点
}

//用回溯法来打印编码
void PrintHuffman(Node *node,vector<int> vctchar)
{
    if(node->lchild==NULL && node->rchild==NULL)
    {//若走到叶子节点，则迭代打印vctchar中存的编码
        cout<<node->value<<": ";
        for(vector<int>::iterator iter=vctchar.begin();iter!=vctchar.end();iter++)
            cout<<*iter;
        cout<<endl;
        return;
    }
    else
    {
        vctchar.push_back(1);     //遇到左子树时给vctchar中加一个1
        PrintHuffman(node->lchild,vctchar);
        vctchar.pop_back();       //回溯，删除刚刚加进去的1
        vctchar.push_back(0);     //遇到左子树时给vctchar中加一个0
        PrintHuffman(node->rchild,vctchar);
        vctchar.pop_back();       //回溯，删除刚刚加进去的0

    }
}

int main()
{
    cout<<"请输入要编码的字符,并以空格隔开（个数任意）："<<endl;
    vector<Node*> vctNode;        //存放Node结点的vector容器vctNode
    char ch;                      //临时存放控制台输入的字符
    while((ch=getchar())!='\n')
    {
        if(ch==' ')continue;      //遇到空格时跳过，即没输入一个字符空一格空格
        Node *temp=new Node;
        temp->value=ch;
        temp->lchild=temp->rchild = NULL;
        vctNode.push_back(temp);  //将新的节点插入到容器vctNode中
    }

    cout<<endl<<"请输入每个字符对应的频度，并以空格隔开："<<endl;
    for(int i=0;i<vctNode.size();i++)
        cin>>vctNode[i]->weight;

    Node *root = BuildHuffmanTree(vctNode);   //构造Huffman树，将返回的树根赋给root
    vector<int> vctchar;
    PrintHuffman(root,vctchar);
cout<<"数据结构小二班11号刘志江"<<endl;
    system("pause");
}

实验截图
请添加图片描述
请添加图片描述
请添加图片描述
请添加图片描述
11
【实验内容】7.小结

即心得体会，包括对算法的讨论、分析，改进设想和其它经验教训等 。

正确答案：

我的答案：

在对于树的各种基本操作时要清晰的知道停止树的条件

在对树的左右子树的交换时可以另加一棵树，也可以在原树上进行交换。

在树的大多数操作中都采用了递归的算法

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
扎眼的阳光的头像扎眼的阳光普通用户
0
上一篇 2023年12月14日
下一篇 2023年12月14日

相关推荐