树二叉树哈夫曼树

1.树

　　需要注意的两点&＃xff1a;n(n>&＃61;0)表示结点的个数&＃xff0c;m表示子树的个数

　　&＃xff08;1&＃xff09;n>0时&＃xff0c;树的根节点是唯一的。

　　&＃xff08;2&＃xff09;m>0时&＃xff0c;子树的个数没有限制。

　　结点的度和树的度

　　&＃xff08;1&＃xff09;结点的度是指结点拥有的子树数

　　&＃xff08;2&＃xff09;树的度是指树的各结点的度的最大值

　　树的深度&＃xff08;Depth&＃xff09;

　　树中结点的最大层次

　　　　　 1 / \2 3/\ \4 5 6
　　此树的深度是3
　　
　　

　　树和图有什么区别&＃xff1f;
　　树其实就是不包含回路的连通无向图。
　　

　　上面这个例子中左边的是一棵树&＃xff0c;而右边的是一个图。因为左边的没有回路&＃xff0c;而右边的存在1->2->5->3->1这样的回路。

　　&＃xff08;1&＃xff09;正是因为树有着“不包含回路”这个特点&＃xff0c;所以树就被赋予了很多特性。

　　&＃xff08;2&＃xff09;一棵树中的任意两个结点有且仅有唯一的一条路径连通。

　　&＃xff08;3&＃xff09;一棵树如果有n个结点&＃xff0c;那么它一定恰好有n-1条边。

2.二叉树
　　特点&＃xff1a;
　　　　&＃xff08;1&＃xff09;每个结点最多有两棵子树
　　　　&＃xff08;2&＃xff09;左子树和右子树都是有顺序的&＃xff0c;次序不能任意颠倒
　　　　&＃xff08;3&＃xff09;即使树中某结点只有一颗子树&＃xff0c;也要区分是左子树还是右子树

　　　　　　 1 \3

　　 3就是1的右子树

　　　二叉树的常见性质&＃xff1a;

　　  性质1 在二叉树的第i层上至多有2^i-1个结点(i>&＃61;1)

　　  性质2 深度为k的二叉树至多有2^k-1个结点(k>&＃61;1)

　　  性质3 满二叉树&＃xff0c;在一棵深度为k且有2^k-1个结点。完全二叉树&＃xff0c;若一棵深度为k的二叉树&＃xff0c;其前k-1层是一个棵满二叉树&＃xff0c;而最下面一层(即第k层)上的结点都集中在该层最左边的若干位置上。

　　  性质4 对于任何一棵二叉树T&＃xff0c;如果其终端结点数&＃xff08;叶子结点数&＃xff09;为n₀,度为2的结点数为n_2,则n₀&＃61;n₂&＃43;1

　　  性质5 具有n个结点的完全二叉树的深度为[log2n]&＃43;1

　　   栗子1&＃xff1a;
　　   具有300个结点的二叉树&＃xff0c;其高度&＃xff08;深度&＃xff09;至少为9
　　　　9层&＃xff1a;至多&＃xff1a;2⁹-1&＃61;512-1&＃61;511
　　　　8层&＃xff1a;至多&＃xff1a;2⁸-1&＃61;256-1&＃61;255
　　
　　   栗子2&＃xff1a;
　　   已知一颗完全二叉树的第6层&＃xff08;设根是第1层&＃xff09;有8个叶结点&＃xff0c;则该完全二叉树的结点个数最多是多少&＃xff1f;
　　　　第6层至多有2^6-1&＃61;32个&＃xff0c;因为有8个叶结点&＃xff0c;所以有24个子结点。又因为是完全二叉树&＃xff0c;则第7层最多有24*2&＃61;48个叶结点。

　　　　前6层至多2⁶-1&＃61;63个&＃xff0c;所以该完全二叉树的结点数最多是48&＃43;63&＃61;111

 　　  栗子3&＃xff1a;

　　 一个具有20个叶子节点的二叉树、它有&＃xff08;&＃xff09;个度为2的节点　
　　　　可知n₀&＃61;20&＃xff0c;由n₀&＃61;n₂&＃43;1&＃xff0c;可以得到n₂&＃61;19

　　 栗子4&＃xff1a;
　　 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,则T中的叶子数为()

　　　　又由于 n &＃61; n0 &＃43; n1 &＃43; n2 &＃43; n3 &＃43; n4 &＃61; n0 &＃43; 8;

　　　　n0 &＃43; 8 &＃61; 16&＃xff0c;所有叶子结点个数为8
　　   栗子5&＃xff1a;
　　  对于有n个结点的二叉树,其高度为()

　　　　正确答案: D   

　　解释&＃xff1a;如果是完全二叉树则是[log 2 n]&＃43;1&＃xff0c;有计算公式。其他的二叉树没有规律&＃xff0c;是没有计算公式的&＃xff0c;也是不确定的&＃xff0c;只能知道其高度的范围是&＃xff1a;[log2n ]&＃43;1 到 n

　　     栗子6&＃xff1a;

　　　完全二叉树共有700结点&＃xff0c;该二叉树有多少个叶子结点&＃xff1f;　

　对于二叉树总的结点数是&＃xff1a;n&＃61;n₀&＃43;n₁&＃43;n₂　
　　由性质4知&＃xff0c;n₀&＃61;n₂&＃43;1　
　　所以&＃xff0c;n₀&＃43;n₁&＃43;n₀-1&＃61;700&＃xff0c;又n₁只能去0或1&＃xff0c;故此处选1
　　2n₀&＃61;700&＃xff0c;n₀&＃61;350

　完全二叉树和满二叉树
　　　　
　　

　　　二叉树的两种存储结构

　　  &＃xff08;1&＃xff09;顺序存储&＃xff08;一般只用于完全二叉树&＃xff09;适用性不强

　　　　对于完全二叉树而言&＃xff0c;可以使用顺序存储结构。但是对于一般的二叉树来说&＃xff0c;使用存储结构会有两个缺点&＃xff1a;
　　　　一、如果不是完全二叉树&＃xff0c;则必须将其转化为完全二叉树&＃xff0c;
　　　　二、是增加了很多虚节点&＃xff0c;浪费资源空间。
　　

　　　　&＃xff08;2&＃xff09; 链式存储

　　　　这是最常用的一种二叉树存储结构。

　　　　每个结点设置三个域&＃xff0c;即值域&＃xff0c;左指针域和右指针域&＃xff0c;用data表示值域&＃xff0c;lchild和rchild分别表示指向左右子树的指针域。如图所示。

　　遍历二叉树
　　前&＃xff0c;中&＃xff0c;后序遍历&＃xff0c;这个前、中、后都是相对于根节点而言的&＃xff0c;都是从根节点出发&＃xff0c;按照某种次序一次访问二叉树中的所有结点&＃xff0c;使得每个结点被访问的次数有且只有一次
　　前序遍历&＃xff08;先根遍历&＃xff09;&＃xff1a;根-->左-->右
　　中序遍历&＃xff08;中根遍历&＃xff09;&＃xff1a;左-->根-->右&＃xff08;左&＃xff0c;是从最下层结点的左子树开始遍历&＃xff09;
　　后序遍历&＃xff08;后根遍历&＃xff09;&＃xff1a;叶子-->结点-->根节点&＃xff08;按照先左子树&＃xff0c;后右子树&＃xff0c;最后访问根节点&＃xff09;
　　层序遍历&＃xff1a;从树的第一层&＃xff0c;也就是根节点开始访问&＃xff0c;从上到下一层一层遍历&＃xff0c;其中在同一层&＃xff0c;就按照从左到右的顺序访问
　　　　
前序遍历&＃xff1a;
12-9-76-35-22-16-48-46-40-90-
中根遍历&＃xff1a;
9--12--16--22--35--40--46--48--76--90--
后根遍历&＃xff1a;
9---16---22---40---46---48---35---90---76---12---

实现代码&＃xff1a;二叉树的创建和遍历都是利用了递归的思想

3.推导遍历结果
三种情况&＃xff1a;
&＃xff08;1&＃xff09;已知前序遍历和中序遍历&＃xff0c;可以唯一确定一棵二叉树

　&＃xff08;2&＃xff09;已知后序遍历和中序遍历&＃xff0c;可以唯一确定一棵二叉树

   &＃xff08;3&＃xff09;已知前序遍历和后序遍历&＃xff0c;是不能确定一棵二叉树的

推导方法&＃xff1a;
&＃xff08;1&＃xff09;先确定根节点。可以根据前序的第一个元素或后序的最后一个元素来确定
&＃xff08;2&＃xff09;确定第一个根节点的左子树和右子树。可以根据中序来确定

栗子1&＃xff1a;
已知前序ABCDEF&＃xff0c;中序CBAEDF&＃xff0c;还原此二叉树&＃xff0c;并推出中序遍历的结果
&＃xff08;1&＃xff09;首先确定根节点是A&＃xff0c;根据前序的第一个元素。
&＃xff08;2&＃xff09;由中序可知&＃xff0c;A的左边是CB&＃xff0c;右边是EDF
　　　　　　A
　　　　　/　　\
　　　　B　　　　D
　　　/　　　　 /　 \
　　C　　　　 E　　　 F
可推出后序&＃xff1a;CBEFDA

栗子2&＃xff1a;
已知中序ABCDEFG&＃xff0c;后序BDCAFGE&＃xff0c;还原此二叉树&＃xff0c;并推出中序遍历的结果

  &＃xff08;1&＃xff09;首先确定根节点是E&＃xff0c;根据后序的最后一个元素。
  &＃xff08;2&＃xff09;由中序可知&＃xff0c;E的左边是ABCD&＃xff0c;右边是FG

　　初步判断&＃xff1a;

　　　　　　　　　E　
　　　　　　　　/　　\
　　　　　　　ABCD　　FG
　　再次判断&＃xff1a;
　　　　　　　　　　E
　　　　　　　　　/　 \
　　　　　　　　A　　　 G
　　　　　　　　 \　　　 /
　　　　　　　　　C　　 F
　　　　　　　　/　　\
　　　　　　　B　　　D

可推出前序&＃xff1a;EACBDGF

栗子3&＃xff1a;某二叉树的先根遍历序列和后根遍历序列正好相反&＃xff0c;则该二叉树具有的特征是(A)　　　

　　　　A.高度等于其结点数

　　　　B.任一结点无左孩子

　　　　C.任一结点无右孩子

　　　　D.空或只有一个结点

解释&＃xff1a;

　　可以是全部都是左孩子&＃xff0c;也可以是全部都是右孩子&＃xff0c;所以在一起就合称高度等于其结点数

　　　　　　  A　　　　　　　　　　A

　　　　　  /　　　　　　　　　　　　　\

　　　　  B　　　　　　　　　　　　　　　B

　　　  /　　　　　　　　　　　　　　　　　　\

　　  C　　　　　　　　　　　　　　　　　　　　C

　　/　　　　　　　　　　　　　　　　　　　　　　\

　D　　　　　　　　　　　　　　　　　　　　　　　　D

先根遍历是&＃xff1a;A-B-C-D　　　　　　　　　　先根遍历是&＃xff1a;A-B-C-D

后根遍历是&＃xff1a;D-C-B-A　　　　　　　　　　后根遍历是&＃xff1a;D-C-B-A

4.哈夫曼树
哈夫曼树是一种带权路径长度最短的二叉树&＃xff0c;也称为最优二叉树。
&＃xff08;1&＃xff09;什么叫带权路径长度&＃xff1f;
从该结点到树根之间路径长度与结点上的权的乘积
下面用一幅图来说明。
　　

　　它们的带权路径长度分别为&＃xff1a;

　　图a&＃xff1a; WPL&＃61;5*2&＃43;7*2&＃43;2*2&＃43;13*2&＃61;54

　　图b&＃xff1a; WPL&＃61;5*3&＃43;2*3&＃43;7*2&＃43;13*1&＃61;48

　　可见&＃xff0c;图b的带权路径长度较小&＃xff0c;我们可以证明图b就是哈夫曼树(也称为最优二叉树)

 　　&＃xff08;2&＃xff09;如何构建哈夫曼树&＃xff1f;

　　　　一般可以按下面步骤构建&＃xff1a;

　　　　&＃xff08;1&＃xff09;将所有左&＃xff0c;右子树都为空的作为根节点。

　　　　&＃xff08;2&＃xff09;在森林中选出两棵根节点的权值最小的树作为一棵新树的左&＃xff0c;右子树&＃xff0c;且置新树的附加根节点的权值为其左&＃xff0c;右子树上根节点的权值之和。注意&＃xff0c;左子树的权值应小于右子树的权值。

　　　　&＃xff08;3&＃xff09;从森林中删除这两棵树&＃xff0c;同时把新树加入到森林中。

　　　　&＃xff08;4&＃xff09;重复2&＃xff0c;3步骤&＃xff0c;直到森林中只有一棵树为止&＃xff0c;此树便是哈夫曼树。

　　　　下面是构建哈夫曼树的图解过程&＃xff1a;

　　&＃xff08;3&＃xff09;哈夫曼编码

　　　　利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

　　　　树中从根到每个叶子节点都有一条路径&＃xff0c;对路径上的各分支约定指向左子树的分支表示”0”码&＃xff0c;指向右子树的分支表示“1”码&＃xff0c;取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码&＃xff0c;即是哈夫曼编码。

　　　　就拿上图例子来说&＃xff1a;

　　　　A&＃xff0c;B&＃xff0c;C&＃xff0c;D对应的哈夫曼编码分别为&＃xff1a;111&＃xff0c;10&＃xff0c;110&＃xff0c;0

　　　　用图说明如下&＃xff1a;

　　　　
注意&＃xff1a;若有编码00&＃xff0c;则至少必须有编码01&＃xff0c;否则只一个结点构成不了双亲&＃xff0c;也就是说&＃xff0c;不是二叉树了。
如&＃xff1a;00,100&＃xff0c;101,110,111不可能是哈夫曼编码
　　
记住&＃xff0c;设计电文总长最短的二进制前缀编码&＃xff0c;就是以n个字符出现的频率作为权构造一棵哈夫曼树&＃xff0c;由哈夫曼树求得的编码就是哈夫曼编码。
栗子1&＃xff1a;
用二进制来编码字符串"abcdabaa"&＃xff0c;需要能够根据编码&＃xff0c;解码回原来的字符串&＃xff0c;最少需要多长的二进制字符串&＃xff1f;
解析&＃xff1a;哈夫曼编码问题。求二进制字符串长度其实就是求带权最短路径长度。
　　　可以先构造哈夫曼树&＃xff0c;字符串中&＃xff0c;a有4个&＃xff0c;b有2个&＃xff0c;c有1个&＃xff0c;d有1个&＃xff0c;这些个数就是权值&＃xff0c;先选最小的两个权值&＃xff0c;c和d&＃xff0c;

　　如图&＃xff1a;

所以字符串总长度&＃xff1a;4*1&＃43;2*2&＃43;1*3&＃43;1*3&＃61;14

栗子2&＃xff1a;

参考文档&＃xff1a;
http://blog.sina.com.cn/s/blog_70600f720100ujnp.html
http://www.cnblogs.com/mcgrady/p/3329825.html