Some concepts
结点：包括一个数据元素以及若干指向其它结点的分支信息结点的度：一个结点的子树个数叶结点：度为0的结点，即无后继的结点，也称终端结点分支结点：度不为0的结点，也称非终端结点结点的层次：从根结点开始定义，根结点层次为1，根的直接后继的层次为2，以此类推结点的层次编号：将树中的结点从上到下、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数树的度：树中所有结点的度的最大值树的高/深度：树中所有结点的层次的最大值有序树：在树T中，如果各子树Ti之间是有先后次序的，称为有序树森林：m棵不相交的树的集合，将一颗非空树的根结点删除，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树二叉树：每个结点的度都不大于2；每个结点的孩子结点次序不能颠倒（即有左右孩子之分）满二叉树：深度为k且有2^k-1个结点的二叉树，即每一层都有两个分支、每层的结点都是满的完全二叉树：深度为k，结点数为n的二叉树，如果其结点1-n分别与等高的满二叉树的1-n结点的位置序号一一对应，则称为完全二叉树满二叉树必为完全二叉树但完全二叉树不一定为满二叉树
二叉树的性质
在二叉树的第i层上最多有2^（i-1）个结点深度为k的二叉树最多有2^k-1个结点（对1中的结点进行累加）对任意一棵二叉树T，若终端结点数为n0，而其度为2的结点数为n2，则n0=n2+1（根据总的结点数和分支结点数进行计算）具有n个结点的完全二叉树的深度为log2n+1(log2n取下限)对有n个结点的完全二叉树，将其按照从上到下从左到右的顺序对二叉树中的所有结点进行顺序编号，对于任意的序号为i的结点有： ① 如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为i/2取下限 ②如2i>n，则序号为i的结点无左孩子；如2i<=n，则序号为i的结点的左孩子结点的序号为2i ③如2i+1>n，则序号为i的结点无右孩子；如2i<=n，则序号为i的结点的右孩子结点的序号为2i+1
二叉树的存储结构
顺序存储结构（非二叉树内存空间浪费较大） 对于完全二叉树来说，将其数据元素逐层存放到一组连续的存储单元中（用一维数组当作存储结构）链式存储结构 对每个结点设置三个域，即数据域、左孩子域和右孩子域
二叉树的遍历
二叉树的遍历主要分为前序、中序和后序遍历 ①前序遍历 先访问根结点；按先序遍历左子树；按先序遍历右子树 ②中序遍历 按中序遍历左子树；访问根结点；按中序遍历右子树 ③后序遍历 按后序遍历左子树；按后序遍历右子树；访问根结点
线索二叉树
其中，指向前驱和后继结点的指针称为线索，以这种结构组成的二叉链表作为二叉树的存储结构，称为线索链表；对二叉树以某种次序进行遍历并加上线索的过程称为线索化；线索化了的二叉树称为线索二叉树。
树、森林和二叉树的关系
①树转为二叉树 树中所有相邻兄弟之前加一条连线；再对树中的每个结点只保留其与第一个孩子结点的连线，删去其与其它孩子结点的连线；以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明 ②森林转为二叉树 将森林中的每棵树都转为相应的二叉树；第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树
③二叉树还原为树或森林 树和森林都可以转化为二叉树，但不同的是，树转为二叉树，根结点必定没有右孩子，而由森林转换而得的二叉树，其根节点有右孩子，具体的还原办法如下：
若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子…都与该结点的双亲结点用线连起来；删除原二叉树中所有双亲结点与右孩子的连线；整理结果得到相应的树或森林。
哈夫曼树
https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc
