多叉树转二叉树C++

### 将多叉树转换为二叉树的C++实现 为了将多叉树转换成二叉树，在程序设计上通常采用孩子兄弟表示法。这种方法的核心在于利用二叉链表来表达多叉树中的父子关系以及同级节点之间的顺序关系。 #### 孩子兄弟表示法原理 在该方法下，每一个结点都拥有两个指针域：`firstchild`指向当前结点的第一个子节点；而`sibling`则用于连接同一父节点下的相邻兄弟节点。通过这种方式可以有效地模拟出一个多叉树结构[^1]。 下面是具体的C++代码实现： ```cpp #include <iostream> using namespace std; struct TreeNode { int val; TreeNode* firstChild; // 指向第一个孩子 TreeNode* sibling; // 指向下一个兄弟姐妹 }; // 构造函数初始化成员变量 TreeNode::TreeNode(int v):val(v), firstChild(nullptr), sibling(nullptr){} class MultiForkToBinaryTreeConverter { public: void convert(const vector<int>& parentList, TreeNode*& root) { if (parentList.empty()) return ; // 创建所有节点并存入哈希表以便快速访问 unordered_map<int, TreeNode*> nodesMap; for (size_t i = 0; i < parentList.size(); ++i){ nodesMap[i + 1] = new TreeNode(i + 1); } // 设置根节点 root = nodesMap[findRoot(parentList)]; // 建立父子和兄弟关系 for (size_t childIndex = 1; childIndex <= parentList.size(); ++childIndex) { int parentId = parentList[childIndex - 1]; if (parentId != -1 && nodesMap.find(childIndex) != nodesMap.end()){ auto currNode = nodesMap.at(childIndex); // 如果父亲还没有任何孩子，则直接作为第一个孩子加入 if (!nodesMap.at(parentId)->firstChild) nodesMap.at(parentId)->firstChild = currNode; else{ // 否则找到最后一个已有的孩子，并将其sibling设为当前节点 auto lastSibling = getLastSibling(nodesMap.at(parentId)); lastSibling->sibling = currNode; } } } } private: static inline size_t findRoot(const vector<int>& parents){ set<size_t> allNodes; for(auto p : parents)if(p!=-1)allNodes.insert(p); for(size_t idx=1;idx<=parents.size();++idx){ if(allNodes.count(idx)==0)return idx; } throw runtime_error("Invalid input data"); } static inline TreeNode* getLastSibling(TreeNode *node){ while(node&&node->sibling!=nullptr){ node=node->sibling; } return node; } }; ``` 此段代码实现了从给定的多叉树描述（即每个节点对应的父节点列表）到基于孩子兄弟表示法构建出来的二叉树对象的过程。其中`convert()`函数接收一个整型数组参数`parentList[]`，它记录着各个节点所属的父亲节点的信息(-1代表无父节点)，并通过一系列操作最终得到一棵以`root`为起点的新建立起来的二叉树实例[^2]。