第三次数据结构实验
1.新建一个 头文件BiTree.h
/*二叉树的实现：类的定义、前序、中序、后序遍历的实现、求出二叉树的结点的数目、树的深度、输出叶子结点*/
#ifndef Bitree_H
#define Bitree_H
struct BiNode
{
char data;/*结点带的数据*/
int num;/*用于存结点数*/
BiNode* lchild, * rchild;/*左孩子，右孩子*/
};
class BiTree
{
public:
/*构造树*/
BiTree()
{
cout << "请使用扩展二叉树的前序遍历输入一棵二叉树的结点的数据：" << endl;
root = Creat(root);
cout<<"该二叉树的结点数目为"<<root->num<<endl;
}
/*析构函数*/
~BiTree()
{
Release(root);
}
/*层序遍历*/
void SequenceOrder()
{
SequenceOrder(root);
}
/*前序遍历*/
void PreOrder()
{
PreOrder(root);
}
/*中序遍历*/
void InOrder()
{
InOrder(root);
}
/*后序遍历*/
void PostOrder()
{
PostOrder(root);
}
/*获取深度*/
int GetHeight()
{
return GetHeight(root);
}
/*打印叶子结点*/
void Printleaf()
{
Printleaf(root);
}
private:
BiNode* root;
BiNode* Creat(BiNode* bt);
void Release(BiNode *bt);
void SequenceOrder(BiNode *bt);
void PreOrder(BiNode *bt);
void InOrder(BiNode *bt);
void PostOrder(BiNode *bt);
int GetHeight(BiNode* bt);
void Printleaf(BiNode *bt);
};
#endif // !Bitree_H
#pragma once
/*from USC cyj*/
2.在工程“二叉链表验证实验”中新建一个源文件程序BiTree.cpp，该文件包括类BiTree中的成员函数的定义
（2）
#include<iostream>
using namespace std;
#include"Bitree.h"
int ct = 0;/*用来临时记录当前的深度*/
/*初始化二叉树*/
BiNode *BiTree::Creat(BiNode* bt)
{
char ch;
/*cout << "请使用扩展二叉树的前序遍历输入：创建的一棵二叉树的结点的数据：" << endl;*/
cin >> ch;
if (ch=='#')
{
return NULL;
}
else
{
ct++;
bt = new BiNode;
bt->data = ch;
bt->lchild = Creat(bt->lchild);
bt->rchild = Creat(bt->rchild);
}
bt->num = ct;
return bt;
}
/*销毁二叉树*/
void BiTree::Release(BiNode* bt)
{
if (bt != NULL)
{
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
}
/*前序遍历*/
void BiTree::PreOrder(BiNode* bt)
{
if (bt == NULL)
return;
else
{
cout << bt->data << " ";
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
/*中序遍历*/
void BiTree::InOrder(BiNode* bt)
{
if (bt==NULL)
{
return;
}
else
{
InOrder(bt->lchild);
cout << bt->data << " ";
InOrder(bt->rchild);
}
}
/*后序遍历*/
void BiTree::PostOrder(BiNode* bt)
{
if (bt == NULL)
return;
else
{
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout << bt->data << " ";
}
}
/*求二叉树的深度*/
int BiTree:: GetHeight(BiNode*bt) {
int cnt = 0;
if (bt) {
int l, r;
l = GetHeight(bt->lchild);
r = GetHeight(bt->rchild);
if (l > r)
cnt = l + 1;
else cnt = r + 1;
}
return cnt;
}
/*打印叶子结点*/
void BiTree::Printleaf(BiNode*bt)
{
if (bt)
{
if (!bt->rchild&&!bt->lchild)
{
cout << "叶子结点：" << (bt->data) << endl;
}
Printleaf(bt->lchild);
Printleaf(bt->rchild);
}
}
/*from USC cyj*/
3.在工程“二叉链表的验证实验”中新建一个BiTree_main.cpp问文件，该文件主要包括主函数
#include<iostream>
using namespace std;
#include"Bitree.h"
int main()
{
BiTree T;
cout << "------------前序遍历----------------" << endl;
T.PreOrder();
cout << endl;
cout << "------------中序遍历--------------" << endl;
T.InOrder();
cout << endl;
cout << "------------后序遍历--------------" << endl;
T.PostOrder();
cout << endl;
cout<<"生成树的深度为：" << T.GetHeight()<<endl;
T.Printleaf();
cout << "------------层序遍历--------------" << endl;
T.SequenceOrder();
cout << endl;
return 0;
}
/*from USC cyj*/
本次输入的实验数据为扩展二叉树的前序遍历：abd##e##c##
实验参考教材：数据结构（c++版）学习辅导与实验指导（第二版）
以上仅供参考！随时欢迎留言讨论。
求赞求赞求赞求赞~~~~~~