树和二叉树练习题 约定不等于承诺〃 2024-03-31 10:50 53阅读 0赞 #### 文章目录 #### * 一 二叉树的五大性质 * 二 判断题 * 三 填空题 * 四 选择题 * 四 分析求解题 * 五 算法设计题 ## 一 二叉树的五大性质 ## * 性质一：对于一颗二叉树，第i层的最大结点数量为 2 i − 1 2^\{i-1\} 2i−1 * 性质二：对于一颗深度为k的二叉树，可以具有的最大结点数量为: n = 2 0 + 2 1 + 2 2 + . . . + 2 k − 1 n=2^0+2^1+2^2+...+2^\{k-1\} n=20\+21\+22\+...\+2k−1 简化计算 S n = a 1 × ( 1 − q n ) 1 − q = 1 × ( 1 − 2 k ) 1 − 2 = − ( 1 − 2 k ) = 2 k − 1 S\_n=\\frac\{a\_1\\times(1-q^n)\}\{1-q\}=\\frac\{1\\times(1-2^k)\}\{1-2\}=-(1-2^k)=2^k-1 Sn=1−qa1×(1−qn)=1−21×(1−2k)=−(1−2k)=2k−1 * 结论： * 一颗深度为k的二叉树最大结点数量为 2 k − 1 2^k-1 2k−1,结点的边数为 E = n − 1 E=n-1 E=n−1 * 性质三：【记忆】 n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1 * 假设一颗二叉树中度为0、1、2的结点数量为 n 0 、 n 1 、 n 2 n\_0、n\_1、n\_2 n0、n1、n2，由于一棵树二叉树中只有这三种类型的结点，可得结点总数： n = n 0 + n 1 + n 2 n=n\_0+n\_1+n\_2 n=n0\+n1\+n2 * 从二叉树的边数考虑，因为每个结点有且仪有一条边与具交结点相连，那么边数之和就可以表示为 E = n 1 + 2 n 2 E=n\_1+2n\_2 E=n1\+2n2 * 度为1的结点有一条边，度为2的结点有两条边，度为0的结点没有，加在一起就是整棵二叉树的边数之和,可得 E = n − 1 = n 1 + 2 n 2 n = n 1 + 2 n 2 + 1 E=n-1=n\_1+2n\_2 n=n\_1+2n\_2+1 E=n−1=n1\+2n2n=n1\+2n2\+1 * 再结合第一个公式 n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1 * 性质四：【记忆】 * 完全二叉树除了最后一层有空缺外，其他层数都是饱满的，假设这模二叉树为满二叉树，那么根据我们前面得到的性质，假设层数为 k k k，那么结点数量为： n = 2 k − 1 n=2^k-1 n=2k−1，根据完全二叉树的性质，最后一层可以满可以不满，那么一棵完全二叉树结点数 n n n满足： 2 k − 1 − 1 < n < = 2 k − 1 2^\{k-1\}-1<n<=2^k-1 2k−1−1<n<=2k−1 * 因为n肯定是一个整数，那么可以写为 2 k − 1 < = n < = 2 k − 1 2^\{k-1\}<=n<=2^k-1 2k−1<=n<=2k−1 * 现在我们只看左边的不等式，我们对不等式两边同时取对数，得到 k − 1 < = l o g 2 n k-1<=log\_2n k−1<=log2n * 综上所述，***一棵具有n个结点的完全二叉树深度为*** k = ⌊ l o g 2 n ⌋ + 1 k=\\lfloor log\_2n \\rfloor+1 k=⌊log2n⌋\+1 * 性质五： * 一颗有n个结点的完全二叉树，由性质四得到深度为k=log2+1现在对于任意一个结点i，结点的顺序为从上往 下，从左往右： * 对于一个拥有左右孩子的结点来说，其左孩子为 2 i 2i 2i，右孩子为 2 i + 1 2i+1 2i\+1 * 如果 i = 1 i=1 i=1，那么此节点为二叉树的根节点，如果 i > 1 i>1 i>1，那么其父节点为 ⌊ i / 2 ⌋ \\lfloor i/2 \\rfloor ⌊i/2⌋ * 如果 2 i > n 2i>n 2i>n，则结点 i i i没有左孩子 * 如果 2 i + 1 > n 2i+1>n 2i\+1>n，则结点i没有右孩子 ## 二 判断题 ## 1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有 n − 1 n-1 n−1个非空指针域。（ √ ） * 解析： n n n个结点的二叉树，总共有 n − 1 n-1 n−1条边，其对应的二叉链表的非空指针个数等于二叉树的边数 n − 1 n-1 n−1,所以答案正确。 2. 二叉树中每个结点的两棵子树的高度差等于1。 （ × ） * 解析： * 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。 * 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。 * 这是个平衡二叉树的定义，而不是普通二叉树的要求 3. 二叉树中每个结点的两棵子树是有序的。 （ √ ） * 解析：二叉树每个结点的左右子树都有特殊含义【左子树表示其孩子，右子树表示其兄弟】，所以答案正确。 4. 二叉树中每个结点有两棵非空子树或有两棵空子树。 （ × ） * 解析：二叉树中允许存在结点有一颗非空子树【完全二叉树】 5. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 ( × ） * 解析：二叉排序树的特点 6. 二叉树中所有结点个数是 2 k − 1 − 1 2^\{k-1\}-1 2k−1−1，其中 k k k是树的深度。 （ × ） * 解析：由二叉树的性质二可知，树的深度应为 k − 1 k-1 k−1 7. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ） * 解析：二叉树中的结点可以不存在左子树【孩子结点】，同时存在右子树【兄弟结点】 8. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有 2 i − 1 2^i-1 2i−1个结点。（ × ） * 解析：由性质一可得，应为 2 i − 1 2^\{i-1\} 2i−1 9. 用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。（ √ ） * 解析：用二叉链表存储包含n个结点的二叉树，结点共有 2 n 2n 2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有 n − 1 n-1 n−1个结点的链域存放指向非空子女结点的指针，还有 n + 1 n+1 n\+1个空指针。）即有后继链接的指针仅 n − 1 n-1 n−1个。 10. 具有12个结点的完全二叉树有5个度为2的结点。（ √ ） * 解析：叶子数＝ ⌈ n / 2 ⌉ \\lceil n/2 \\rceil ⌈n/2⌉＝6\[向上取整\]，再求 n 2 = n 0 − 1 = 5 n\_2=n\_0-1=5 n2=n0−1=5 11. 一颗完全二叉树有1001个结点，其叶子节点的个数为500（×） * 解析： * 既然是完全二叉树，那么最下面这一排肯定是按顺序排的，并且上面各层应该是排满了的，那么我们先求出层数，根据性质四 k = l o g 2 n + 1 = 9 + 1 = 10 k=log\_2n+1=9+1=10 k=log2n\+1=9\+1=10 * 所以此二叉树的层数为10，也就是说上面9层都是满满当当的，最后一层不满，那么根据性质二，我们求出前9层的结点数 n = 2 k − 1 = 511 n=2^k-1=511 n=2k−1=511 * 那么剩下的结点就都是第十层的了，得到 第 十 层 所 有 叶 子 结 点 数 量 = 1001 − 511 = 490 第十层所有叶子结点数量=1001-511=490 第十层所有叶子结点数量=1001−511=490，因为第十层并不满，剩下的叶子第九层也有，所以最后我们还需要求出第九层的叶子结点数量，先计算第九层的所有结点数量 n = 2 i − 1 = 256 n=2^\{i-1\}=256 n=2i−1=256 * 接着我们需要去掉那些第九层度为一和度为二的结点，其实只需要让第十层都叶子结点除以2就行 n = （ 490 + 1 ） / 2 = 245 n=（490+1）/2=245 n=（490\+1）/2=245 > 注意在除的时候+1，因为有可能会出现一个度为1的结点，此时也需要剔除，所以说+1变成偶数这样才可以正确得到结果。最后剔除这些结点，得到最终结果 n 0 = 256 − 245 + 490 = 501 n\_0=256-245+490=501 n0=256−245\+490=501 * 深入研究 * 探索： * 设叶子节点个数为 n 0 n\_0 n0,度为 1 1 1的节点个数为 n 1 n\_1 n1,度为 2 2 2的节点个数为 n 2 n\_2 n2侧有 n 0 + n 1 + n 2 = n n\_0+n\_1+n\_2=n n0\+n1\+n2=n * 对于二叉树有： n 0 = n 2 + 1 n\_0=n\_2+1 n0=n2\+1 * 可得 n 0 = ( n + 1 − n 1 ) / 2 n\_0=(n+1-n\_1)/2 n0=(n\+1−n1)/2 * 由完全二叉树的性质可知： n 1 = 0 或 1 n\_1=0 或 1 n1=0或1 * 总结: 1. 当n1=0时(即度为1的节点为0个时,此时n为奇数）或者n为奇数时 n 0 = ( n + 1 ) / 2 n\_0= (n+1)/2 n0=(n\+1)/2 2. 当n1=1时(即度为1的节点为1个时,此时n为偶数）或者n为偶数 n 0 = n / 2 n\_0= n/2 n0=n/2 3. 一个具有 n n n个节点的完全二叉树,其叶子节点的个数 n 0 n\_0 n0为: ⌈ n / 2 ⌉ \\lceil n/2 \\rceil ⌈n/2⌉ 向上取整或者 ⌊ ( n + 1 ) / 2 ⌋ \\lfloor (n+1)/2 \\rfloor ⌊(n\+1)/2⌋向下取整 1. 一颗1025个结点的二叉树的层数 k k k的层数范围为 11 − 1205 11-1205 11−1205（ √ ） * 解析：根据性质四可得最小深度为 ⌊ l o g 2 n ⌋ + 1 = 11 \\lfloor log\_2n \\rfloor+1=11 ⌊log2n⌋\+1=11,最大的深度为1005【每层只一个结点】 2. 由一棵树转化而来的二叉树，根节点无右子树。由森林转化而来的二叉树，根节点由有右子树。( √ ) * 解析：一棵树根节点没有兄弟节点，森林中的每棵树的根节点互为兄弟节点。 ## 三 填空题 ## 1. 由３个结点所构成的二叉树有\*\*\*（5 ）\*\*\*种形态。 ![在这里插入图片描述][2873edb26f954cf5b068bb3de324f9f1.png] * 深入研究： * 如果是 N N N个结点的话，利用动态规划进行解答，分析如下： * 假设现在只有一个结点或者没有结点、那么只有一种， h ( 0 ) = h ( 1 ) = 1 h(0)=h(1)=1 h(0)=h(1)=1 * 假设现在有两个结点，那么其中一个拿来做根结点，剩下这一个可以左边可以右边，要么左边零个结点右边一个结点，要么左边一个结点右边零个结点，所以说 h ( 2 ) = h ( 1 ) × h ( 0 ) + h ( 0 ) x h ( 1 ) = 2 h(2)=h(1)×h(0)+h(0)xh(1)=2 h(2)=h(1)×h(0)\+h(0)xh(1)=2 * 假设现在有三个结点，那么依然是其中一个拿来做根节点，剩下的两个结点情况就多了，要么两个都在左边，两个都在右边，或者一边一个，所以说 h ( 3 ) = h ( 2 ) x h ( 0 ) + h ( 1 ) x h ( 1 ) + h ( 1 ) × h ( 2 ) h(3)=h(2)xh(0)+h(1)xh(1)+h(1)×h(2) h(3)=h(2)xh(0)\+h(1)xh(1)\+h(1)×h(2) * 规律: N 每 + 1 N每+1 N每\+1，项数多一项，所以我们只需要按照规律把所有情况的结果相加 int main() { int size; cout<<"请输入结点的总个数:"; cin>>size; int dp[size+1]; dp[0]=dp[1]=1;//没有节点或者只有一个结点直接得到1 for(int i=2;i<=size;i++) { //从2开始进行叠加的计算 dp[i]=0;//一开始 //内层循环，计算所有的情况，如i=3,计算dp[0]*dp[2],dp[1]*dp[1],dp[2]*dp[0] for(int j=0;j<i;j++) { dp[i]+=dp[j]*dp[i-j-1]; } } cout<<"二叉树的种类总数为:"<<dp[size]<<endl; return 0; } ![在这里插入图片描述][425a565585ad4ef89e9f4037d0f2be1c.png] * 这个数列其实其***卡特兰数***，其通项公式为： C n = 1 n + 1 C 2 n n = 1 n + 1 × ( 2 n ) ! n ! × ( 2 n − n ) ! = ( 2 n ) ! n ! × ( n + 1 ) ! C\_n=\\frac\{1\}\{n+1\}C\_\{2n\}^\{n\}=\\frac\{1\}\{n+1\}\\times\\frac\{(2n)!\}\{n!\\times(2n-n)!\}=\\frac\{(2n)!\}\{n!\\times(n+1)!\} Cn=n\+11C2nn=n\+11×n!×(2n−n)!(2n)!=n!×(n\+1)!(2n)! int factorial(int n) { int res=1; for(int i=2;i<=n;i++) res*=i; return res; } int main() { int n; cout<<"请输入结点的总个数:"; cin>>n; cout<<"二叉树的种类总数为:"; cout<<factorial(2*n)/(factorial(n)* factorial(n+1)); return 0; } ![在这里插入图片描述][61bedec36b2c4dc1a4b01c43deacab55.png] 1. 一棵深度为6的满二叉树有 ***(31)*** 个分支结点和 ***(32)*** 个叶子。 * 解析： * 满二叉树没有度为 1 1 1的结点，所以分支结点数就是度 2 2 2为结点数。 * 满二叉树的最后一层的结点都是叶子节点，个数为 n 0 = 2 6 − 1 = 32 n\_0=2^\{6-1\}=32 n0=26−1=32 * 分支结点的个数为 n 1 + n 2 = 0 + n 2 = n 0 − 1 = 31 n\_1+n\_2=0+n\_2=n\_0-1=31 n1\+n2=0\+n2=n0−1=31 1. 一棵具有 257 257 257个结点的完全二叉树，它的深度为 ***(9)*** 。 * 解析： ⌊ l o g 2 ( n ) ⌋ + 1 = 8 + 1 = 9 \\lfloor log\_2(n) \\rfloor+1=8+1=9 ⌊log2(n)⌋\+1=8\+1=9 2. 设一棵完全二叉树有700个结点，则共有 ***(350)*** 个叶子结点。 * 解析： ⌈ n / 2 ⌉ ＝ 350 \\lceil n/2 \\rceil＝350 ⌈n/2⌉＝350 3. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 ***(500)*** 个叶子结点，有 ***(499)*** 个度为2的结点，有 ***(1)*** 个结点只有非空左子树，有 ***(0)*** 个结点只有非空右子树。 * 解析：用叶子数 ⌈ n / 2 ⌉ ＝ 500 \\lceil n/2 \\rceil＝500 ⌈n/2⌉＝500 ， n 2 = n 0 − 1 = 499 n\_2=n\_0-1=499 n2=n0−1=499。 另外，最后一结点为 2 i 2i 2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝ 0 0 0. 4. 【有坑】一棵含有n个结点的k叉树，可能达到的最大深度为 ***n*** ，最小深度为 ***2*** 。 * 解析： * 当 k = 1 k=1 k=1(单叉树)时应该最深，深度＝n（层）； * 当 k = n − 1 k=n-1 k=n−1（n-1叉树）时应该最浅，深度＝2（层），但不包括n=0或1时的特例情况. * 类似的题目： * 深度为 h h h的满 m m m叉树的第 k k k层有多少个结点? * 类比于二叉树的性质一，可得 n = m k − 1 n=m^\{k-1\} n=mk−1 5. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 ***L R N*** 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 ***F E G H D C B*** 。 * 解析：先由已知条件画图，再后序遍历得到结果； ![在这里插入图片描述][83d6959edc6d407b849bace7702639f6.png] 6. 中序遍历的递归算法平均空间复杂度为 ***O ( n ) O(n) O(n)*** 。 \-解析：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度 k + 1 k+1 k\+1，包括叶子的空域也递归了一次。 7. 用5个权值\{3, 2, 4, 5, 1\}构造的哈夫曼（Huffman）树的带权路径长度是 33 。 * 解析：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×3=33 ![在这里插入图片描述][5e8bcf64d58847d091db6d4018280d3c.png] ## 四 选择题 ## 1. 不含任何结点的空树 ***（ C ）*** 。 （Ａ）是一棵树; （Ｂ）是一棵二叉树; ***（Ｃ）是一棵树也是一棵二叉树;*** （Ｄ）既不是树也不是二叉树 2. 二叉树是非线性数据结构，所以 ***（ C ）*** 。 （Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储; ***（Ｃ）顺序存储结构和链式存储结构都能存储;*** （Ｄ）顺序存储结构和链式存储结构都不能使用 3. 具有n(n>0)个结点的完全二叉树的深度为 ***（ C ）*** 。 (Ａ) ⌈ l o g 2 ( n ) ⌉ \\lceil log\_2(n) \\rceil ⌈log2(n)⌉ (Ｂ) ⌊ l o g 2 ( n ) ⌋ \\lfloor log2(n) \\rfloor ⌊log2(n)⌋ (Ｃ) ⌊ l o g 2 ( n ) ⌋ \\lfloor log2(n) \\rfloor ⌊log2(n)⌋\+1 (Ｄ) ⌈ l o g 2 ( n ) + 1 ⌉ \\lceil log\_2(n)+1 \\rceil ⌈log2(n)\+1⌉ * 解析：由性质四即可解答 1. 把一棵树转换为二叉树后，这棵二叉树的形态是 ***（ A ）*** 。 （Ａ）唯一的 （Ｂ）有多种 （Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 2. 树是结点的有限集合，它***A*** 根结点，记为T。其余的结点分成为m（m≥0）个 ***B*** 的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子结点个数为该结点的 ***C*** 。 供选择的答案 * A： * ***①有0个或1个*** * ②有0个或多个 * ③有且只有1个 * ④有1个或1个以上 * B: * ***①互不相交*** * ② 允许相交 * ③ 允许叶结点相交 * ④ 允许树枝结点相交 * C： * ①权 * ② 维数 * ***③ 次数（或度）*** * ④ 序 * 解析：ABC＝1，1，3 1. 二叉树 ***A*** 。在完全的二叉树中，若一个结点没有 ***B*** ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 ***C*** ，而N的右子女是它在原树里对应结点的 ***D*** 。 * A： * ①是特殊的树 * ***②不是树的特殊形式*** * ③是两棵树的总称 * ④有是只有二个根结点的树形结构 * B: * ***①左子结点*** * ② 右子结点 * ③ 左子结点或者没有右子结点 * ④ 兄弟 * C～D： * ***①最左子结点*** * ② 最右子结点 * ***③ 最邻近的右兄弟*** * ④ 最邻近的左兄弟 * ⑤ 最左的兄弟 * ⑥ 最右的兄弟 * 答案：ABCDE＝2，1，1，3 ## 四 分析求解题 ## 1. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。 ![在这里插入图片描述][75d7b5ccdb1a49ebaed41411621c004a.png] 2. 给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 ![在这里插入图片描述][7ccd0f506aea43fcb59ecb4d593395ff.png] * 解：要遵循中序遍历的轨迹来画出每个前驱和后继。 * 中序遍历序列：55 40 25 60 28 08 33 54 1. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 ![在这里插入图片描述][398f6d2bd00e44b4beb75296b98eb580.png] * 前序DLR：A B D F J G K C E H I L M * 中序LDR: B F J D G K A C H E L I M * 后序LRD：J F K G D B H L M I E C A 1. 把如图所示的树转化成二叉树 ![在这里插入图片描述][29495870f57d49a19ba12c4fbbcc5c22.png] * 解答 ![在这里插入图片描述][4d2dc01f6bb54488ae5f1b7f18eabb9c.png] 5．画出和下列二叉树相应的森林。 答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。 ![在这里插入图片描述][be42707ad49c49c282fbb69c3af99872.png] 1. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 ![在这里插入图片描述][2f84b322f3dd45968d89ef804f46db04.png] ## 五 算法设计题 ## 1. 编写递归算法，计算二叉树中叶子结点的数目。 思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。 法一：核心部分为： DLR(liuyu *root) /*中序遍历 递归函数*/ { if (root!=NULL) { if ((root->lchild==NULL)&&(root->rchild==NULL)){ sum++; printf ("%d\n",root->data);} DLR (root->lchild); DLR (root->rchild); } Return (0); } 法二： int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 { If (!T) return 0; //空树没有叶子 else if (!T->lchild&&!T->rchild) return 1; //叶子结点 else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加 上右子树的叶子数 }//LeafCount_BiTree 1. 写出求二叉树深度的算法。 设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。 但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/ { int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0; if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{ d=depth(root->lchild); if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; } p=p+1; return(p); } 法二： int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 { if(T->data==x) { printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度 exit 1; } } else { if(T->lchild) Get_Sub_Depth(T->lchild,x); if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 } }//Get_Sub_Depth int Get_Depth(Bitree T)//求子树深度的递归算法 { if(!T) return 0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; } }//Get_Depth 1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。 技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。 Level (liuyu*T) /* liuyu *T,*p,*q[100]; 假设max已知*/ { int f,r; f=0; r=0; /*置空队*/ r=(r+1)%max; q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ { f=(f+1%max); p=q[f]; /*出队*/ printf("%d",p->data); /*打印根结点*/ if(p->lchild){ r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){ r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ } return(0); } 法二： void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 1. 编写算法判别给定二叉树是否为完全二叉树。 int IsFull_Bitree (Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { { DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree 分析：该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针. [2873edb26f954cf5b068bb3de324f9f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/532525513f4f42b9b603dac164cd2e61.png [425a565585ad4ef89e9f4037d0f2be1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2d7d9fb9d63e46829e54d29b868fbabd.png [61bedec36b2c4dc1a4b01c43deacab55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b230c30405a5401397eec14e4f0e149c.png [83d6959edc6d407b849bace7702639f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/193220f6a5ac42a7a8cbbcc22344c652.png [5e8bcf64d58847d091db6d4018280d3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e833091ce4044f81b06b5bcc2af5805d.png [75d7b5ccdb1a49ebaed41411621c004a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e028508dab36484aa455c0efb30f0e07.png [7ccd0f506aea43fcb59ecb4d593395ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/770042b03a9c48f1a9ee0d027d69c438.png [398f6d2bd00e44b4beb75296b98eb580.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5c7eafdb770c4f278e88003bcf0179dd.png [29495870f57d49a19ba12c4fbbcc5c22.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3abb1636e51d471ca5301ea600c2983e.png [4d2dc01f6bb54488ae5f1b7f18eabb9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c70d0901d52048b389a525115c2c6e55.png [be42707ad49c49c282fbb69c3af99872.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3a4e1bf2debe40d68d178fc9f7578f5f.png [2f84b322f3dd45968d89ef804f46db04.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2b69ca57610c4e449bd551d9749c8c97.png
相关 树和二叉树练习题 文章目录 一 二叉树的五大性质 二 判断题 三 填空题 四 选择题 四 分析求解题 五 算法设计题 一 二叉树的五大性质 约定不等于承诺〃/ 2024年03月31日 10:50/ 0 赞/ 54 阅读
相关 树和二叉树 树和二叉树 一、基本术语 二、性质 三、前/中/后序遍历 四、霍夫曼树（满二叉树） 五、图的遍历 一、基本术语 1. 树结点：包含 谁借莪１个温暖的怀抱￠/ 2023年10月05日 14:41/ 0 赞/ 25 阅读
相关 二叉树和排序二叉树 二叉树 > 相关名词 > > 根节点 > > 左叶子节点 > > 右叶子节点 > > 子树 > > 高度 > 二叉树的排序方式： > > - 广度遍历（ 灰太狼/ 2023年08月17日 16:53/ 0 赞/ 230 阅读
相关 树和二叉树 树型结构是一类重要的非线性数据结构. 树是n个结点的有限集.树的结构定义是一个递归定义,即在树的定义中又用到树的概念,它道出树的固有特性. 树的结点包含一个 骑猪看日落/ 2023年07月01日 15:56/ 0 赞/ 2 阅读
相关 树和二叉树 一、树的概述 1. 树结构概述 根节点：该节点没有父节点 双亲结点：有父节点和子节点 子节点：一个节点的下面一个节点为子节 拼搏现实的明天。/ 2023年06月23日 06:54/ 0 赞/ 33 阅读
相关 树和二叉树 树的定义 树（Tree）是n(n>=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m(m>0) 末蓝、/ 2022年06月08日 00:49/ 0 赞/ 230 阅读
相关 树和二叉树 树 > 不同于队列、栈等一对一的数据结构，树是一对多的数据结构。树（Tree）是n（n>=0）各节点的有限集。当n=0，为空树。 在任意一颗非空树中： 1. 有且只 落日映苍穹つ/ 2022年05月16日 01:36/ 0 赞/ 300 阅读
相关 二叉树、满二叉树、完全二叉树、平衡二叉树（AVL树） 二叉树： -------------------- 二叉树由节点（node）和边组成。节点分为根节点、父节点、子节点。 二叉树是每个结点最多有两个子树的树结构。 
约定不等于承诺〃
灰太狼
骑猪看日落
太过爱你忘了你带给我的痛
柔情只为你懂
还没有评论，来说两句吧...