最近在准备考研阅读王道数据结构单科书时看到一个问题问题是给定一棵树(不一定是二叉树)所有节点的层次次序序列和度数创建该树的子女右兄弟链表示书中给出的参考答案略显繁琐所以自己考虑了一个算法运用层次次序的特点和队列解决问题。尽管代码简单但详述这一算法非常费劲可能吃力不讨好如果想要理解这一算法可以选较简单的测试样例自己手动模拟一遍这样效果可能更好。#includepch.h#includedeque#includestring#includevector#includeiostreamusingnamespacestd;structChildRightBrotherNode//子女右兄弟链节点{chardata;//数据域ChildRightBrotherNode*first_childnullptr;//长子指针ChildRightBrotherNode*next_siblingnullptr;//右兄弟指针ChildRightBrotherNode(chard):data(d){}};structDequeNode{ChildRightBrotherNode*tree_node;//每一层的树节点指针string::size_type degree;//该树节点的度数DequeNode(ChildRightBrotherNode*t,intd):tree_node(t),degree(d){}};voidpreOutPut(ChildRightBrotherNode*root){if(root!nullptr){coutroot-data;preOutPut(root-first_child);preOutPut(root-next_sibling);}}voidinOrderOutPut(ChildRightBrotherNode*root){if(root!nullptr){inOrderOutPut(root-first_child);coutroot-data;inOrderOutPut(root-next_sibling);}}intmain(){dequeDequeNodework_queue;vectorpairchar,string::size_typenode_degree_array{{A,3},{B,2},{C,1},{D,2},{E,0},{F,0},{G,0},{H,0},{I,0}};//节点数据域-度数数组各树节点从左到右按层次序排列string::size_type i0;ChildRightBrotherNode*rootnewChildRightBrotherNode(node_degree_array[0].first);//创建根节点work_queue.push_back(DequeNode(root,node_degree_array[0].second));//根节点及其度数入队while(work_queue.empty()false)//队列不为空重复迭代{DequeNode pwork_queue.front();//出队一个队列节点work_queue.pop_front();ChildRightBrotherNode*qp.tree_node;//获取当前层的树节点指针string::size_type j1;for(;jp.degree;j)//将当前树节点的所有子女节点以右兄弟链的形式链接至当前树节点{if(j1){q-first_childnewChildRightBrotherNode(node_degree_array[ij].first);//创建当前树节点的长子节点work_queue.push_back(DequeNode(q-first_child,node_degree_array[ij].second));//长子节点及度数入队qq-first_child;}else{q-next_siblingnewChildRightBrotherNode(node_degree_array[ij].first);//创建当前树节点长子节点之后的兄弟节点work_queue.push_back(DequeNode(q-next_sibling,node_degree_array[ij].second));//兄弟节点及度数入队qq-next_sibling;}}iij-1;//将i更新为当前树节点的直接子女节点中最右侧的子女节点在node_degree_array数组中的下标}cout普通树的先根次序序列为:;preOutPut(root);//先序遍历子女右兄弟链输出先根次序序列coutendl;cout普通树的后根次序序列为:;inOrderOutPut(root);//中序遍历子女右兄弟链输出后根次序序列coutendl;}