《计算机二级公共基础专题探究二叉树》由会员分享，可在线阅读，更多相关《计算机二级公共基础专题探究二叉树（13页珍藏版）》请在金锄头文库上搜索。
1、word公共根底专题探究二叉树16 树与二叉树树是一种简单的非线性结构，所有元素之间具有明显的层次特性。在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点：1非空二叉树只有一个根结点；2每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的根本性质：必考的题目1在二叉树的第k层上，最多有2k-1(k1)个结点；2深度为m的二叉树最多有2m-1个结点；3度为0的结点即叶子结点
2、总是比度为2的结点多一个；4二叉树中 n = n0 +n1 +n2满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，如此k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的假如干结点。二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进展顺序存储。二叉树的遍历：一般画个图要你把顺序写出来1前序遍历DLR，首先访问根结点，然后遍历左子树，最后遍历右子树；2中序遍历LDR，首先遍历左子树，然后访问根结点，最后遍历右子树；3后序遍历LRD首先遍历左子树，然后访问遍历右子树，最后访问根结点。
3、序号高频考点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：某二叉树
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的节点数等于度
5、为2的节点数加1，即n2=n0-1，叶子节点即度为0，如此n2=79，总结点数为n0+n1+n2=80+70+79=2293在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。4前序遍历访问根结点在访问左子树和访问右子树之前前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。前序遍历描述为：假如二叉树为空，如此执行空操作。否如此：访问根结点；前序遍历左子树；前序遍历右子树，5中序遍历访问根结点在访问左子树和访问右子树两者之间6后序遍历访问
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完全二叉树指除最后一层外，每一层
7、上的结点数均达到最大值，在最后一层上只缺少右边的假如干结点。例1：深度为7的完全二叉树中共有125个结点，如此该完全二叉树中的叶子结点数为63【解析】在树结构中，定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1，树的最大层次称为树的深度。深度为6的满二叉树，结点个数为26-1=63，如此第7层共有125-63=62个叶子结点，分别挂在第6层的左边62个结点上，加上第6层的最后1个叶子结点，该完全二叉树共有63个叶子结点，故B选项正确。9满二叉树和完全二叉树可以按层序进展顺序存储，一般的二叉树不试用。10堆可以用一维数组储存也可以用完全二叉树来表示堆的结构。11完
8、全二叉树中，假如总结点数是偶数，如此N1=1，假如为奇数，如此N1=012深度为i的满二叉树中，N2=2i-1 -1排序二叉树中有序的是中序序列。堆排序问题：题型一：三种序列的转换。文字表示型例1：前序序列与中序序列均为ABCDEFGH，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-RABCDEFGH中：L-D-RABCDEFGH 后：L-R-D待求 由此可知，L=0，D-R= ABCDEFGH故R-D=HGFEDCBA，即后序序列=HGFEDCBA变式训练1：后序序列与中序序列均为ABCDEFGH，求前序序列答案：HGFEDCBA，这次R=0结论：假如前
9、序序列与中序序列均为某序列，如此后序序列为该序列的倒序，且为折线；同样地，假如后序序列与中序序列均为某序列，如此前序序列为该序列的倒序，且为折线例2：前序序列=ABCD，中序序列=DCBA，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-RABCD中：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-RB
10、DC,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，中序序列
11、=CBA，求后序序列【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-RA,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，中序序列=
12、DCBAEFG，1求后序序列2求深度。令根节点在第一层【解析】设根节点为D0，左子树为L，右子树为R，有遍历顺序为：前：D-L-RA,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变式训
13、练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，有遍历顺序为：前：D-L-R A,BDEGH,CFIJ A为第一层根结点中：L-D-R DBGEH,A,CIFJ通过观察可知，R=C,F,I,J ，L=D,B,G,E,H ，D=A对第一层的第二层L，前：D-L-R B,D,EGH B为第二层左结点中：L-D-R D,B,GE
