哈夫曼树的认识

                         哈夫曼树的认识
    先介绍一下链表。链表由一系列的结点组成，每个结点包括两个部分：数据域和指针域。数据域用来存储数据元素，指针域用来存储下一个结点的指针。这样，只要记录头结点的位置，便能找到链表中的所有数据。链表分为单向链表，双向链表和循环链表。链表能实现的基本操作：查找，删除，插入，排序，交换等。
    树，其实，树和链表类似，只不过有些结点的后继大于等于一。同样，只要有根节点，便能得到整棵树上的所有数据。对于一棵结点不为零的树来说，整棵树中有且只有一个结点没有前驱，将其定义为根结点（root），其他的结点都有一个前驱，有m（m>=0）个后继。
    二叉树是每个结点的后继个数小于等于二的树。二叉树分为(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树。
    哈夫曼树是带权路径最小的二叉树。这种树在信息搜索，文件压缩中发挥着很重要的作用。
    树的路径长度：从树的根节点到树的每一个叶子节点的路径长度之和。