数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究C++ 中将 N 元树编码为二叉树
假设我们有一个 N 元树。我们必须将该树编码成一个二叉树。我们还必须制作反序列化器以将二叉树反序列化为 N 元树。
因此，如果输入如下所示：
那么输出将是
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 `encode()`，它将接收根节点作为参数，
如果根节点有效，则：
返回 null
node = 一个值为根节点的新树节点
如果根节点的子节点数量不为 0，则：
node 的左子节点 := encode(根节点的 children[0])
curr = node 的左子节点
对于 i := 1，当 i < 根节点的子节点数量，更新 (i 增加 1)，执行：
node 的右子节点 := encode(根节点的 children[i])
curr := curr 的右子节点
返回 node
定义一个函数 `decode()`，它将接收根节点作为参数，
如果根节点不存在，则：
返回 NULL
node := 一个值为根节点的新节点
curr := 根节点的左子节点
当 curr 不为零时，执行：
将 decode(curr) 插入到 node 的子节点的末尾
curr := curr 的右子节点
返回 node
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
string n_ary_to_str(Node *root){
string ret = "";
if(root){
ret = ret + to_string(root->val);
if(root->children.size() > 0){
ret += "[";
for(Node* child : root->children){
ret += n_ary_to_str(child) + ", ";
}
ret += "]";
}
}
return ret;
}
class Codec {
public:
TreeNode* encode(Node* root) {
if(!root) return NULL;
TreeNode* node = new TreeNode(root->val);
if(root->children.size()){
node->left = encode(root->children[0]);
}
TreeNode* curr = node->left;
for(int i = 1; i < root->children.size(); i++){
curr->right = encode(root->children[i]);
curr = curr->right;
}
return node;
}
Node* decode(TreeNode* root) {
if(!root) return NULL;
Node* node = new Node(root->val);
TreeNode* curr = root->left;
while(curr){
node->children.push_back(decode(curr));
curr = curr->right;
}
return node;
}
};
main() {
Codec ob;
Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);
cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
cout << "Serialized Binary Tree: ";
TreeNode *root = ob.encode(&n1);
inord(root);
cout << endl;
Node *deser = ob.decode(root);
cout << "Deserialized Tree: " << n_ary_to_str(deser);
}输入
Node n5(5), n6(6); Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6); Node n2(2), n4(4); Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4);
输出
Given Tree: 1[3[5, 6, ], 2, 4, ] Serialized Binary Tree: 5 6 3 2 4 1 Deserialized Tree: 1[3[5, 6, ], 2, 4, ]
更新于：2020年7月21日
485 次浏览
广告