树和森林

树：它是一个（一对多）的结构，也可以是（1对0）（ 1对1）这样子 ，有一个起点叫作 '根结点'
结点：是指一个数据元素
孩子:一对多里的多
子树：以某个孩子结点为根的一棵树
叶子结点:指的是没有孩子的结点（这个是易忘点）
森林：多棵树
 

二叉树

二叉树的每个结点至多有两个孩子（可以是0个1个2个），分别称为左孩子和右孩子

二叉树的高度指从根节点向下直至最深叶子结点的高度


特殊二叉树


补充：完全二叉树  设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
第 h 层所有的结点都连续集中在最左边


树和森林转化为二叉树

    
树转为二叉树： 每个结点只保留第一个孩子(老大)作为左孩子，剩下的孩子(老大的兄弟们)依次接到老大的右孩子链上

森林转为二叉树：
1. 各树分别转为二叉树
2. 各树根用右孩子链相连
    


森林向二叉树转化是确定且唯一的过程，且根结点没有右孩子


二叉树的遍历

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根




注意  可以通过中序+先序/后序序列之一来还原二叉树结构，先+后则不行


哈夫曼树

初始时，一堆独立结点，结点各有自己的权值
重复地让当前权值最小的两个根结点作为左右孩子，生成新的根结点，新结点权值为它们的权值之和，直至形成一颗二叉树





把路标标上0和1，可以使每一个叶子结点都有一个唯一编码