2023年上半年程序员考点：特殊二叉树

考点1：二叉查找树

图 3-29  二叉查找树1

特点：

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

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

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

插入结点：序列(89.48.56.48.20.112.51)

图 3-30  二叉查找树2

考点2：哈夫曼树

需要了解的基本概念：

树的路径长度：从树根到树中每一结点的路径长度之和。

权：在一些应用中，赋予树中结点的一个有某种意义的实数。

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

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

图 3-31  哈夫曼树

例：假设有一组权值50,20,30,40,10，请尝试构造哈夫曼树。

     图 3-32  构造哈夫曼树

考法1：考查二叉排序树的性质

1)对一棵二叉排序树进行( )遍历，可得到该二叉树中结点关键字的有序序列。

A. 先序 B. 中序 C. 后序 D. 层序

考法2：考查哈夫曼树

1)由权值为29、12、15、6、23的5个叶子结点构造的哈夫曼树为( )，其带权路径长度为( )。

A.B. 

C.D. 

A. 85  B. 188  C. 192  D. 222

考法3：考查哈夫曼树

1)根据权值集合{0.30.0.25.0.25.0.12.0.08｝构造的哈夫曼树中，每个权值对应哈夫曼树中的一个叶结点，( )。

A. 根结点到所有叶结点的路径长度相同

B. 根结点到权值0.30和0.25所表示的叶结点路径长度相同

C. 根结点到权值0.30所表示的叶结点路径最长

D. 根结点到权值0.25所表示的两个叶结点路径长度不同

总结

图 3-33  树总结