1.层序遍历voidLevelOrder(BTNode*root){Queue q;QueueInit(q);QueuePush(q,root);// 根节点入队while(!QueueEmpty(q)){BTNode*topQueueFront(q);// 取出队首printf(%c ,top-data);// 访问QueuePop(q);// 弹出if(top-left)// 左孩子非空则入队QueuePush(q,top-left);if(top-right)// 右孩子非空则入队QueuePush(q,top-right);}QueueDestroy(q);}层序遍历是什么意思它又被称为广度优先遍历。算法思想层序遍历就是从上到下、从左到右依次访问每个节点。它借助队列实现先将根节点入队。只要队列不为空就重复取出队首节点访问它。如果该节点有左孩子将左孩子入队。如果该节点有右孩子将右孩子入队。这样就能保证先访问第1层再第2层同一层从左到右。我们这里可以画个图给大家来解释一下这里给大家画了第一步后面就不再演示了这里不就是按照上面的逻辑嘛。把根节点弹出插入根节点的左右节点然后再弹出2插入3依次循环即可知道队列为空。2.判断完全二叉树boolBinaryTreeComplete(BTNode*root){Queue q;QueueInit(q);QueuePush(q,root);// 第一阶段按层序遍历直到遇到第一个空节点while(!QueueEmpty(q)){BTNode*topQueueFront(q);QueuePop(q);if(topNULL){break;// 遇到第一个空节点停止入队}// 不管孩子是否为空都入队QueuePush(q,top-left);QueuePush(q,top-right);}// 第二阶段检查队列中剩余的所有节点while(!QueueEmpty(q)){BTNode*topQueueFront(q);QueuePop(q);if(top!NULL){QueueDestroy(q);returnfalse;// 发现非空节点不是完全二叉树}}QueueDestroy(q);returntrue;}判断算法基于层序遍历核心思想利用层序遍历将所有节点的左右孩子包括空节点都入队。当遇到第一个空节点时检查队列中剩余的所有节点如果还有非空节点则说明不是完全二叉树否则是完全二叉树。步骤将根节点入队。循环直到队列为空取出队首节点 top。如果 top NULL则遇到第一个空节点跳出循环。否则将 top-left 和 top-right 入队无论是否为空。然后继续遍历队列剩余部分如果遇到任何一个非空节点则说明不是完全二叉树返回 false。如果全部为空返回 true。关键点为什么遇到第一个空节点就停止入队因为在完全二叉树中一旦出现空节点该层之后的所有节点都应该是空。如果继续入队可能会把后面的非空节点也入队但我们只需要检查队列中已有的节点是否全是空。为什么第一阶段要把空节点也入队这样才能保证我们能够遇到第一个空节点。如果只入队非空节点那么遇到空节点时实际上队列中已经没有该空节点了无法判断。第二阶段检查队列剩余节点这些节点是在遇到第一个空节点之前就已经入队的它们可能是后续的节点。如果其中有非空说明在空节点之后还有节点结构不符合完全二叉树。我给大家再画图演示一下可能会更加清晰一些3.二叉树性质总结一、满二叉树/完全二叉树性质第 i 层最多节点数若规定根结点的层数为 (1)则一棵非空二叉树的第 (i) 层上最多有 (2^{i-1}) 个结点。深度为 h 的二叉树的最大结点数若规定根结点的层数为 (1)则深度为 (h) 的二叉树的最大结点数是 (2^h - 1)此时为满二叉树。满二叉树的深度若规定根结点的层数为 (1)具有 (n) 个结点的满二叉树的深度 (h log_2(n1))(log) 以 (2) 为底。二、一般二叉树性质对任何一棵二叉树如果度为 (0) 的叶结点个数为 (n_0)度为 (2) 的分支结点个数为 (n_2)则有[n_0 n_2 1]4.二叉树的性质小练习4.1题目1某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A .不存在这样的二叉树B .200C .198D .199解析根据二叉树的性质对于任何一棵二叉树叶子结点数 (n_0) 与度为 2 的结点数 (n_2) 满足关系[n_0 n_2 1]已知 (n_2 199)则 (n_0 199 1 200)。选项B正确。4.2 题目2在具有 (2n) 个结点的完全二叉树中叶子结点个数为 A .(n)B .(n1)C .(n-1)D .(n/2)解析我们可以想到完全二叉树的情况是不是要不N1就为1要不N1就根本没有啊那么在这道题里我们想要保证等式右边为偶数左边是不是一定为奇数呀所以在这里N1等于1所以N0等于n因此答案为A。4.3题目3一棵完全二叉树的结点数为 531 个那么这棵树的高度为 A .11B .10C .8D .12解析完全二叉树的高度 (h) 满足深度为 (h) 的满二叉树节点数为 (2^h - 1)深度为 (h-1) 的满二叉树节点数为 (2^{h-1} - 1)。对于此题我们可以使用排除法我们想如果是完全二叉树假设高度为h那么前h-1层是不是都是满的最后一层可能为1也可能是满的对不对所以在本题中因为总节点数为531所以只需看是否满足合适区间就可以了对于A选项2的11次方等于2048就算再减去最后一层也就是最小值也得有1000个往上所以A肯定错同理D选项绝对错我们来看B选项2的10次方等于1024也就是说最多有1023个节点那么最少是不是有511呀5115311023区间合理保险起见我们来看C选项对于C选项2的8次方等于512-1等于511最大都没有达到531所以不可能。综上所述因此答案为B。4.4题目4一个具有 767 个结点的完全二叉树其叶子结点个数为 A .383B .384C .385D .386解析还是同上一样分析因为节点为奇数所以在这里N1等于0因此答案为B。5.链式二叉树遍历小练习5.1题目1某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH。该完全二叉树的前序序列为 A .ABDHEFCGB .ABCDEFGHC .HDBEAFCGD .HDEBFGCA这题还是很简单的先把图画出来就好了因此答案为A。5.2题目2二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK中序遍历HFIEJKG。则二叉树根结点为 A . EB. FC. GD .H此题同理画图即可答案A5.3题目3设一棵二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为____。A .adbceB .decabC .debacD .abcde同理画图所以前序遍历为abcde答案D5.4题目4某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF则按层次输出同一层从左到右的序列为A. FEDCBAB .CABFEDC .DEFCBAD .ABCDEF同上画图因此答案A
数据结构初阶之二叉树收尾
发布时间：2026/5/21 16:55:39
1.层序遍历voidLevelOrder(BTNode*root){Queue q;QueueInit(q);QueuePush(q,root);// 根节点入队while(!QueueEmpty(q)){BTNode*topQueueFront(q);// 取出队首printf(%c ,top-data);// 访问QueuePop(q);// 弹出if(top-left)// 左孩子非空则入队QueuePush(q,top-left);if(top-right)// 右孩子非空则入队QueuePush(q,top-right);}QueueDestroy(q);}层序遍历是什么意思它又被称为广度优先遍历。算法思想层序遍历就是从上到下、从左到右依次访问每个节点。它借助队列实现先将根节点入队。只要队列不为空就重复取出队首节点访问它。如果该节点有左孩子将左孩子入队。如果该节点有右孩子将右孩子入队。这样就能保证先访问第1层再第2层同一层从左到右。我们这里可以画个图给大家来解释一下这里给大家画了第一步后面就不再演示了这里不就是按照上面的逻辑嘛。把根节点弹出插入根节点的左右节点然后再弹出2插入3依次循环即可知道队列为空。2.判断完全二叉树boolBinaryTreeComplete(BTNode*root){Queue q;QueueInit(q);QueuePush(q,root);// 第一阶段按层序遍历直到遇到第一个空节点while(!QueueEmpty(q)){BTNode*topQueueFront(q);QueuePop(q);if(topNULL){break;// 遇到第一个空节点停止入队}// 不管孩子是否为空都入队QueuePush(q,top-left);QueuePush(q,top-right);}// 第二阶段检查队列中剩余的所有节点while(!QueueEmpty(q)){BTNode*topQueueFront(q);QueuePop(q);if(top!NULL){QueueDestroy(q);returnfalse;// 发现非空节点不是完全二叉树}}QueueDestroy(q);returntrue;}判断算法基于层序遍历核心思想利用层序遍历将所有节点的左右孩子包括空节点都入队。当遇到第一个空节点时检查队列中剩余的所有节点如果还有非空节点则说明不是完全二叉树否则是完全二叉树。步骤将根节点入队。循环直到队列为空取出队首节点 top。如果 top NULL则遇到第一个空节点跳出循环。否则将 top-left 和 top-right 入队无论是否为空。然后继续遍历队列剩余部分如果遇到任何一个非空节点则说明不是完全二叉树返回 false。如果全部为空返回 true。关键点为什么遇到第一个空节点就停止入队因为在完全二叉树中一旦出现空节点该层之后的所有节点都应该是空。如果继续入队可能会把后面的非空节点也入队但我们只需要检查队列中已有的节点是否全是空。为什么第一阶段要把空节点也入队这样才能保证我们能够遇到第一个空节点。如果只入队非空节点那么遇到空节点时实际上队列中已经没有该空节点了无法判断。第二阶段检查队列剩余节点这些节点是在遇到第一个空节点之前就已经入队的它们可能是后续的节点。如果其中有非空说明在空节点之后还有节点结构不符合完全二叉树。我给大家再画图演示一下可能会更加清晰一些3.二叉树性质总结一、满二叉树/完全二叉树性质第 i 层最多节点数若规定根结点的层数为 (1)则一棵非空二叉树的第 (i) 层上最多有 (2^{i-1}) 个结点。深度为 h 的二叉树的最大结点数若规定根结点的层数为 (1)则深度为 (h) 的二叉树的最大结点数是 (2^h - 1)此时为满二叉树。满二叉树的深度若规定根结点的层数为 (1)具有 (n) 个结点的满二叉树的深度 (h log_2(n1))(log) 以 (2) 为底。二、一般二叉树性质对任何一棵二叉树如果度为 (0) 的叶结点个数为 (n_0)度为 (2) 的分支结点个数为 (n_2)则有[n_0 n_2 1]4.二叉树的性质小练习4.1题目1某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A .不存在这样的二叉树B .200C .198D .199解析根据二叉树的性质对于任何一棵二叉树叶子结点数 (n_0) 与度为 2 的结点数 (n_2) 满足关系[n_0 n_2 1]已知 (n_2 199)则 (n_0 199 1 200)。选项B正确。4.2 题目2在具有 (2n) 个结点的完全二叉树中叶子结点个数为 A .(n)B .(n1)C .(n-1)D .(n/2)解析我们可以想到完全二叉树的情况是不是要不N1就为1要不N1就根本没有啊那么在这道题里我们想要保证等式右边为偶数左边是不是一定为奇数呀所以在这里N1等于1所以N0等于n因此答案为A。4.3题目3一棵完全二叉树的结点数为 531 个那么这棵树的高度为 A .11B .10C .8D .12解析完全二叉树的高度 (h) 满足深度为 (h) 的满二叉树节点数为 (2^h - 1)深度为 (h-1) 的满二叉树节点数为 (2^{h-1} - 1)。对于此题我们可以使用排除法我们想如果是完全二叉树假设高度为h那么前h-1层是不是都是满的最后一层可能为1也可能是满的对不对所以在本题中因为总节点数为531所以只需看是否满足合适区间就可以了对于A选项2的11次方等于2048就算再减去最后一层也就是最小值也得有1000个往上所以A肯定错同理D选项绝对错我们来看B选项2的10次方等于1024也就是说最多有1023个节点那么最少是不是有511呀5115311023区间合理保险起见我们来看C选项对于C选项2的8次方等于512-1等于511最大都没有达到531所以不可能。综上所述因此答案为B。4.4题目4一个具有 767 个结点的完全二叉树其叶子结点个数为 A .383B .384C .385D .386解析还是同上一样分析因为节点为奇数所以在这里N1等于0因此答案为B。5.链式二叉树遍历小练习5.1题目1某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH。该完全二叉树的前序序列为 A .ABDHEFCGB .ABCDEFGHC .HDBEAFCGD .HDEBFGCA这题还是很简单的先把图画出来就好了因此答案为A。5.2题目2二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK中序遍历HFIEJKG。则二叉树根结点为 A . EB. FC. GD .H此题同理画图即可答案A5.3题目3设一棵二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为____。A .adbceB .decabC .debacD .abcde同理画图所以前序遍历为abcde答案D5.4题目4某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF则按层次输出同一层从左到右的序列为A. FEDCBAB .CABFEDC .DEFCBAD .ABCDEF同上画图因此答案A
