二、实验任务1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
三、源代码 源文件1．输入字符序列，建立二叉链表。
2．中序遍历二叉树：递归算法。
3．中序遍历二叉树：非递归算法。（最好也实现先序，后序非递归算法）
4．求二叉树的高度。
5．求二叉树的叶子数。
6．借助队列实现二叉树的层次遍历。
7．在主函数中设计一个简单的菜单，调用上述算法。
/*
实验名称：二叉树的应用
实验目的：
1．掌握二叉树的存储实现。
2．掌握二叉树的遍历思想。
3．掌握二叉树的常见算法的程序实现。
实验内容：
1．输入字符序列，建立二叉链表。
2．中序遍历二叉树：递归算法。
3．中序遍历二叉树：非递归算法。（最好也实现先序，后序非递归算法）
4．求二叉树的高度。
5．求二叉树的叶子数。
6．借助队列实现二叉树的层次遍历。
7．在主函数中设计一个简单的菜单，调用上述算法。
实验日期：2020/12/6
开发者：每天八杯水
*/
#include "BinTree.h"
int Out();
pBiTree DGCreatBinTree();//递归创建二叉树
void InOrder_Recursion();//递归中序遍历
pBiTree CreatBTree_NRecursion();//非递归创建二叉树
void InOrder_NRecursion();//非递归中序遍历
int CountLever();//统计二叉树的深度
int CoumtLeafNode();//统计二叉树的叶子数
void LevelOrder();//层次遍历二叉树
pBiTree SF();//释放空间-采用递归删除结点
int main()
{
cout << "\n";
pBiTree bt;//定义一个结点bt存放创建好的二叉树
//bt=DGCreatBinTree(); //递归创建二叉链表
bt= CreatBTree_NRecursion();//非递归创建
bool opt = true; //是否循环的一个标志
while (opt == true) {
//菜单列表
cout << "\n\t\t************************************\n";
cout << "\t\t* WELCOM TO MY WORLD *\n";
cout << "\t\t* 1. 中序遍历-递归 *\n";
cout << "\t\t* 2. 中序遍历-非递归 *\n";
cout << "\t\t* 3. 求二叉树的高度 *\n";
cout << "\t\t* 4. 求二叉树的叶子数 *\n";
cout << "\t\t* 5. 层次遍历 *\n";
cout << "\t\t* 6. 释放空间 *\n";
cout << "\t\t* 7. 退 出 *\n";
cout << "\t\t************************************\n";
//接收输入选择
cout << "\t\t请选择：";
char x;
cin >> x;
//判断用户的选择
switch (x) {
case '1':
cout << "递归中序遍历：";
InOrder_Recursion(bt);
opt = Out(); //小目录选择1返回true到循环条件时再次执行主菜单；选择2返回false退出循环
break;
case '2':
cout << "非递归中序遍历：";
InOrder_NRecursion(bt);
; opt = Out(); //小目录
break;
case '3':
cout << "该二叉树的高度为：" << CountLever(bt);
opt = Out(); //小目录
break;
case '4':
cout << "该二叉树的叶子数个数为：" << CoumtLeafNode(bt);
opt = Out(); //小目录
break;
case '5':
cout << "层次遍历该二叉树：" ;
LevelOrder(bt);
opt = Out(); //小目录
break;
case '6':
if (SF(bt)==NULL)
{
cout << "释放成功" << endl;
}
else
{
cout << "释放失败" << endl;
cout << bt->data;
}
opt = Out(); //小目录
break;
case '7':
cout << "\n\t\t你选择了6\n";
opt = false; //把标志位为假，就退出了循环
break;
default:
cout << "\n\t\t输入非法，请重新选择!\n";
break;
}
}
cout << "\n\t\t菜单已退出!\n";
}
#pragma once
#include
#include
#include
#include
using namespace std;
/*
定义小目录-进入算法后如何退出的实现
*/
int Out() {
cout << "\n";
cout << "\t\t************\n";
cout << "\t\t*1.返回菜单*\n";
cout << "\t\t*2.退出程序*\n";//退出，程序结束
cout << "\t\t************\n";
cout << "\t\t选择：";
char y;
cin >> y; //接受输入
switch (y) {
case '1':
return true;
case '2':
return false;
default:
cout << "\t\t非法输入，已返回主目录!\n";//输入其他数字无效
return true;
break;
}
}
/*
结构类型定义
*/
#define ElemType char // 元素类型
typedef struct BiTNode
{
ElemType data;
BiTNode* Lchild, * Rchild;
} BiTNode, * pBiTree;
/*
递归创建二叉链表
*/
//pBiTree DGCreatBinTree()
//{
// pBiTree bt;//根结点
// cout << "\t\t请输入字符建立二叉链表：";
// ElemType data;
// cin >> data;
// if (data == '@')
// bt = NULL;
// else
// {
// bt = (pBiTree)malloc(sizeof(struct BiTNode));
// bt->data = data;
// bt->Lchild = DGCreatBinTree();
// bt->Rchild = DGCreatBinTree();
// }
// return bt;
//}
/*
非递归创建二叉链表
*/
pBiTree CreatBTree_NRecursion()//非递归创建二叉树-需要使用链队列
{
pBiTree bt,s,p;
bt = NULL;
int count = -1;//计数器-结点编号
queuesqueue;
cout << "\t\t请输入字符创建二叉树（@代表空）以#号键结束：";
char ch;
ch = getchar();
while (ch!='#')
{
s = NULL;//这里设置的原因是：如果接下来的ch是虚结点，就会跳过赋值，那么该结构体类型的指针为空了
if (ch != '@')//判断输入的字符是正常地还是表示空的结点
{
s = (pBiTree)malloc(sizeof(BiTNode));//*************需要释放空间--递归删除结点**********
s->data = ch;
s->Lchild = s->Rchild = NULL;
}
squeue.push(s);
count++;
if (count == 0)bt = s;//根结点编号为0
else//count为奇数，是左孩子；偶数是右孩子
{
p = squeue.front();//取出-作为父结点
if(s!=NULL && p!=NULL)//
if (count % 2 == 1) { p->Lchild = s; }//如果s为@，p左孩子就是空的，奇数就把从队列中取出来的结点左孩子指向它
else { p->Rchild = s; }
if (count % 2 == 0) { squeue.pop(); } //该结点左右孩子已经赋值完毕，可以出队列了
}
ch = getchar();
}
return bt;
}
/*
递归中序
*/
void InOrder_Recursion(pBiTree bt)
{
if (bt == NULL)return;
InOrder_Recursion(bt->Lchild);
cout << bt->data;
InOrder_Recursion(bt->Rchild);
}
/*
非递归中序
*/
void InOrder_NRecursion(pBiTree bt)//需要使用栈
{
stacksstack;
pBiTree p;
p = bt;
if (p == NULL)return;
sstack.push(bt);
p = p->Lchild;
while (p||!sstack.empty())//栈为空返回的0，所以加上！
{
while (p != NULL)//一直入栈左孩子直到为空
{
sstack.push(p);
p = p->Lchild;
}//循环最后一次p为空的左孩子
p = sstack.top();//给p赋值为栈顶元素->也就是上面那个空的左孩子的父结点 所以取出来输出
sstack.pop();//因为该栈顶元素的左孩子为空，所以按照中序遍历，下一个应该是D结点，其次是R结点，
cout << p->data;
p = p->Rchild;//左孩子为空，就返回到
}
}
/*
统计二叉树的深度
*/
int CountLever(pBiTree bt)//递归思想
{
if (bt == NULL)return 0;//左孩子为空返回个数0，右孩子为空返回0.一次循环结束返回值为1
else
{
int i = CountLever(bt->Lchild);//一直递归到根结点最后一个左孩子、结束该递归条件是左孩子为空
int j = CountLever(bt->Rchild);//当上一条左孩子为空时，进入右孩子
return(i > j ? i : j) + 1;//三目运算符
}
}
/*
统计二叉树的叶子数
*/
int CoumtLeafNode(pBiTree bt)//有个数的前提条件是该结点的左右孩子都为空时个数加1
{
if (bt == NULL)return 0;
else if ((bt->Lchild == NULL) && (bt->Rchild == NULL))return 1;//只要遇见一个左右孩子都是空的结点就个数加1
else
return(CoumtLeafNode(bt->Lchild) + CoumtLeafNode(bt->Rchild));//相当于兵分两路，从根结点左孩子和右孩子分别进入
}
/*
层次遍历二叉树
*/
void LevelOrder(pBiTree bt)//使用队列思想-与非递归建立二叉树思想相同，根结点先入队列，再取队头元素为索引，若孩子不空，把索引左右孩子依次入队，该索引用了就出队
{
queuesqueue;
if (bt == NULL)return;
pBiTree p;
p = bt;
squeue.push(bt);
while (!squeue.empty())//栈空循环结束
{
p = squeue.front();
squeue.pop();
cout << p->data;
if(p->Lchild != NULL)//左孩子入队列
squeue.push(p->Lchild);
if(p->Rchild != NULL)//紧接着右孩子入队列
squeue.push(p->Rchild);
}
}
pBiTree SF(pBiTree bt)
{
if (bt == NULL)return bt;
SF(bt->Lchild);
//cout << bt->data;
SF(bt->Rchild);
free(bt);
bt = NULL;//
return bt;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）