特殊二叉树

https://www.bilibili.com/video/BV1hg411V7Bm?p=61

1）二叉查找树

二叉排序/查找树

左子树小于根

右子树大于根

对每一个结点而言，它的左孩子小于它自身，右孩子大于它自身。

特点：

1）二叉查找树的中序遍历序列为从小到大排列的序列。

2）值最小的结点无左子树，值最大的结点无右子树。

3）每一层从左到右进行遍历的序列为从小到大排列的序列。

插入结点：序列（89，48，56，48，20，112，51）

1、若查找二叉树为空树，则以新结点为查找二叉树；

2、将要插入结点值与父结点值比较，确定要放左子树还是右子树中，若子树为空，则作为子树的根结点插入；

3、若该键值结点已存在，则不再插入。

二叉查找树为空树，以新结点89为查找二叉树

89

将要插入结点值48与父结点值89比较，48<89，放左子树，左子树为空，作为子树的根结点插入；

89
48

将要插入结点值56与根结点值89比较，56<89，放左子树；

左子树不为空，将要插入结点值56与左子树的根结点值48比较，56>48，放右子树；

右子树为空，作为右子树的根结点插入；

89
48
	56

键值48的结点已存在，不再插入

89
48
	56

将要插入结点值20与根结点值89比较，20<89，放左子树；

左子树不为空，将要插入结点值20与左子树的根结点值48比较，20<48，放左子树；

左子树为空，作为左子树的根结点插入；

89
48
20	56

将要插入结点值112与根结点值89比较，112>89，放右子树；

右子树为空，作为右子树的根结点插入；

89
48		112
20	56

将要插入结点值51与根结点值89比较，51<89，放左子树；

左子树不为空，将要插入结点值51与左子树的根结点值48比较，51>48，放右子树；

右子树不为空，将要插入结点值51与右子树的根结点值56比较，51<56，放左子树；

左子树为空，作为左子树的根结点插入；

89
48			112
20	56
	51

2）哈夫曼树

需要了解的基本概念：

图1

图2

树的路径长度：从树根到树中每一结点的路径长度之和（一般讨论的对象是叶子结点）

比如图1中：

2到根15距离是2；

4到根15距离是3；

8到根15距离是3；

1到根15距离是1；

图2中：

4到根15距离是2；

1到根15距离是3；

2到根15距离是3；

8到根15距离是1；

权：在一些应用中，赋予树中结点的一个有某种意义的实数（一般讨论的对象是叶子结点）

结点值就是叶子结点的权，比如图1中：

2的权就是2，4的权就是4……

带权路径长度：结点到树根之间的路径长度与该结点上权的乘积

比如图1中：

2的带权路径长度就是2×2；

4的带权路径长度就是3×4；

8的带权路径长度就是3×8；

1的带权路径长度就是1×1；

树的带权路径长度（树的代价）：树中所有叶结点的带权路径长度之和

比如图1就是：

2×2+3×4+3×8+1×1

=4+12+24+1

=16+25

=41；

图2就是：

2×4+3×1+3×2+1×8

=8+3+6+8

=11+14

=25；

例：假设有一组权值50，20，30，40，10，请尝试构造哈夫曼树。（如何构造代价最小的哈夫曼树）

从找权值最小的两个结点构建子树开始，循环