数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++二叉树的简洁编码
假设我们有一个二叉树。众所周知，二叉树的简洁编码接近最低可能的存储空间。第n个卡塔兰数由具有n个不同节点的结构不同的二叉树的数量决定。如果n很大，则约为4n；因此，我们需要至少约log2(4)n = 2n位来对其进行编码。因此，简洁的二叉树将消耗2n + O(n)位。
所以，如果输入是这样的：
那么输出将是：
编码：
结构列表：1 1 1 0 0 1 0 0 1 0 1 0 0
数据列表：10 20 40 50 30 70
解码：如上所示的树。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数Encode()，它将接收根节点、名为struc的列表和名为data的列表作为参数。
- 如果根节点等于NULL，则：
- 在struc的末尾插入0
- 返回
- 在struc的末尾插入1
- 在data的末尾插入根节点的值
- Encode(根节点的左子节点, struc, data)
- Encode(根节点的右子节点, struc, data)
- 定义一个函数Decode()，它将接收名为struc的列表和名为data的列表作为参数。
- 如果struc的大小小于等于0，则：
- 返回NULL
- vb := struc的第一个元素
- 从struc中删除第一个元素
- 如果b等于1，则：
- key := data的第一个元素
- 从data中删除第一个元素
- root = 创建一个具有key值的新节点
- root的左子节点 := Decode(struc, data)
- root的右子节点 := Decode(struc, data)
- 返回root
- 返回NULL
示例 (C++)
让我们看看下面的实现来更好地理解：
#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 Encode(TreeNode *root, list<bool>&struc, list<int>&data){
if(root == NULL){
struc.push_back(0);
return;
}
struc.push_back(1);
data.push_back(root->val);
Encode(root->left, struc, data);
Encode(root->right, struc, data);
}
TreeNode *Decode(list<bool>&struc, list<int>&data){
if(struc.size() <= 0)
return NULL;
bool b = struc.front();
struc.pop_front();
if(b == 1){
int key = data.front();
data.pop_front();
TreeNode *root = new TreeNode(key);
root->left = Decode(struc, data);
root->right = Decode(struc, data);
return root;
}
return NULL;
}
void preorder_trav(TreeNode* root){
if(root){
cout << "key: "<< root->val;
if(root->left)
cout << " | left child: "<< root->left->val;
if(root->right)
cout << " | right child: "<< root->right->val;
cout << endl;
preorder_trav(root->left);
preorder_trav(root->right);
}
}
main() {
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(20);
root->right = new TreeNode(30);
root->left->left = new TreeNode(40);
root->left->right = new TreeNode(50);
root->right->right = new TreeNode(70);
cout << "The Tree\n";
preorder_trav(root);
list<bool> struc;
list<int> data;
Encode(root, struc, data);
cout << "\nEncoded Tree\n";
cout << "Structure List\n";
list<bool>::iterator si; // Structure iterator
for(si = struc.begin(); si != struc.end(); ++si)
cout << *si << " ";
cout << "\nData List\n";
list<int>::iterator di; // Data iIterator
for(di = data.begin(); di != data.end(); ++di)
cout << *di << " ";
TreeNode *newroot = Decode(struc, data);
cout << "\n\nPreorder traversal of decoded tree\n";
preorder_trav(newroot);
}输入
root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70);
输出
The Tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70 Encoded Tree Structure List 1 1 1 0 0 1 0 0 1 0 1 0 0 Data List 10 20 40 50 30 70 Preorder traversal of decoded tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70
更新于：2020年8月27日
298 次浏览
广告