搜索
本章小结二叉树的结构特性，各性质相应的证明方法。二叉树的各种存储结构的特点及适用范围。遍历二叉树是二叉树各种操作的基础，遍历的具体算法与所采用的存储结构有关。树和森林与二叉树的转换。最优二叉树的特性，掌握建立最优树和哈夫曼编码的方法。-、树的定义1、树型结构：（非线性结构）至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构。树的定义：是n(n≥0)个结点的有限集合T，对于任意一棵非空树，它满足：有且仅有一个特定的称为根(root)的结点；当n＞1时，其余结点可分为m(m＞0)个互不相交的有限集T1，T2，….，Tm，其中每个集合本身又是一棵树，称为根的子树。上述树的定义是一个递归定义。2、基本术语结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数。叶子(或终端)结点：度为零的结点。分支(或非终端)结点：度大于零的结点树的度：树中所有结点的度的最大值结点的层次：根结点的层次为1，第l层的结点的子树的根结点的层次为l+1。树的深度：树中叶子结点所在的最大层次。任何一棵非空树是一个二元组Tree=(root，F)其中：root被称为根结点F被称为子树森林二、二叉树1、二叉树的定义是n(n=0)个结点的有限集合，它或为空树(n=0)，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。2、二叉树的五种基本形态：空树只含根结点右子树为空树左子树为空树左右子树均不为空树3、二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。其中2i-1为2的i-1次方性质2：深度为k的二叉树上至多含2k-1个结点(k≥1)。其中2k-1为2的k次方减一性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2，∵二叉树上分支总数b=n1+2n2，①而b=n-1=n0+n1+n2–1②由①②，n0=n2+1。除根结点外，其余结点都有一个分支进入，设b为分支总数，则n=b+1性质4：具有n个结点的完全二叉树的深度为log2n+1。其中log2n为不大于log2n的最大整数性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。4、两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。其中2k-1为2的k次方减一特点：是每一层上的结点数都是最大结点数。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。特点：⑴叶子结点只可能在层次最大的两层出现；⑵对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。性质练习：1.一棵二叉树在其第五层中有17个结点，可不可能？第i层上至多有2i-1个结点，则25-1=16。所以，不可能。2.二叉树的根结点属于第0层还是属于第1层？第1层3.已知一棵二叉树有20个结点，其中6个结点为叶子，则该树中度为2的结点数为5？度为0的结点为6？由性质3：n0=n2+1，则n2=n0-1=6-1=5。4.已知一棵完全二叉树中编号为101的结点有LC和RC结点，则其LC结点编号为202，RC结点编号为203？由性质5，可知左孩子为2i，右孩子为2i+15.一棵深度为h的完全k叉树，如果按层次自顶向下、同一层自左向右、顺序从1开始对全部结点进行编号，试问：该树上最多有多少个结点？最少有多少个结点？由性质1和定义，可知除第h层外，其余各层都是满的，所以：1+k+k2+...+kh-2=(kh-1-1)/(k-1)，则最多有：(kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)；最少有：(kh-1-1)/(k-1)+1三、二叉树的存储结构1、顺序存储结构：特点：一组地址连续的存储单元存储各结点(定义一个一维数组)；自根而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。缺点：空间利用率太低！2、链式存储结构：二叉链表：结点结构至少包含：数据域和左右孩子指针域lchilddatarchild三叉链表：结点结构至少包含：数据域、左右孩子指针域、双亲指针parentlchilddatarchild四、遍历二叉树和线索二叉树1、遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。基本操作是访问结点先(根)序的遍历算法：若二叉树为空树，则空操作；否则，⑴访问根结点；⑵先序遍历左子树；⑶先序遍历右子树。中(根)序的遍历算法：若二叉树为空树，则空操作；否则，⑴中序遍历左子树；⑵访问根结点；⑶中序遍历右子树。后(根)序的遍历算法：若二叉树为空树，则空操作；否则，⑴后序遍历左子树；⑵后序遍历右子树；⑶访问根结点。2、建立二叉树的存储结构：基本要点：以“遍历”为基本出发点；不同的遍历方法相应地有不同的建立算法代码如何由二叉树的先序和中序序列建树？？？3、线索二叉树指向该线性序列中的“前驱”和“后继”的指针，称作“线索”。包含“线索”的存储结构，称作“线索链表”。与其相应的二叉树，称作“线索二叉树”遍历二叉树的结果是，求得结点的一个线性序列。线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索，而前驱或者后续的信息只有在遍历时才能得到，因而线索化的过程即为在遍历的过程中修改空指针的过程。四、树和森林1、树的存储结构①双亲表示法：用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。其中根节点的值为-1②孩子链表表示法：树结点表和孩子结点表为了快速查找每个结点的孩子结点③树的二叉链表(孩子-兄弟)存储表示法：又称二叉树表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向结点的第一个孩子结点和下一个兄弟结点。左边孩子右边兄弟与孩子－兄弟链表对应的二叉树：转化后，二叉树的右子树必为空！2、森林与二叉树的转换给定一棵树，可以找到惟一的一棵二叉树与之对应。——用二叉链表作为存储结构（依据）把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，即作为二叉树的右子树，则同样可以导出森林和二叉树的对应关系。注意：和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。3、树和森林的遍历两种遍历树的方法：①先根(次序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。②后根(次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。森林的遍历：森林由三部分构成：森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树构成的森林。遍历森林：先序遍历：若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。五、哈夫曼树及其应用1、最优二叉树(哈夫曼树)结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度：树中每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和WPL(T)=∑wklk(对所有叶子结点)在所有含n个叶子结点、并带相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。2、如何构造最优树？(赫夫曼算法)以二叉树为例：⑴根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；⑵在F中选取其根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；⑶从F中删去这两棵树，同时加入刚生成的新树；⑷重复(2)和(3)两步，直至F中只含一棵树为止。3、采用二叉树设计二进制前缀编码规定：左分支用“0”表示；右分支用“1”表示。4、算法实现：由于哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点（因n2=n0-1)，可以存储在一个大小为2n-1的一维数组中。5、编码需要从叶子到根；译码需要从根到叶子课后作业P38：6.5P39：6.6(要求：写出推导过程)1.某二叉树的先序遍历结点访问顺序是abdgcefh，中序遍历的访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。2.P41：6.23P41：6.23，然后将该树转化为对应的二叉树。6.26