二叉树是有序树，二叉树可以为空，结点的度可以为0、1、2，不存在度大于2的结点，⚠️注意与度为2的有序树区分开来
每一层都有最多数量的结点
编号1～n的结点与满二叉树中编号1～n的结点一一对应
结点编号i小于等于n/2的向下取整
左子树上的所有结点的关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字
在含有n个结点的二叉链表中，将会含有（n+1）个空链域
非线性结构
适合存储完全二叉树和满二叉树（对于一般的二叉树，为了能让每个结点与完全二叉树上的结点相对应，只能添加一些空结点来反映二叉树中结点之间的逻辑关系）
存储结构描述
先序遍历NLR
中序遍历LNR
后序遍历LRN
先序遍历非递归算法见P133
中序遍历非递归算法见P134
算法见P134
后序遍历序列最后一个为根结点，然后再中序中分除左子树和右子树，再根据后序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
先序遍历序列的第一个为根结点，然后再中序中分除左子树和右子树，再根据先序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
层序遍历序列的第一个为根结点，然后再中序中分除左子树和右子树，再根据层序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
ltag或rtag==0则代表lchild或rchild指针指示的是孩子结点，如果ltag或rtag==1则代表lchild或rchild指针指示的是其前驱或者后继
存储结构描述
中序线索二叉树的构造算法和遍历
左子树的值小于根结点的值，右子树的值大于根结点的值
查找
插入
构造
删除
最坏时间复杂度O(n)
保证任意结点的左右子树高度差的绝对值不超过1
左右子树的高度差为该结点的平衡因子
插入（四种情况下为保持平衡二叉树的平衡的四种操作） 在结点的左孩子的左子树上插入了新结点，导致了不平衡
在结点的右孩子的右子树上插入了新结点，导致了不平衡
在结点的左孩子的右子树上插入了新结点，导致了不平衡
在结点的右孩子的左子树上插入了新结点，导致了不平衡
每次旋转操作的对象都是最小的不平衡树（示意图看一遍就明白P177，比较简单）
比较关键字的次数不超过平衡二叉树的深度，含有n个结点的平衡二叉树的最大深度为O(log2n)，因此平衡二叉树的平均查找长度为O(log2n)
权
结点的带权路径长度
树的带权路径长度WPL
带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
每次选剩下的结点和已生成的根结点中最小的两个作为左右子树生成新的根结点 不难，结合例子很容易理解
每个字符采用相同长度的二进制位表示
允许对不同字符采用不同长度的二进制位表示
非常容易被名称迷惑，并不是顾名思义
0
0
分享
