牛客网刷题纠错04

末蓝、 2021-11-16 13:06 307阅读 0赞

### 文章目录 ###

*  1.哈夫曼树的构造
 *  2.关于排序树的性质
 *  3.熟悉各种排序.....
 *  4.栈的记忆性

# 1.哈夫曼树的构造 #

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：  
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；  
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；  
(3)从森林中删除选取的两棵树，并将新树加入森林；  
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

哈夫曼树的带权路径  
首先：将权值从小到大排序，然后像下图一样，每次合并的两个节点下面画一个横线，（期间可能要适当的调整结点）  
![在这里插入图片描述][aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vaW1hZ2VzLzIwMTcwNzExLzE1MDU4OTlfMTQ5OTc3MTUzOTM0NV84MEQyNTg0Q0Q5N0RERUZCNjM2NUExODY0RDQyQTY0Mw]权值的话，就等于所有的结点权值\*横线个数 之和。

# 2.关于排序树的性质 #

链接：[https://www.nowcoder.com/questionTerminal/76826caa65ed49cb89556b05d101083d][https_www.nowcoder.com_questionTerminal_76826caa65ed49cb89556b05d101083d]  
来源：牛客网

一：二叉排序树的左子树节点值都小于根节点值，右子树节点值都大于根节点，因此假如根节点值为10，其左节点值为5，其左节点的右节点值为8，那么从右节点到跟节点的值依次为8 5 10，显然不是有序的  
二：哈夫曼树是带权路径最小的二叉树，也不是  
三：AVL树是二叉排序树，只不过其左右子树的高度差有限制，在1之内，由一只非有序  
四：堆是一种完全二叉树，其有大顶堆和小顶堆的分别，大顶堆是指其每个节点的值都大于其左右孩子的值（小顶堆反之），因此从任一节点到根节点是升序排列的（小顶堆反之）

# 3.熟悉各种排序… #

# 4.栈的记忆性 #

链接：[https://www.nowcoder.com/questionTerminal/daad3682a864441dadc8e4557000d5a5][https_www.nowcoder.com_questionTerminal_daad3682a864441dadc8e4557000d5a5]  
来源：牛客网

栈的特点是FILO，后进栈的先出栈，所以你对一个栈进行出栈操作，出来的元素肯定是你最后存入栈中的元素，所以栈有记忆功能。  
而队列是先进先出，你取队列的第一个元素，得到的是你最先存入队列的元素，而不是上一个存入队列的元素，所以没有记忆功能  
栈经常用于History的记录而已

你想象下，用什么方式来实现浏览器的历史？

我浏览了一个页面，然后入栈，再浏览一个，再入栈，当想回退一个页面的时候，就弹出栈顶的数据就可以~

[aHR0cHM6Ly91cGxvYWRmaWxlcy5ub3djb2Rlci5jb20vaW1hZ2VzLzIwMTcwNzExLzE1MDU4OTlfMTQ5OTc3MTUzOTM0NV84MEQyNTg0Q0Q5N0RERUZCNjM2NUExODY0RDQyQTY0Mw]: /images/20211116/8f706725b5344f4d8ae68436fc0f3f30.png
[https_www.nowcoder.com_questionTerminal_76826caa65ed49cb89556b05d101083d]: https://www.nowcoder.com/questionTerminal/76826caa65ed49cb89556b05d101083d
[https_www.nowcoder.com_questionTerminal_daad3682a864441dadc8e4557000d5a5]: https://www.nowcoder.com/questionTerminal/daad3682a864441dadc8e4557000d5a5