【数据结构】宜宾大学-计院-实验七

实验七二叉树

一、实验目的：
二、实验内容：
三、实验结果：
- 1,2；
- 3,4,5;
- - 6.
  - 数组顺序存储的优缺点
  - 二叉链表存储的优缺点

一、实验目的：

掌握二叉树的顺序存储结构
掌握二叉树的链式存储结构

二、实验内容：

在这里插入图片描述

1．实现用数组形式存储二叉树。
2．把上面这棵树输入到数组里存储，测试。
存储方案：
用数组顺序存储二叉树，树上的元素存放位置在数组中是固定的，如果树的i位置（从0开始按层编号）有元素，就放在数组的i号位置，没有元素，数组对应的位置就空着（为了便于观察，这里放 ‘#’ ）。i的左右子树的编号分别为2i+1和2i+2

在这里插入图片描述

3．实现二叉树的二叉链表存储
4．实现用先序，中序，后序中的任何一种输出二叉树结点
5．把上面这棵树作为输入数据，测试程序的正确性
6. 比较数组顺序存储和二叉链表存储的优缺点。
存储方案：
链表存储二叉树通常用具有两个指针域的链表作为二叉树的存储结构，每一个结点由数据域Data, 左指针域lchild和右指针域rchild组成，最后还需要一个指针指向根结点。
存储结构
typedef struct BiTNode
{
elem data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

三、实验结果：

每个同学都要记录实验结果（无论对与错），如果程序调试中有什么错误，记录并分析原因，必须另寻时间调试成功。
实验报告:（及时撰写实验报告）

1,2；

在这里插入图片描述

运行截图：
在这里插入图片描述

代码实现：

#include<iostream>
#include<stdlib.h>
#define N 11 //N = 2*n + 1(n为节点个数)
using namespace std;

typedef char type;

//定于节点结构
typedef struct BiTNode
{
	type data;
	struct BiTNode* lchild, * rchild;
}BiTNode, *BiTree;

//开辟节点
BiTree BuyNode(type x)
{
	BiTree T = new BiTNode;
	//BiTree T = (BiTree)malloc(sizeof(BiTNode));
	T->data = x;
	T->lchild = nullptr;
	T->rchild = nullptr;
	return T;
}

//手创建一个二叉树
BiTree CreateBiT1()
{
	BiTree node1 = BuyNode('1');
	BiTree node2 = BuyNode('2');
	BiTree node3 = BuyNode('3');
	BiTree node4 = BuyNode('4');
	BiTree node5 = BuyNode('5');
	node1->rchild = node2;
	node2->rchild = node3;
	node3->rchild = node4;
	node4->rchild = node5;

	return node1;
}
//将创建的二叉树按照要求存储在数组中并输出
void PreOrder(BiTree T, char arr[], int& i)
{
	if (T == nullptr)
	{
		arr[i++] = '#';
		return;
	}
	arr[i++] = T->data;
	PreOrder(T->lchild, arr, i);
	PreOrder(T->rchild, arr, i);
}

int  main()
{
	char arr[N];
	int i = 0;
	BiTree T = CreateBiT1();
	PreOrder(T, arr, i);

	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}

3,4,5;

按照要求输入如下二叉树：（为空处需要输入 ‘#’ 来结束递归）
在这里插入图片描述

运行截图：
在这里插入图片描述
代码实现：

#include<iostream>
#include<stdlib.h>
#define N 11 //N = 2*n + 1(n为节点个数)
using namespace std;

typedef char type;

//定于节点结构
typedef struct BiTNode
{
	type data;
	struct BiTNode* lchild, * rchild;
}BiTNode, *BiTree;

//开辟节点
BiTree BuyNode(type x)
{
	BiTree T = new BiTNode;
	//BiTree T = (BiTree)malloc(sizeof(BiTNode));
	T->data = x;
	T->lchild = nullptr;
	T->rchild = nullptr;
	return T;
}

//递归创建二叉树，需要按照要求输入创建
void CreateBiT2(BiTree& T)
{
	char x;
	cin >> x;
	if (x == '#')
		return;
	T = new BiTNode;
	if (T == nullptr) return;
	T->data = x;
	T->lchild = nullptr;
	T->rchild = nullptr;
	CreateBiT2(T->lchild);
	CreateBiT2(T->rchild);
}

//先序遍历
void PreOrder1(BiTree T)
{
	if (T == nullptr)
		return;
	cout << T->data << " ";
	PreOrder1(T->lchild);
	PreOrder1(T->rchild);
}

//中序遍历
void InOrder1(BiTree T)
{
	if (T == nullptr)
		return;
	InOrder1(T->lchild);
	cout << T->data << " ";
	InOrder1(T->rchild);
}

//后序遍历
void PosOrder1(BiTree T)
{
	if (T == nullptr)
		return;
	PosOrder1(T->lchild);
	PosOrder1(T->rchild);
	cout << T->data << " ";
}
int main()
{
	BiTree T;
	cout << "需要按照先序遍历输入数据来创建二插树，每个NULL节点输入'#'代替" << endl;
	CreateBiT2(T);
	cout << "按照先序遍历输出二叉树" << endl;
	PreOrder1(T);
	cout << endl << "按照中序遍历输出二叉树" << endl;
	InOrder1(T);
	cout << endl << "按照后序遍历输出二叉树" << endl;
	PosOrder1(T);
	return 0;
 }