多叉树的创建及其树形输出
版权声明:本文为博主原创文章,遵循 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; }