版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/zha_ojunchen/article/details/84844598

// MyTree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
 
#include "pch.h"
#include <iostream>
#include <string>
#include <vector>//模拟栈的结构
#include<queue>//模拟队列
#include<cmath>//pow()
#include<iomanip>//setw()格式控制
#include<windows.h>
#define MAX 4//定义最大的度数
using namespace std;
//元素节点
class reflecttable {
public:
int lie;//{}所在行的列数
int related;//节点在当前组的位置{a,b,c} a:0 b:1 c:2
int data; //{}树的节点值
};
 
class Node {
public:
int data;//
Node * child[MAX];
Node(int data1 = 0);//初始化节点
~Node() {};
};
 
Node::Node(int data1) {
data = data1;
for (int i = 0; i < MAX; i++) {
child[i] = 0;
}
}
 
//三叉树类
class Tree {
public:
Node * root;//根节点
string constr;//广义表
int depth;//深度
int degree;//度数
int numbers;//树节点的数目
Tree() {//初始化
root = NULL;
numbers = 0;//节点数目
cout << "输入广义表:";
cin >> constr;
depth = getdepth();//获取深度
createTree();//构造树
}
void levelorder();
~Tree() { destory(root); };//析构函数销毁树
private:
int getdepth();
void createTree();//构造树
void destory(Node *r);//销毁树
};
int Tree::getdepth() {//利用广义表求出树的深度
int treedepth = 1;
int l = constr.length();
int sta = 1;
for (int i = 0; i < l; i++) {
if (constr[i] == '(') {
++sta;
treedepth = sta > treedepth ? sta : treedepth;
}if (constr[i] == ')') {
--sta;
}
}
cout << "这个树的深度" << treedepth;
/* code */
return treedepth;
}
 
void Tree::createTree() {
int i, j = -1, length = constr.length();//flag代表插入位置i遍历因子  j存储如入栈时孩子节点位置情况;
int *positionjudge = new int[length];//初始化所有的值为0
char c;
Node *p = NULL, *r = NULL;//r栈顶元素  p新建的当前节点
int number;//将连续的数字字符转化为正真的的数字
std::vector<Node*> Mystack;//模拟栈
for (i = 0; i < length; i++) {
c = constr[i];
switch (c) {
case '('://入栈,设置flag位置为1,代表在栈节点下flag位置插入新的节点
Mystack.push_back(p);//
j++; positionjudge[j] = 0;//位置信息入栈  孩子节点的位置设为0号
break;
case ')'://出栈
Mystack.pop_back();//出栈
j--;//出栈
break;
case ','://修改这个flag插入位置
++positionjudge[j];
degree = positionjudge[j] > degree ? positionjudge[j] : degree;//得到最大的度数
break;
default:
//数据处理
number = constr[i] - '0';
for (; constr[i + 1] <= '9'&&constr[i + 1] >= '0'; i++) {
number = number * 10 + constr[i + 1] - '0';
}//处理够早的广义表数据
p = new Node(number);//新建数据节点
++numbers;
if (root == NULL) {
root = p;//首节点
}
else {
r = Mystack.back();//栈顶元素指针
r->child[positionjudge[j]] = p;
}
}
}
degree += 1;
delete[] positionjudge;
}
 
void Tree::destory(Node *r) {//递归销毁树
if (r != NULL) {
for (int i = 0; i < degree; ++i) {
destory(r->child[i]);
}
cout << "free" << r->data << "  ";
delete r;
}
}
 
void Tree::levelorder() {//输出
Node*r = this->root;
if (r == NULL) return;//为空树时结束
// bool索引 初始化为false  所在索引有元素是 bool值设置为true
int all_id = ((pow(degree, depth) - 1) / (degree - 1));//
bool *id_bool = new bool[all_id];
int i, j;
 
for (i = 0; i < all_id; ++i) {
id_bool[i] = false;
}//初始化id
 
// 保存信息
reflecttable*table = new reflecttable[this->numbers], *temp;
int *line = new int[depth], line_iter = 0, *line_end = new int[depth];//存储每一行的首元素的数组下标志
line[0] = 0;//首行的根节点标为0
line_end[depth - 1] = numbers - 1;
int nowline = 0;//当前的行数
 
queue<Node*>Myqueue;//模拟队列
Node *q = NULL;
 
 
Myqueue.push(r);//入队  同时加入映射表
int k = 0, w = 0;//k遍历bool数组索引   w遍历table索引  
int p = (pow(degree, nowline + 1) - 1) / (degree - 1), p_old = 0;//优化运算
//开始获取元素的信息
while (!Myqueue.empty()) {//栈不为空时
q = Myqueue.front();//队首元素，k此时为元素的位置 首次循环是初始化为1
Myqueue.pop();
 
// 入栈其余数据元素   设置数据节点的位置
for (i = 0; i < degree; ++i) {
if (q->child[i] != NULL) {
Myqueue.push(q->child[i]);//入栈元素
id_bool[degree*k + i + 1] = true;
}
}
 
if (k >= p) {//当超出第i行容纳的极限是  行数增加 p更新   p的引入是的总共只需要depth次pow运算  而非循环一次 
nowline++;
p_old = p;//p_old还有用处
p = (pow(degree, nowline + 1) - 1) / (degree - 1);
line_end[line_iter] = w - 1;//存储节点   
line[++line_iter] = w;//存储当前节点的w
}
//以上我们可以得到每一行的下标范围  [line[i],line_end[i] ]
 
 
id_bool[k] = true;
temp = &table[w];
temp->lie = (k - p_old);
temp->data = q->data;
// 获取每个节点的关联节点个数 {a,b,c,d,e}这里我们只是关心首元素,其余元素的
temp->related = temp->lie%degree;
temp->lie /= degree;
 
++w;
//变化索引
++k;
while (id_bool[k] != true && k <= all_id) {//调整k，是的posi的k指向下一个元素的位置
++k;//
}//跳过没有实际元素的索引
}
table[0].related = 0;//特殊处理
 
for (i = 0; i < depth; i++) {
cout << "\nstart" << line[i] << " end" << line_end[i];
}
cout << endl << "树状输出结果如下" << endl;
//现在我要开始按照格式输出了
int width, width_, width__;//wdith最底层的输出宽度为（2degree+2）   width_ = width/(degree*2)   width__ = width/(degree)
width = ((degree << 1) + 2)*pow(degree, depth - 1 - 1);
cout << setw((width >> 1) - 1) << "{" << table[0].data << "}" << endl;
int x, y;
for (i = 1; i < depth; i++) {//从i=1输出   根节点特殊处理
j = line[i], k = line_end[i];
width = ((degree << 1) + 2)*pow(degree, depth - 1 - i);//一行的特定花括号的固定输出长度
width_ = width / (degree << 1);//每一个节点占的位宽
width__ = width_ << 1;
while (k >= j) {//这是一行的所有的元素     倒着输出
y = table[k].related;
k -= y;
cout << setw(table[k].lie*width) << "";//占位
cout << "{" << setw(width_ - 1) << table[k].data;
for (x = 1; x <= y; ++x)
cout << setw(width__) << table[k + x].data;
cout << setw(width__*(degree - y - 1)) << "" << setw(width_) << "}\r";
--k;
}
cout << "\n";//输出换行  转换到下一行
}
delete[]table;
delete[]id_bool;
delete[]line;
delete[]line_end;
}
 
int main(int argc, char const *argv[])
{
system("mode con:cols=3000 lines=100");//设置输出宽度
double totaltime;
clock_t start = clock();
Tree a;
cout << "\n树的广义表:" << a.constr << endl;;
cout << "树的度数:" << a.degree << endl;
cout << "树的高度:" << a.depth << endl;
a.levelorder();
totaltime = (double)(clock() - start) / CLOCKS_PER_SEC;
cout << "\n执行时间" << totaltime << "\npress any to exit\n" << endl;
system("PAUSE");
return 0;
}