简介
树是一个有趣的数据结构，他不像图那么复杂，又不像线性表那么呆板！这种一对多的数据结构，使得树能够实现许多常用的算法！ 现实中的许多复杂关系，也往往转化成“一对多”的树来解决！
这一节我们一起来看看“树的那些事”！ 本张的主要内容是以二叉树进行展开叙述的，一共由3部分组成：
- 树的概念及二叉树
- 树的遍历
- 最优二叉树
相关代码也托管到Github上了~我是代码，快点我
相关概念：
首先来粗略复习一下树的相关概念： 子树、结点的度、叶子结点、非终端结点、树的度（max(结点的度)）、孩子、兄弟、双亲、树的深度、结点的堂兄弟、 二叉树、完全二叉树、满二叉树、有序树、无序树、森林、
树的常用3种表示方法：双亲、孩子、孩子兄弟
二叉树
二叉树的结构：
- 线性结构：顺序存储
- 链式结构：链式存储结构
定义如下代码所示：
//顺序
typedef Teletype int[1000];
//链式
typedf struct node
{
T data;
node* lchild;
node* rchild;
}node;
二叉树性质：
- 1：i层上最多2^(i-1)个点
- 2：深度为k的二叉树最多2^(k-1)个节点
- 3：度为2的结点为n1，那么叶子结点的个数n2=n1+1;
- 4：n个结点的完全二叉树的深度D=[log2(n)]+1 (向下取整+1)
- 5：完全二叉树编号， * 节点i有双亲则为[i/2]，* 2i>n 则i无左孩子，否则左孩子编号为2i * 2i+1>n 则结点i无右孩子，否则右孩子编号为2i+1
树的遍历
树的遍历4种方式：先序遍历、中序遍历、后续便利、层序遍历！
时间复杂度O(n) 空间复杂度O(n)=D(T)
树的遍历分了一章单独来讲：从树的遍历看递归展开 感兴趣的同学可以点进去指点一下! ^-^
Huffman 树
Huffman树又叫最优二叉树，最大的特点是：树的带权深度最小: min(sum(W*L)) 哈夫曼树的性质：
- 树中没有度为1的点，所以有n个叶子节点的Huffman树一共有2n-1个节点！ （可以想象一下，如果存在度为1的点，一定存在比它“带权深度”小的树）
- Huffman树不唯一，但所有Huffman的带权深度值相等！
- 用频率表示权重，所有树结点的求和即为通信字符总的编码长度！
Huffman树的构造：
使用线性表的存储形式！
算法思路：
- 定义临时数组temp,Huffman树数组tree
- 对temp排序，求权重最小的2个元素a,b，分别放入tree中，并从temp中去除
- 新建元素，weight=a.weight+b.weight，lchild=a,rchild=b；并放入temp中，
- 如果temp.size()>1 则继续2，否则5
- temp中最后一个元素放入tree，tree中即确定树的结构
- 递归先序遍历，构造parent指针！构造完毕，Huffman树即完成！
哈哈，大功告成！从叶子结点出发，依次访问根节点，即可确定每个叶子结点的Huffman编码~
下面是Huffman的构造代码：
class TreeNode
{
public:
int index;//值的索引
int weight;
int parent;
int lchild;
int rchild;
TreeNode():index(-1),weight(-1),parent(-1),lchild(-1),rchild(-1)
{}
TreeNode(int in,int we):parent(-1),lchild(-1),rchild(-1)
{
index = in;
weight = we;
}
TreeNode(int in,int we,int pa,int lc,int rc)
{
index = in;
weight = we;
parent = pa;
lchild = lc;
rchild = rc;
}
bool operator >(TreeNode t2)
{
return weight>t2.weight;
}
};
bool compare(TreeNode &a,TreeNode &b)
{
return a.weight<b.weight;
}
void ttree(vector<TreeNode> &T,int i)
{
if(T[i].index==-1)//非叶节点
{
T[T[i].lchild].parent=i;
T[T[i].rchild].parent=i;
ttree(T,T[i].lchild);
ttree(T,T[i].rchild);
}
}
void HuffmanTree()
{
//以序列 a:1 b:1 c:2 d:2 e:3 为例
vector<int> num(5,0);//频率
num[0]=1;num[1]=1;num[2]=2;num[3]=2;num[4]=3;
vector<string> con(5);//字符
con[0]="a";con[1]="b";con[2]="c";con[3]="d";con[4]="e";
vector<TreeNode> tree;//保存构造的Huffman树
vector<TreeNode> temp;//构造过程 频率 临时数组
for(int j=0;j<con.size();j++)
{
temp.push_back(TreeNode(j,num[j]));
}
for(;temp.size()>1;)
{
sort(temp.begin(),temp.end(),compare);
TreeNode t1(*temp.begin());
TreeNode t2(*(temp.begin()+1));
tree.push_back(t1);
tree.push_back(t2);
TreeNode t3;
t3.lchild=tree.size()-1;
t3.rchild=tree.size()-2;
t3.weight=t1.weight+t2.weight;
temp.erase(temp.begin());
temp.erase(temp.begin());
temp.push_back(t3);
}
tree.push_back(*temp.begin());
for(int i=0;i<tree.size();i++)
{
cout<<"weight: "<<tree[i].weight;
if(tree[i].index!=-1)
cout<<" contain: "<<con[tree[i].index];
cout<<endl;
}
ttree(tree,tree.size());//遍历树，构造parent
}
总结
树型结构，内容基本就这么多了吧，哈哈，到了这里《数据结构》一书也算是复习一半了！
番外话：
找工作倒计时2个月，说实话，心里还是满没底气的！依然要努力加油！ 希望能够通过接下来2个月的学习找到本科时的那份自信：为那些不招我的公司感到惋惜！