计算机二级公共基础专题探究——二叉树.doc

公共基础专题探究二叉树16 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的基本性质：必考的题目（1）在二叉树的第k层上，最多有2k-1(k1)个结点；（2）深度为m的二叉树最多有2m-1个结点；（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；（4）二叉树中 n = n0 +n1 +n2满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（一般画个图要你把顺序写出来）（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。序号高频考点1树是简单的非线性结构，二叉树作为树的一种也是一种非线性结构。2重点题型：二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子结点总比度为2的结点多一个例1：某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（6）例2：一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（16）【解析】度为2的结点是514个，所以度为1的结点的个数是255416个。例3：某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（7）。 【解析】度为2的结点为110个，所以可以知道本题目中的二叉树的每一个结点都有一个分支，所以共7个结点共7层，即度为7例4：某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（ 48）。【解析】由16个度为2的结点可知叶子结点个数为17，则结点结点总数为16+17+15=48例5：某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层） （12）【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0-1，叶子节点即度为0，n0=1，则n2=0，总节点数为12=n0+n1+n2=1+n1+0，则度为1的节点数n1=11，故深度为12，例6：一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为 （229）【解析】二叉树中，度为0的节点数等于度为2的节点数加1，即n2=n0-1，叶子节点即度为0，则n2=79，总结点数为n0+n1+n2=80+70+79=2293在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。4前序遍历（访问根结点在访问左子树和访问右子树之前）前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：若二叉树为空，则执行空操作。否则：访问根结点；前序遍历左子树；前序遍历右子树，5中序遍历（访问根结点在访问左子树和访问右子树两者之间）6后序遍历（访问根结点在访问左子树和访问右子树之后）7重点题型：二叉树的遍历例1：某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（DCBA ）。【解析】前序序列为ABCD，可知A为根结点。根据中序序列为DCBA可知DCB是A的左子树。根据前序序列可知B是CD的根结点。再根据中序序列可知DC是结点B的左子树。根据前序序列可知，C是D的根结点，故后序序列为DCBA例2：对下列二叉树进行前序遍历的结果为 ABDYECFXZ 例3：设二叉树如下，则后序序列为 DGEBHFCA【解析】本题中前序遍历为ABDEGCFH，中序遍历为DBGEAFHC，后序遍历为DGEBHFCA8完全二叉树指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。例1：深度为7的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（63）【解析】在树结构中，定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1，树的最大层次称为树的深度。深度为6的满二叉树，结点个数为26-1=63，则第7层共有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，加上第6层的最后1个叶子结点，该完全二叉树共有63个叶子结点，故B选项正确。9满二叉树和完全二叉树可以按层序进行顺序存储，一般的二叉树不试用。10堆可以用一维数组储存也可以用完全二叉树来表示堆的结构。11完全二叉树中，若总结点数是偶数，则N1=1，若为奇数，则N1=012深度为i的满二叉树中，N2=2i-1 -1排序二叉树中有序的是中序序列。堆排序问题：题型一：三种序列的转换。（文字叙述型）例1：已知前序序列与中序序列均为ABCDEFGH，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知ABCDEFGH 中：L-D-R 已知ABCDEFGH 后：L-R-D 待求 由此可知，L=0，D-R= ABCDEFGH 故R-D=HGFEDCBA，即后序序列= HGFEDCBA变式训练1：已知后序序列与中序序列均为ABCDEFGH，求前序序列答案：HGFEDCBA，（这次R=0）结论：若前序序列与中序序列均为某序列，则后序序列为该序列的倒序，且为折线；同样地，若后序序列与中序序列均为某序列，则前序序列为该序列的倒序，且为折线例2：已知前序序列=ABCD，中序序列=DCBA，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知ABCD 中：L-D-R 已知DCBA 后：L-R-D 待求因为ABCD与DCBA正好相反，由此可知，R=0所以D-L=ABCD，即L-D=DCBA所以后序序列= DCBA变式训练2-1：中序序列=BDCA，后序序列=DCBA，求前序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 待求 中：L-D-R 已知BDC,A 后：L-R-D 已知DCB,A 通过观察可知，R=0，L=B,D,C，D=A中、后变换时，B,D,C发生了变化，说明左子树结构特殊，进一步令 中：L-D-R 已知B,DC 后：L-R-D 已知DC,B 可知L=0，即D=B，R= DCA可以画出二叉树示意图为：BCD所以前序序列= ABCD变式训练2-2：中序序列=ABC，后序序列=CBA，求前序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 待求 中：L-D-R 已知ABC 后：L-R-D 已知通过观察可知，L=0，D-R=ABC，R-D=CBA 所以前序序列=D-L-R= D-R=ABC变式训练2-3：前序序列=ABC，中序序列=CBA，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知A,BC 中：L-D-R 已知CB,A 后：L-R-D 待求通过观察可知，D=A ，L=B,C，R=0 所以后序序列=CBA (一边偏)题型二：求二叉树的深度 。例1：已知某二叉树共有12个节点，其中叶子结点1个，求深度。（令根节点在第一层）【解析】设叶子结点=N0 ，度为1的节点为N1 ，度为2的节点为N2。 有二叉树的性质3，N0= N2+1 由题，N2= N0-1=0，有总节点数N= N0+ N1+ N2=12， 解得N1=11，故二叉树的图像为一条折线（或直线） 所以深度为12例2：已知二叉树的前序序列=ABCDEFG，中序序列=DCBAEFG，（1）求后序序列（2）求深度。（令根节点在第一层）【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-R 已知A,BCD,EFG 中：L-D-R 已知DCB,A,EFG 后：L-R-D 待求通过观察可知，R= EFG，D=A，L=B,C,D 同理，B为C的父节点，C为D的父节点，且CD在B的同侧可得后=DCB,GFE,AA可以画出二叉树示意图为：EBFCGD由图可知，深度为4题型三：求树的叶子结点数或某度的结点数。例1：【解析】先列一个表，设叶子结点数=nN42N33N23N10N0n有N=（42+33+23+10）+1=24，其中多加的1是根节点然后n=24-2-3-3-0=16变式训练1：【解析】先列一个表，设叶子结点数=nN33N20N14N0n有N=（33+20+14）+1=14，其中多加的1是根节点然后n=14-3-0-4=7例2：【解析】先列一个表，设叶子结点数=nN38N0n有N=（38）+1=25，其中多加的1是根节点然后n=25-8=17变式训练2-1：【解析】先列一个表，设度为3的结点数=nN3nN07有N=（3n）+1=25，其中多加的1是根节点，可知n=8然后725-8=17！ 故：“不存在这样的树”（启示：一定要验算）变式训练2-2：【解析】先列一个表，设度为3的结点数=nN3nN23N14N015有N=（3n）+23+14）+1，其中多加的1是根节点然后15=N-22-n 联立后无整数解 故：“不存在这样的树”（启示：一定要验算）例3：5+1=6题型四：与按层次输出有关的问题。例1：（由层次输出求序列）【解析】第一步，画图：ACBEDGFH 求中序序列：L-D-R，所以是HDB,E,A,FC,G例2：（由序列求层次输出）【解析】设根节点为D0，左子树为L，右子树为R，有遍历