資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告