|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 MFwxy 于 2019-12-11 10:52 编辑
大问题已经解决了，大佬看一看附件就好啦
数组访问的[2][6]明明应该为NULL，但实际上却是[3][0]的'K'。这是为啥啊？
森林的层序遍历，
TForst.h:#pragma once
#include<iostream>
#define maxn 100
#define ElemenType char
using namespace std;
struct FSNode
{
ElemenType data = NULL;
FSNode* firstchild = NULL;
FSNode* nextsibling = NULL;
};
class TForest
{
public:
TForest();
virtual ~TForest();
//输入数据
void Tree_in();
//各种遍历
void H_BL(FSNode* H);
void L_BL();
void CreatLay(FSNode* L, int layer, int num);
void T_BL(FSNode* T);
void NodeFound(FSNode* F, ElemenType n); //找到改造后的二叉树中的元素
void NodeFoundF(FSNode* F, ElemenType n, ElemenType m);
void Mchild(FSNode* F, ElemenType m);
void MaxH(FSNode* L, int layer);
void RenewTree(FSNode* T);
void CouNode(FSNode* T);
void CouLeaves(FSNode* T);
void Getdegree(FSNode* T, int layer, int dg);
void HHTri(FSNode* H, int h);
void GYB(FSNode* H);
//题目用函数
void choose();
void no0();
void no1();
void no2();
void no3();
void no4();
void no5();
void no6();
void no7();
private:
FSNode* Tdata;
};
TForest.cpp:#include "TForest.h"
ElemenType Laysort2[10][10];
int Layer = 0;
int MaxHeight = 0, degree = 0;
int num = 0;
bool flag = false;
int nNode = 0;
int nLeaves = 0;
TForest::~TForest()
{
}
TForest::TForest()//要完成"读树"以及"转化"成二叉树
{
Tdata = new FSNode;
Tdata->data = NULL;
}
void TForest::H_BL(FSNode* H)
{
cout << H->data << " ";
if (H->firstchild != NULL)
{
H_BL(H->firstchild);
}
if (H->nextsibling != NULL)
{
H_BL(H->nextsibling);
}
}
void TForest::L_BL()//记得输入当前的层数，以及最大的层数；完成之后需要重置层数和最大的层数
{
int h = 0;
int n = 0;
while (h < MaxHeight)
{
//if(Laysort2[h][n]!='#')
cout << Laysort2[h][n]<<" ";
n++;
if (Laysort2[h][n] == NULL)
{
n = 0;
h++;
}
if (Laysort2[h][0] == NULL)
{
break;
}
}
}
void TForest::CreatLay(FSNode* L, int layer, int num)//记得输入当前的层数，以及最大的层数；完成之后需要重置层数和最大的层数
{
while (Laysort2[layer][num] != NULL)
{
num+=1;
}
Laysort2[layer][num] = L->data;
if (L->nextsibling != NULL)
{
CreatLay(L->nextsibling, layer, num + 1);
}
if (L->firstchild != NULL)
{
CreatLay(L->firstchild, layer + 1, 0);
}
}
void TForest::MaxH(FSNode* L, int layer)//读得最大的深度，然后用于创建存储每一层节点的数组
{
if (L->nextsibling != NULL)
{
MaxH(L->nextsibling, layer);
}
if (L->firstchild != NULL)
{
MaxH(L->firstchild, layer + 1);
}
if (layer > MaxHeight)
{
MaxHeight = layer;
}
}
void TForest::T_BL(FSNode* T)
{
if (T->firstchild != NULL)
{
T_BL(T->firstchild);
}
if (T->nextsibling != NULL)
{
T_BL(T->nextsibling);
}
cout << T->data << " ";
}
void TForest::NodeFound(FSNode* F, ElemenType n)
{
if (F->firstchild != NULL)
{
NodeFound(F->firstchild, n);
}
if (F->nextsibling != NULL)
{
NodeFound(F->nextsibling, n);
}
if (F->data == n)
{
flag = true;
return;
}
}
void TForest::NodeFoundF(FSNode* F, ElemenType n, ElemenType m)
{
if (F->firstchild != NULL)
{
NodeFoundF(F->firstchild, n, m);
}
if (F->nextsibling != NULL)
{
NodeFoundF(F->nextsibling, n, m);
}
if (F->data == n)
{
if (F->firstchild == NULL)
{
F->firstchild = new FSNode;
F->firstchild->data = m;
}
else//反向中序遍历，找到F->firstchild的空的兄弟节点，植入新的子节点
{
Mchild(F->firstchild, m);
}
}
}
void TForest::Tree_in()
{
FSNode* c = NULL;
int i = 0, j = 0;
char a, b;
cout << "input the father and son:(enter '#' and '#' to end)" << endl;
do
{
cin >> a;
cin >> b;
if (a == '#' || '#' == b)
break;
//此时c没有数据，第一次手动录入
if (Tdata->data == NULL)
{
Tdata->data = a;
c = Tdata;
}
//第一步查找父节点a是否存在，若存在则将b加入到左子树根节点的右节点最右方（如果有的话）
//若不存在,则在当前根的右子树中加入一个a。最后将b加于a左子树根结点处
NodeFound(c, a);
if (flag)//遍历；查找到a就直接接子节点，并且跳过加载a的环节
{
NodeFoundF(c, a, b);
}
else
{//没找到a就加载a，并接入子节点.问题是要是c都没有。。。。
Mchild(c, a);
NodeFoundF(c, a, b);
}
flag = false;
} while (a != '#' && b != '#');
//数组创建完成之后直接变化成右兄弟左孩子的二叉树
}
void TForest::Mchild(FSNode* F, ElemenType m)
{
if (F->nextsibling != NULL)
{
Mchild(F->nextsibling, m);
}
if (F->nextsibling == NULL)
{
F->nextsibling = new FSNode;
F->nextsibling->data = m;
return;
}
}
void TForest::RenewTree(FSNode* T)
{
if (T->firstchild != NULL)
{
RenewTree(T->firstchild);
}
if (T->nextsibling != NULL)
{
RenewTree(T->nextsibling);
}
delete T;
T = NULL;
}
void TForest::CouNode(FSNode* T)
{
if (T->firstchild != NULL)
{
CouNode(T->firstchild);
}
if (T->nextsibling != NULL)
{
CouNode(T->nextsibling);
}
if (T->data != NULL)
{
nNode++;
}
}
void TForest::CouLeaves(FSNode* T)
{
if (T->firstchild != NULL)
{
CouLeaves(T->firstchild);
}
if (T->nextsibling != NULL)
{
CouLeaves(T->nextsibling);
}
if (T->firstchild == NULL)
{
nLeaves++;
}
}
void TForest::Getdegree(FSNode* T,int layer,int dg)
{
if (T->firstchild != NULL)
{
Getdegree(T->firstchild, layer + 1, 0);
}
if (T->nextsibling != NULL && layer != 0)
{
Getdegree(T->nextsibling, layer, dg + 1);//
}
else if (T->nextsibling != NULL && layer == 0)
{
Getdegree(T->nextsibling, layer, 0);
}
if (T->nextsibling == NULL)
{
dg++;
}
if (dg>degree)
{
degree=dg;
}
}
void TForest::HHTri(FSNode* H,int h)
{
cout <<" ( "<< H->data <<","<<h<<" ) ";
if (H->firstchild != NULL)
{
HHTri(H->firstchild,h+1);
}
if (H->nextsibling != NULL)
{
HHTri(H->nextsibling,h);
}
}
void TForest::GYB(FSNode* H)
{
cout << H->data ;
if (H->firstchild != NULL)
{
cout << "(";
GYB(H->firstchild);
cout << ")";
}
if (H->nextsibling != NULL)
{
cout << ",";
GYB(H->nextsibling);
}
}
/***********************************************************************************************************/
void TForest::choose()
{
int aa;
label1: cout << "Please choose the issue you want to solve:(enter -1 to exit)" << endl;
cin >> aa;
switch (aa)
{
case 0:
no0();
break;
case 1:
no1();
break;
case 2:
no2();
break;
case 3:
no3();
break;
case 4:
no4();
break;
case 5:
no5();
break;
case 6:
no6();
break;
case 7:
no7();
break;
case -1:
return;
default:
cout << "Wrong number!\n" << "Please choose again!" << endl;
break;
}
goto label1;
}
void TForest::no1()
{
MaxHeight = 0;
cout << "前序遍历：" << endl;
H_BL(Tdata);
cout << "\n" << "层序遍历：" << endl;
Layer = 1;
MaxH(Tdata, Layer);
Layer = 0;
CreatLay(Tdata, Layer, 0);
L_BL();
cout << "\n" << "后序遍历：" << endl;
T_BL(Tdata);
cout << endl;
}
void TForest::no2()
{
MaxHeight = 0;
Layer = 1;
MaxH(Tdata, Layer);
cout << "H: " << MaxHeight << " \n";
}
void TForest::no3()
{
nNode = 0;
CouNode(Tdata);
cout << "The number of node: " << nNode << endl;
}
void TForest::no4()
{
nLeaves = 0;
CouLeaves(Tdata);
cout << "The number of leaves: " << nLeaves << endl;
}
void TForest::no5()
{
degree = 0;
Getdegree(Tdata, 0, 0);
cout << "Degree: " << degree << endl;
}
void TForest::no6()
{
cout << "前序遍历以及对应高度：" << endl;
HHTri(Tdata, 1);
cout << endl;
}
void TForest::no7()
{
cout << "广义表：" << endl;
GYB(Tdata);
cout << endl;
}
void TForest::no0()//有BUG,最后来实现
{
RenewTree(Tdata);
Tdata->data = NULL;
Tdata->firstchild = NULL;
Tdata->nextsibling = NULL;
Tree_in();
}
main.cpp:#include <iostream>
#include"TForest.h"
using namespace std;
int main()
{
TForest a;
a.Tree_in();
a.choose();
std::cout << "Hello World!\n";
}
用的是VS2019编译
输入内容：
A B
A C
A D
B E
B F
C G
D H
D I
D J
E K
# #
1
-1
大佬看一看附件就好啦
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-12-9 10:47:36
置顶卡
千斤顶
显身卡
楼主