1.二叉树的性质：
- 第i层最多有2^(i-1)个节点，当然i>=1的。
- 深度为k的二叉树最多有2^k-1个节点。
- 对任何一棵二叉树T，如果其终端的节点为n0，度为2的节点为n2，则n0=n2+1。也就是叶子结点的数量=有两个儿子的非叶子节点+1。总的分支线为（n-1）条。n-1=2*n2 + 1*n1。树T的节点总数为n=n0+n1+n2。可以推导出n0=n2+1。
- 具有n个节点的完全二叉树的深度为floor( log2(n) )+1
- 具有n个节点的完全二叉树，节点按照层的编号（从第一层到第floor(log2(n))+1层，每层从左到右），对于任意的节点i（1<=1<=n）：1）如果i=1，则节点i时二叉树的根。2）如果2*i>n则节点没有左孩子；否则其左孩子节点为2*i。3）如果2*i+1>n，则节点没有有儿子，否则其左孩子节点为2*i+1。4）这个性质对于二叉堆的实现特别有用哦。（要注意一下：如果i从0开始，且<n，那么i的父亲为floor((i-1)/2)，i的左孩子是2*i+1哦）：）
- 树的高度：从节点x向下到某一个叶节点的最大的简单路径的边条数。求任意的节点的深度就可以从左右儿子两边时，向上到达节点，那个最大高度就是他。
- 树的深度：感觉就是所在的层数（待查证）
- 最深叶节点的深度就是树的深度，树根节点的高度就是树的高度。
2.二叉树有哪些？
- 满二叉树：所有的非叶子节点的度为2，且所有的叶子结点都在同一层上，就是满二叉树。
- 完全二叉树：1）叶子只出现在最下两层。2）最下层的叶子一定集中在左部连续的位置。3）倒数二层，若有叶子结点，一定在右部的连续位置。4）如果节点度为1，则节点只有左孩子。5）同样节点的二叉树，完全二叉树的深度最小。如何判断？一颗深度为k二叉树，有n个节点，然后，也对这棵树进行按层从左向右编号，如果所有的编号都和满二叉树对应，那么这棵树是完全二叉树。如果出现编号空挡，就不是完全二叉树。
3.前序遍历、中序遍历和后续遍历：PLR、LPR和LRP，P表示根节点、L左子树或左儿子、R右子树或右儿子。
4.线索化：对于n个节点的二叉树，存在2*n-(n-1)=n+1空闲的个指针域。所以希望利用这些空闲的指针域。对于建立中序遍历的线索树：需要沿着他的遍历方向（所以建立的过程类似于中序遍历），但需要同时修改pre前驱。前驱和后继就是所谓的线索，一般而言空的左子树的指针域为前驱，右子树的为后继。访问呢的时候，和中序一样递归到最左的儿子，然后以此为起点进行遍历，但是需要注意的是，每次访问右子树的时候需要将以右子树为下一个循环的起点。这样可以极大的缩短遍历的时间。
5.二叉树以及三种便利、线索化的实现：
#include <stack>
#include <iostream>
#include <queue>
using namespace std;
template<typename T>
class BinaryTreeNode
{
typedef T DataType;
typedef BinaryTreeNode<DataType> NodeType;
typedef NodeType *Node;
public:
BinaryTreeNode():leftchild(nullptr),rightchild(nullptr){}
BinaryTreeNode(DataType da,Node l=nullptr,Node r=nullptr):leftchild(l),rightchild(r),data(da){}
//获取
DataType &getData()
{
return data;
}
//设置左儿子
void setLeftchild(Node l) { leftchild = l; }
//设置右儿子
void setRightchild(Node r) { rightchild = r; }
//获取左儿子
Node getLeftchild() { return leftchild; }
//获取右儿子
Node getRightchild() { return rightchild; }
//析构函数 Node由管理类释放
~BinaryTreeNode(){}
//获取左儿子的状态 是否是线索（前驱）
bool getLeftchildStatus()
{
return leftThread;
}
//获取右儿子的状态 是否是线索（后继）
bool getRightchildStatus()
{
return rightThread;
}
//设置左儿子的状态 是否是线索（前驱）
void setLeftchildStatus(bool status)
{
leftThread = status;
}
//设置右儿子的状态 是否是线索（后继）
void setRightchildStatus(bool status)
{
rightThread = status;
}
private:
Node leftchild;
Node rightchild;
DataType data;
//这是用来线索化的二叉树标志
bool leftThread=false;
bool rightThread=false;
};
template<typename T> class BinaryTreeList
{
public:
//类型别名
typedef T DataType;
typedef BinaryTreeNode<DataType> NodeType;
typedef NodeType *Node;
//构造函数
BinaryTreeList(DataType init) :root(new NodeType) { root->getData() = init; }
//各种操作
//访问
//获取根节点
Node &getRoot() { return root; }
DataType &Retrieve(Node node) { return node->getData(); }
//更改
//插入右子节点
void insert_right(Node parent,DataType da)
{
Node nd = new NodeType(da);
nd->setRightchild(parent->getRightchild());
parent->setRightchild(nd);
}
//插入左子节点
void insert_left(Node parent,DataType da)
{
Node nd = new NodeType(da);
nd->setLeftchild(parent->getLeftchild());
parent->setLeftchild(nd);
}
//删除节点
//注意要判断删除的是叶子还是非叶子
void erase_left(Node node)
{
destroy(node->getLeftchild());
node->setLeftchild(nullptr);
}
void erase_right(Node node) { destroy(node->getRightchild()); node->setRightchild(nullptr); }
//释放所有节点
void clear()
{
destroy(root);
root = nullptr;
}
~BinaryTreeList() { clear(); }
//遍历
//前序遍历
void PreOrder(Node p)
{
if (p != nullptr)
{
cout << p->getData() << " ";
PreOrder(p->getLeftchild());
PreOrder(p->getRightchild());
}
}
void PreOrder_Stack(Node p)
{
std::stack<NodeType*> sta;
Node root = p;
while (sta.empty() == false || root != nullptr)//只要栈不为空 那么就要
{
while (root)
{
sta.push(root);
cout << root->getData() << " ";
root = root->getLeftchild();
}
root = sta.top();//此时的top是深度最大的左叶子
sta.pop();//把那个将要访问的pop
root = root->getRightchild();//将要访问的叶子节点的父节点的值 左儿子已经处理过了 所以这个root要被更新为父节点的右儿子然后在对右儿子进行处理
}
cout << endl;
}
//中序遍历
void InOrderTraverse(Node root)
{
if (root != nullptr)
{
InOrderTraverse(root->getLeftchild());
cout << root->getData() << " ";
InOrderTraverse(root->getRightchild());
}
}
void InOrderTraverse_Stack(Node root)
{
stack<Node> nodes;
Node p = root;
while (!nodes.empty() || p != nullptr)
{
while (p)
{
nodes.push(p);
p = p->getLeftchild();
}
if (nodes.empty() == false)
{
p = nodes.top();
cout << p->getData() << " ";
nodes.pop();
p = p->getRightchild();
}
}
cout << endl;
}
//后续遍历
void PostOrderTraverse(Node p)
{
if (p != nullptr)
{
PostOrderTraverse(p->getLeftchild());
PostOrderTraverse(p->getRightchild());
std::cout << p->getData() << " ";
}
}
void PostOrderTraverse_Stack(Node root)
{
stack<Node> sta;
Node p = root;
Node prev = nullptr;
while (!sta.empty() || p != nullptr)
{
while (p)
{
sta.push(p);
p = p->getLeftchild();
}
p = sta.top();
//分析当前的栈顶元素 此时是没有左儿子的
if (p->getRightchild() ==nullptr /*叶子节点直接访问*/|| p->getRightchild() ==prev/*如果左儿子为null 而且右儿子先前被访问过（说明要访问该节点（LR的父亲））*/)
{
cout << p->getData() << " ";
prev = p;
sta.pop();//将这个节点从栈中pop
p = nullptr;//将p设置为nullptr是为了不要又开始搜索左儿子 应该访问栈顶了
}
else
{
//sta.pop();
p = p->getRightchild();//不满足条件 那么应该继续搜索右儿子
}
}
cout << endl;
}
//层次遍历
void LevelOrderTraverse(Node root)
{
queue<Node> que;
Node p = root;
if (p != nullptr)
{
que.push(p);//首元素入队
while (!que.empty()) //只要队列不为空的话
{
p = que.front();//获取对头元素
cout << p->getData() << " ";
que.pop();//出对 将对头元素转移到与之同级的右节点上 然后该节点的左右子树分别入队
if (p->getLeftchild())
que.push(p->getLeftchild());
if (p->getRightchild())
que.push(p->getRightchild());
}
}
cout << endl;
}
//线索化操作
//建立前序搜索关联
void InOrderThread(Node root)
{
Node pre = nullptr;//这个指针总是保存之前访问的位置
InOrderThread_Process(root, pre);
}
//中序线索遍历
void Display_InOrderThread(Node root)
{
for (Node p = InOrder_FindFirst(root); p != nullptr; p = InOrder_NextNode(p))
cout << p->getData() << " ";
cout << endl;
}
// 前序搜索建立
//建立前序搜索关联
void PreOrderThread(Node root)
{
Node pre = nullptr;//这个指针总是保存之前访问的位置
PreOrderThread_Process(root, pre);
}
//前序线索树显示
void Display_PreOrderThread(Node root)
{
Node d = root;
while (d != nullptr)
{
cout << d->getData() << " ";
d = PreOrder_NextNode(d);
}
cout << endl;
}
//后续线索化
void PostOrderThread(Node root)
{
Node pre = nullptr;
PostOrderThread_Process(root, pre);
}
//显示线索化
void Display_PostOrderThread(Node root)
{
Node p = PostOrderThread_FindFirstNode(root);
while (p != nullptr)
{
cout << p->getData() << " ";
p = PostOrderThread_NextNode(p);
}
cout << endl;
}
//清除指定根节点以及他的子树的线索信息
void clearAllThreads(Node r)
{
if (r != nullptr)
{
clearAllThreads(r->getLeftchild());
clearAllThreads(r->getRightchild());
if (r->getLeftchildStatus() == true)
{
r->setLeftchildStatus(false);
r->setLeftchild(nullptr);
}
if (r->getLeftchildStatus() == true)
{
r->setRightchild(nullptr);
r->setRightchildStatus(false);
}
}
}
private:
Node root;//保存根节点
void destroy(Node r)
{
if (r != nullptr)
{
if (r->getLeftchildStatus() == false)//如果不是修改后的指针域才会释放他们 避免二次释放
{
destroy(r->getLeftchild());
}
if (r->getRightchildStatus() == false)
{
destroy(r->getRightchild());
}
delete r;
}
}
//中序线索化 私有函数
void InOrderThread_Process(Node root, Node &pre)
{
if (root != nullptr)
{
InOrderThread_Process(root->getLeftchild(), pre);//遍历左子树
if (root->getLeftchild() == nullptr)
{
//没有左孩子
root->setLeftchildStatus(true);
root->setLeftchild(pre);//将左孩子的指正改为前驱 指向树的前驱节点（也就是pre）
}
if (pre!=nullptr /*这个要判断*/ &&pre->getRightchild() == nullptr)
{
//前一个节点没有右孩子
pre->setRightchildStatus(true);
pre->setRightchild(root);
}
pre = root;//这个pre是一个引用 所以能够保证指向的是root!=nullptr的前一个节点
InOrderThread_Process(root->getRightchild(), pre);//如果没有右儿子 那么会自动结束当前的递归 从而可以把root定位到原root的父节点 pre已经更新到root
}
}
//寻找中序遍历的起点 最左的左儿子
Node InOrder_FindFirst(Node o)
{
if (o != nullptr)
{
Node first = o;
while (first->getLeftchildStatus() == false)
first = first->getLeftchild();
return first;
}
else
{
return nullptr;
}
}
//寻找中序遍历后续的节点 可能是右儿子(因为是中序遍历)或者是指定的后继
Node InOrder_NextNode(Node p) {
if (p == nullptr)
{
return nullptr;
}
else
{
if (p->getRightchildStatus() == false) return InOrder_FindFirst(p->getRightchild());//右子树的第一个结点（右子树的最左的儿子）
else return p->getRightchild();//或后继
}
}
//寻找前序线索遍历的下一个节点
Node PreOrder_NextNode(Node p) {
if (p == nullptr)
{
return nullptr;
}
else
{
if (p->getLeftchildStatus() == false)//如果左儿子不是空的话 返回的下一个节点就是左儿子
{
return p->getLeftchild();
}
else
{
return p->getRightchild();//如果左儿子为空的话（此时节点指的是前驱）那么就返回他的右儿子
}
}
}
//前序线索便利构造
void PreOrderThread_Process(Node root, Node &pre)
{
if (root != nullptr)
{
if (root->getLeftchild() == nullptr)
{
//没有左儿子 那这个左儿子域就用来保存前驱节点的指针
root->setLeftchildStatus(true);
root->setLeftchild(pre);
}
if (pre && pre->getRightchild() == nullptr)//前一个结点没有指针的位置 那么就让他指向下一个节点
{
pre->setRightchildStatus(true);
pre->setRightchild(root);
}
pre = root;
if (root->getLeftchildStatus() == false)//如果还有左儿子 那么也需要对左儿子建立线索
{
PreOrderThread_Process(root->getLeftchild(), pre);
}
if (root->getRightchildStatus() == false)//如果还有左右儿子 那么也需要对右儿子建立线索
{
PreOrderThread_Process(root->getRightchild(), pre);
}
}
}
//后续线索遍历
void PostOrderThread_Process(Node root, Node &pre)
{
if (root != nullptr)
{
if (root->getLeftchildStatus() == false)
PostOrderThread_Process(root->getLeftchild(), pre);
if (root->getRightchildStatus() == false)
PostOrderThread_Process(root->getRightchild(), pre);
if (root->getLeftchild() == nullptr)
{
root->setLeftchild(pre);
root->setLeftchildStatus(true);
}
if (pre !=nullptr && pre->getRightchildStatus() == false)
{
pre->setRightchild(root);
pre->setRightchildStatus(true);
}
pre = root;
}
}
Node PostOrderThread_FindFirstNode(Node nd)
{
if (nd != nullptr)
{
//用来寻找最深层的节点
while (nd->getLeftchild())
nd = nd->getLeftchild();
return nd;
}
else
{
return nullptr;
}
}
//后续线索的下一个节点
Node PostOrderThread_NextNode(Node root)
{
if (root != nullptr)
{
if (root->getRightchildStatus() == false)
{
//存在右儿子
if (root->getLeftchildStatus() == false)//如果存在左儿子的话 也就是到达了第一个有两个儿子的节点 那么我们认为他是不需要遍历的节点
{
return nullptr;
}
else
{
return PostOrderThread_FindFirstNode(root->getLeftchild());//存在右儿子 左儿子是前驱 那么我们就搜索他的子树 从最低的左儿子开始遍历
}
}
else
{
return root->getRightchild();//右儿子是后继 直接返回右儿子
}
}
else
{
return nullptr;
}
}
};
6.哈夫曼树：最优二叉树，每次选取频数最小的两个子树或者节点，构建一颗二叉树，然后放入优先队列中。频数最大的节点就会出现在数离根节点最近的地方。所以他的字符映射的长度就会是最小的
#include <algorithm>
#include <map>
#include <vector>
#include <utility>
#include <unordered_map>
#include <queue>
#include <iostream>
#include <tchar.h>
#include <string>
using namespace std;
class HuffmanTreeNodeBase {
public:
//构造函数必须提供频数或频数之和
HuffmanTreeNodeBase(int f) :flag(f) {}
//获取flag值 对于叶子节点派生类这个保存的是频数 对于节点保存的是两个flag的频数纸盒之和
int getFlag() const {
return flag;
}
//设置flag
void setFlag(int w) {
flag = w;
}
virtual ~HuffmanTreeNodeBase() {}
private:
int flag;//表示这个节点的值
};
class HuffmanLeafTree :public HuffmanTreeNodeBase {
public:
//必须提供叶子节点频数和代表的字符
HuffmanLeafTree(int f, char c) :HuffmanTreeNodeBase(f), ch(c) {}
//获取叶子节点代表的字符
char getChar() {
return ch;
}
//设置叶子节点代表的字符
void setChar(char c) {
ch = c;
}
~HuffmanLeafTree() {}
private:
char ch;//这个表示叶子节点的被编码的符号
};
class HuffmanTreeNode : public HuffmanTreeNodeBase {
typedef HuffmanTreeNodeBase *Node;
public:
//提供频数和频数之和 左儿子节点指针 右儿子节点指针
HuffmanTreeNode(int flag, Node l, Node r) :HuffmanTreeNodeBase(flag), left(l), right(r) {}
~HuffmanTreeNode() {
delete left; //析构函数
delete right;
}
//获取左儿子节点指针
Node getLeftchild() {
return left;
}
//获取右儿子节点指针
Node getRightchild() {
return right;
}
private:
Node left;
Node right;
};
class Huffman {
public:
typedef std::map<char, int> Charfrenquent;//这个用来保存被编码的字符的出现的频数
typedef std::vector<int> Encoding;//这个用来保存一组哈夫曼编码
typedef std::map<char, Encoding> CharMap;//这个用来保存对应字符的编码表
//构造函数
Huffman() {}
//这个用来整理map 频率最小的排在前面 现在已经不使用
void sortMap(std::unordered_map<char, int> &ma) {
std::vector<std::pair<char, int>> res;
for (auto iter = ma.begin(); iter != ma.end(); ++iter)
res.push_back(std::make_pair(iter->first, iter->second));
std::sort(res.begin(), res.end(),
[](const std::pair<char, int> &c1, std::pair<char, int> &c2) {
return c1.second < c2.second;
}
);
//重新排序
ma.clear();
for (auto i = res.cbegin(); i != res.cend(); ++i)
ma[i->first] = i->second;
}
//这个函数用来计算字符出现的频率 第三个参数是输出的保存字符对应平频率的映射表
void calcFrenquentofChars(const char *c, int size, Charfrenquent &cf) {
if (c != nullptr && size > 0) {
for (int i = 0; i < size; ++i) {
cf[c[i]]++;
}
//sortMap(cf);
}
}
//这个用来生成哈夫曼树 需要获取已知的频率映射表 生成的树依据最优二叉树的规则
HuffmanTreeNodeBase *buildHuffmanTree(Charfrenquent &cf) {
auto j = [](const HuffmanTreeNodeBase *c1, const HuffmanTreeNodeBase *c2) {
return c1->getFlag() > c2->getFlag();/*如果返回的是true表示后面的频数比前面的小 那么就需要吧后面的和前面的交换顺序*/
};//这个用来设置优先队列最先出出对的佘顺序 依据的是频数 频数最小的先出来
std::priority_queue < HuffmanTreeNodeBase*, std::vector<HuffmanTreeNodeBase*>, decltype(j)> trees(j);
for (auto i = cf.begin(); i != cf.end(); ++i)
trees.push(new HuffmanLeafTree(i->second, i->first));
//优先队列
while (trees.size() > 1) {
//从优先队列出来是频数最小的字符
HuffmanTreeNodeBase *le = trees.top();
trees.pop();
HuffmanTreeNodeBase *ri = trees.top();
trees.pop();
HuffmanTreeNode *nd = new HuffmanTreeNode(le->getFlag() + ri->getFlag(), le, ri);//新建的一个Node节点 由于是base的派生类 所以指针是可以插入的
trees.push(nd);//把这个节点插入优先队列
}
return trees.top();
}
//这个用来生成哈夫曼编码 charmap输出的就是字符对应的编码 用vector保存 第三个参数用来验证是否只存在一个编码的情况
void genrateCode(HuffmanTreeNodeBase *tree, CharMap &cm, Charfrenquent &fren) {
Encoding enc;//这个是用于临时保存的vector
if (fren.size() == 1) {
enc.push_back(0);
}
else {
if (fren.size() <= 0)
return;
}
do_genrateCode(tree, enc, cm);
}
std::string deCoding(CharMap &cm, std::string &encodedstr) {
std::string result;
std::map<std::string, char> reverseMap;
for (CharMap::const_iterator it = cm.cbegin(); it != cm.cend(); ++it) {
std::string k;
for (Encoding::const_iterator i = it->second.cbegin(); i != it->second.cend(); ++i)
k.push_back(*i + '0');//将vector中的编码序列变成字符串的形式 注意int和char类型的互换
reverseMap.insert(std::make_pair(k, it->first));//将键值对插入map
}
//反向映射表建立完成
auto beg = encodedstr.cbegin();
auto end = encodedstr.cend();
auto range = ++encodedstr.cbegin();//这个表示范围的有开区间 我们将会从[Beg,range) 中构建查找的字符串 beg！=range 否则为空字符串
int cnt = 0;//cnt计数用于吧beg递增到最近一次匹配位置的尾后
while (beg != end) {
char dest;
bool changeres = match_str(reverseMap, beg, range, dest);//查找
if (changeres == true) {
result.push_back(dest);
for (int i = 0; i <= cnt; ++i) {
++beg;
}
if (range == end)//如果此时的匹配之后range的位置是尾后 那么表示这是最后一次成功的匹配 就结束while
break;
range = beg + 1;//range>beg
cnt = 0;//cntc重新开始计数
}
else {
++cnt;//如果匹配失败 那么一旦匹配成功那么bg会递增到beg+cnt+1的位置
++range;//范围也要递增
}
}
return result;
}
~Huffman() {}
private:
void do_genrateCode(HuffmanTreeNodeBase *tree, Encoding &precode, CharMap &charmap) {
if (tree == nullptr)
return;
HuffmanLeafTree *leaf = dynamic_cast<HuffmanLeafTree*>(tree);
if (leaf) {
//表示这个指针是叶子节点 那么就设置该字符的编码 编码保存在int的vector中
charmap[leaf->getChar()] = precode;
}
else {
HuffmanTreeNode *nd = dynamic_cast<HuffmanTreeNode*>(tree);
if (nd) {
//表示这是节点 所以还是必须把编码压入vector
Encoding leftcode = precode;//这里定义一个新的vector他是用来防止不同的vector编码冲突的问题
leftcode.push_back(0);//做儿子的话 路径上的权为0
do_genrateCode(nd->getLeftchild(), leftcode, charmap);//从左儿子开始 递归
Encoding rightcode = precode;//解释同上
rightcode.push_back(1);
do_genrateCode(nd->getRightchild(), rightcode, charmap);
}
}
}
//这个用来寻找哈夫曼序列对应的字符 第一个参数是映射表 [beg,end） 注意beg ！=end 表示要匹配的迭代器范围
bool match_str(std::map<std::string, char> reverseMap, string::const_iterator beg_match, std::string::const_iterator end_match, char &res) {
std::string s(beg_match, end_match);//构建一个临时的字符串
auto r = reverseMap.find(s);//根据字符串查找对应的哈夫曼字符映射
if (r == reverseMap.end()) { //如果没有找到的话 返回的是end迭代器
return false;
}
else {
res = r->second;//找到了映射
return true;
}
}
};
int main() {
const char *c;
int sz;
cout << "请输入要编码的序列：";
std::string s;
cin >> s;
c = s.c_str();
sz = s.size();
Huffman hmf;//哈夫曼对象
Huffman::Charfrenquent hmf_freq;//字符出现的频数
hmf.calcFrenquentofChars(c, sz, hmf_freq);
HuffmanTreeNodeBase *tree = hmf.buildHuffmanTree(hmf_freq);//得到地哈夫曼树
Huffman::CharMap hmf_map;//哈夫曼映射表
hmf.genrateCode(tree, hmf_map, hmf_freq);
delete tree;
int orgsz = 0;
int zipsz = 0;
//计算应该的长度
int cnt = 0;
int weight = 1;
int t = hmf_map.size();
while (1) {
if (t == 1) {
cnt = 1;
break;
}
if (t - weight <= 0) {
break;
}
else {
weight *= 2;
++cnt;
}
}
//cnt就应该要编码的二进制的位数
orgsz = sz*cnt;
cout << endl << "获得的哈夫曼编码映射为：" << endl;
for (auto i = hmf_map.cbegin(); i != hmf_map.cend(); ++i) {
cout << "[" << i->first << "]=";
for (int j = 0; j < (i->second).size(); ++j) {
cout << i->second[j];
}
cout << endl;
}
std::string hfm_encodedstr;//这个表示哈夫曼编码后的二进制
cout << "得到的哈夫曼字符编码为：";
for (int i = 0; i < sz; ++i) {
for (int j = 0; j < hmf_map[c[i]].size(); ++j) {
cout << hmf_map[c[i]][j];
hfm_encodedstr.push_back(hmf_map[c[i]][j] + '0');
++zipsz;//压缩后大小计算
}
cout << " ";
}
cout << endl << "原始编码长度：" << orgsz << "，编码后长度：" << zipsz << " 压缩率为：" << (static_cast<float>(zipsz) / orgsz) << endl;
cout << "解码后：" << hmf.deCoding(hmf_map, hfm_encodedstr) << endl;//重新解码
return 0;
}
为什么需要二叉树呢？因为一个char类型字符可能需要8位来表示。而如果转换成0和1表示，就可以使用floor((log2(N))个0 1 序列表示。假设一共所有的字符可以用宽位4的二进制位表示，那么一个8位就可以用来表示两个字符，积少成多就可以省下很多的空间。有点让我想起了可以用int表示32个真假逻辑值。
7.平衡树：每当插入节点时，可能会使二叉树变成一个链表，这会严重降低二叉树的搜索性能，最坏的时间复杂度会达到O(N)。所以我们仍然需要做出一些调整，使得二叉树能够在floor(log2(N))的时间查找一个节点。所以就需要不断地调整。
- AVL树：比较简单的平衡查找树。平衡因子就是左右子树高度之差的绝对值不超过1，就认为是平衡的。如果定义平衡因子=左子树高度-右子树高度。如果没有子树，对应的高度为-1。插入新元素后，不满足的平衡的四种情况：
参考：
- 树的高度与深度：http://blog.csdn.net/fanpei_moukoy/article/details/23828603
- 《算法之美》
- 《大话数据结构》