查看“特殊二叉树”的源代码

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

=== 1）二叉查找树 ===
[[文件:二叉查找树.png|无|缩略图]]
二叉排序/查找树

左子树小于根

右子树大于根





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



特点：

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

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

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





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

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

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

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




二叉查找树为空树，以新结点89为查找二叉树
{| class="wikitable"
!89
|}


将要插入结点值48与父结点值89比较，48<89，放左子树，左子树为空，作为子树的根结点插入；
{| class="wikitable"
! colspan="2" |89
|-
!48
!
|}



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

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

右子树为空，作为右子树的根结点插入；
{| class="wikitable"
! colspan="3" |89
|-
! colspan="2" |48
!
|-
!
!56
!
|}



键值48的结点已存在，不再插入
{| class="wikitable"
! colspan="4" |89
|-
! colspan="2" |48
! colspan="2" |
|-
!
!56
!
!
|}



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

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

左子树为空，作为左子树的根结点插入；
{| class="wikitable"
! colspan="4" |89
|-
! colspan="2" |48
! colspan="2" |
|-
!20
!56
!
!
|}


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

右子树为空，作为右子树的根结点插入；
{| class="wikitable"
! colspan="4" |89
|-
! colspan="2" |48
! colspan="2" |112
|-
!20
!56
!
!
|}


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

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

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

左子树为空，作为左子树的根结点插入；
{| class="wikitable"
! colspan="5" |89
|-
! colspan="3" |48
! colspan="2" |112
|-
!20
! colspan="2" |56
!
!
|-
!
!51
!
!
!
|}




=== 2）哈夫曼树 ===
需要了解的基本概念：
{| class="wikitable"
|[[文件:哈夫曼树图1.png|无|缩略图|图1]]
|[[文件:哈夫曼树图2.png|无|缩略图|图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；