树和二叉树数据结构讲解.ppt

第六章 树和二叉树;一、树的基本概念;;;;性质1的证明： 证明：根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点。也就是说，每个结点与指向它的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数(度数)，从而可得树中的结点数等于所有结点的度数加1。 ;性质2证明（数学归纳法）： （1）对于第一层，因为树中的第一层上只有一个结点，即整个树的根结点，而由i=l代入mi-1得mi-1 =1，也同样得到只有一个结点，显然结论成立。 （2）假设对于第(i-1)层(il)命题成立，即度为m的树中第(i-1)层上至多有mi-2结点，则根据树的度的定义，度为m的树中每个结点至多有m个孩子，所以第i层上的结点数至多为第(i-1)层上结点数的m倍，即至多为mi-2 *m= mi-1个，这与命题相同，故命题成立。 ;性质4的证明：;;;（2）孩子存储结构：按树的度设计节点的孩子节点的指针域的个数。;;树的基础要点;;;;二、二叉树的概念和性质;;;;;;;;;三、二叉树的存储结构;;;;;四、二叉树的基本运算及其实现;;;;;;;;;五、二叉树的遍历;;二叉树的基础要点;;;;;;;六、线索化二叉树;;;;对同一棵二叉树的遍历方式不同，所得到的线索树也不同，二叉树有先序、中序和后序三种遍历方式，所以线索树也有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。 以中序线索二叉树为例，讨论建立线索二叉树的算法。 建立线索二叉树，或者说，对二叉树线索化，实质上就是遍历一棵二叉树，在遍历的过程中，检查当时结点的左、右指计域是否为空。如果为空，将它们改为指向前驱结点或后继结点的线索。另外，在对一棵二叉树加线索时，必须首先创建一个头结点，建立头结点与二叉树的根结点的线索。对二叉树线索化后，还须建立最后一个结点与头结点之间的线索。;;线索二叉树基础要点;;;七、哈夫曼树;;;2、哈夫曼树的构造方法 哈夫曼算法：;3、哈夫曼编码 在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串，我们称这个过程为编码。显然，希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。 具体构造方法如???：设需要编码的字符集合为{d0,d1,…,dn-1},各个字符在电文中出现的次数集合为{W0,W1,…,Wn-l}，以d0,d1,…,dn-1作为叶结点，以w0, W0,W1,…,Wn-l作为各根结点到每个叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。 实质：就是利用使用频率越高的采用越短的编码。;哈夫曼树的基础要点;;;练习;5.对于如图所示的二叉树： (1)请画出它的顺序存储结构图； (2)请将它转换成森林。 ;;6.设F={T1,T2,T3}是森林，试画出所对应的二叉树，森林如下图所示。 ;;;;;;;