)
分享目标二叉树、完全二叉树的定义二叉树、完全二叉树的表示和存储二叉树的层序遍历二ヌ树的定义二叉树(Binary tree)是每个结点最多只有两个子结点的树结构。● 树中结点的度都不大于2● 两个子结点分别称为树的左子结点和右子结点● 两个子结点是有左右之分的例如,图的树就是一棵二叉树。2是1的左子结点,3是1的右子结点。2、3的左右子结点都是空。1、下图的树是二叉树吗?NO二叉树所有结点的度都不大于2。而本题结点3的度是3,所有这不是二叉树。2、下面两颗二叉树相同吗?不同二叉树的子结点是有左右之分的。子结点换位置后得到的是一棵新的二叉树。二叉树的基本形态二叉树的基本性质(1)二叉树的基本性质(2)树的深度有两种不同的定义(一般题目中会说明)。不同的深度定义,性质2的公式不相同。如果树的深度的定义是从根结点到最远叶结点所经过的边的数量。结点的数量。性质2:深度为h的二叉树最多有2h1-1个结点(根结点深度为0)根结点深度为0。那么深度为4的二叉树,最多有312h1-1 241-1 31个结点。其中第5层最多有_162i-1 25-116 个结点。可以套用公式,也可以用画图的方式,从根结点开始一层一层添加结点,最后数结点总数。二叉树的基本性质(3)性质3:对于任何一棵二叉树,如果它的叶子结点个数为n0,度为2的结点数为n2,那么一定满足:n0n21例如图,叶子结点有6个。两个分支的结点有5个:a、b、d、c、g。651,满足性质3的描述!(这个公式的证明过程不要求掌握)二ヌ树的表示和存储二叉树一般使用孩子表示法1、结点定义为结构体:(每个结点都包含:结点的值、左孩子和右孩子)structtreenode{//结点的值intleftchild,rightchild;//左右子结点在数组中的下标intdata;};2、结点数组用来保存二叉树:tree node tree[maxn];//树3、结点编码,并保存到数组:· 结点的编码从1开始,编码i的结点保存在数组下标i。· leftchild、rightchild保存左右子结点的下标(编号),如果没有子结点,赋值0或-1。例如,图所示的二叉树,保存到数组之后:满二叉树所有叶结点的深度均相同,且所有非叶结点的子结点数量均为2的二叉树称为满二叉树。简而言之,满二叉树的每一层都完全填满。一棵深度为h的满二叉树一定有2h1-1个结点(根结点深度为0时)。满二叉树也叫完美二叉树。完全二ヌ树对于一棵二叉树,除了最后一层外,每一层都被完全填满,并且最后一层所有结点都靠左且连续,这样的二叉树称为完全二叉树。完全二叉树如果去掉最后一层的所有结点,得到的一定是一棵满二叉树。注意,满二叉树也是一种完全二叉树。完全二叉树的基本性质完全二叉树的数组表示法首先,完全二叉树可以使用二叉树的孩子表示法(结构体)。其次,基于完全二叉树的基本性质,还有更高效简洁的表示法:数组表示法。完全二叉树的数组表示法,就是使用数组表示和存储一个完全二叉树。具体步骤:第一步编号:根结点编号为1,其他结点从上到下、从左到右依次编号。第二步保存:以编号为下标,依次把结点数据存放到一维数组中。例如,使用数组表示法存储右图的完全二叉树:第一步编号:根结点编号为1,其他结点从上到下、从左到右依次编号第二步保存:以编号为下标,依次把结点数据存放到数组中【注意】如果不是完全二叉树,不推荐使用数组表示法。数组表示法的优点:可以方便地访问指定结点的父结点和子结点。完全二叉树的基本性质(1)编号×大于1的结点,它的父结点编号为x/2。(2)结点x的左孩子是2x(2x n时),右孩子是2x1(2x1 n时)。二叉树的深度给定一棵二叉树,求该二叉树的深度。二叉树深度的定义:从根结点到叶结点依次经过的结点形成树的一条路径。最长路径的结点个数(含根、叶结点)为树的深度。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n 10。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】输出一个整型数,表示树的深度。本题要求根据题目给出的每个结点的左右子结点,存储这棵二叉树,然后求出树的深度。树的深度可以使用深度优先搜索(DFS)遍历树来找到最长路径,就是树的深度。· 从根结点出发· 每走一层深度1· 所有结点深度的最大值就是树的深度深搜找二叉树深度的具体步骤:从根结点出发开始搜索(深度为1)如果访问的是空节点(编号为-1),进行回溯。如果访问的是一个非空结点:1)先记录并更新深度的最大值。2)然后递归搜索左右孩子(深度1)。搜索完成后保存的深度的最大值就是树的深度。1、定义结点(结构体)和数组由于不需要考虑每个结点的值,因此结构体只需要存储每个结点的左右孩子即可。structtreenode{intls,rs;//ls:左子结点编号,rs:右子结点编号};tree node tree[11];数组的大小为n1(结点编号从1开始)2、实现dfs递归函数intans;//结点深度的最大值// id:当前结点的编号,depth:这个结点的深度voiddfs(intid,intdepth){if(id1)return;//是空结点,回溯,试其他路径ansmax(ans,depth);//更新最大值// 分别对左右子结点进行dfs,传入子结点的编号和深度// 子结点的深度当前结点深度1dfs(tree[id].ls,depth1);dfs(tree[id].rs,depth1);}3、main函数1)读入输入并保存到树(数组)2)从根结点开始深搜3)输出深度值题目按顺序给出每个结点的左右孩子,因此读入和建树也非常方便,直接按顺序读入即可。intn;// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始深搜//根结点编号1,深度1dfs(1,1);// 输出深度coutans;完整代码#includeiostreamusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号};tree_node tree[11];//数组长度n1,节点编号从1 开始intn,ans;// ans:结点深度的最大值// dfs// id:当前结点的编号,depth:这个结点的深度voiddfs(intid,intdepth){if(id-1)return;//是空结点,回溯,试其他路径ansmax(ans,depth);//更新最大值// 分别对左右子结点进行dfs,传入子节点的编号和深度// 子节点的深度当前结点深度1dfs(tree[id].1s,depth1);dfs(tree[id].rs,depth1);}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始深搜dfs(1,1);//根结点编号1,深度1// 输出深度coutans;return0;}二ヌ树的遍历二叉树常用的遍历方式包括:● 层序遍历● 前序(先序)遍历● 中序遍历● 后序遍历层序遍历:从二叉树根结点开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序访问结点。层序遍历的实现层序遍历的核心在于按照树的层次来访问结点。与广搜(BFS)的原理相同,因此二叉树的层序遍历一般通过BFS实现。1)使用队列(Queue)数据结构2)按层处理结点:根结点第一个入队。每次从队列中取出一个结点,访问该结点的值。将该结点的左、右子结点“先左后右”入队。重复步骤23,直到队列为空,即所有结点都被访问过。二叉树的层序遍历,因此也被称为二叉树的广度优先遍历。#includequeuestructtreenode{intls,rs;intvalue;};tree node tree[MAXN];queueintq;本示例代码:· 队列只保存结点的编号 · 编号0表示空结点 · 空结点不入队voidbfs(){// 根结点,入队q.push(1);while(!q.empty()){// 队首出队intidq.front();q.pop();couttree[id].value ;//子结点(非空)先左后右,入队if(tree[id].ls!0)q.push(tree[id].ls);if(tree[id].rs!0)q.push(tree[id].rs);}}层序遍历的应用(一)层序遍历求二叉树的深度structtreenode{intls,rs;intvalue;intdepth;//结点的深度};1、定义结点结构体 增加一个成员:结点的深度值2、层序遍历:根结点第一个入队。根结点深度为1。每次从队列中取出一个结点。用这个结点的深度值更新深度的最大值。将该结点的左、右子结点“先左后右”入队。并设置子节点深度当前节点深度1。重复步骤2、3,直到队列为空,即所有结点都被访问过。深度的最大值就是二叉树的深度。简而言之,在遍历过程中为访问到的结点更新深度值,同时记录最大值。层序遍历的应用(二)层序遍历判断是否完全二叉树根据完全二叉树的定义:除了最后一层外,每一层都被完全填满(每个结点都有左右子结点),并且所有结点都尽可能地向左对齐。在层序遍历中,遇到一个空结点,并且之后的所有结点都是空结点,那么这是完全二叉树。反之,如果在遇到第一个空结点后,又出现了一个非空结点,那么这棵树就不是完全二叉树。判断完全二叉树给定一棵二叉树,请编程判断是否是完全二叉树。完全二叉树的定义:对于一棵二叉树,除了最后一层外,每一层都被完全填满,并且所有结点都尽可能地向左对齐。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n(1 n 10),根结点为1。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】是完全二叉树输出“YES”,否则输出“NO”。本题首先要求保存指定的二叉树,并判断是否完全二叉树。应用层序遍历进行判断:遇到一个空结点,之后不再遇到非空结点,就是完全二叉树。反之,在遇到一个空结点后,又出现了非空结点,那么就不是完全二叉树。● 本题中空结点编号为-1。● 实现时,层序遍历(广搜)过程中需要把输入的空结点也入队。层序遍历判断完全二叉树的步骤://是否完全二叉树boolisComplettreetrue;//是否遇到空结点boolmetNullfalse;根结点第一个入队。每次从队列中取出一个结点进行处理直到队列为空:1)如果这个结点是空节点,设标记metNull为true。2)否则不是空节点,先查看标记:①如果metNull为true,则说明不是完全二叉树,设isComplettree为false。②否则将该结点的左、右子结点“先左后右”入队。实现层序遍历structtreenode{intls,rs;};tree node tree[11];queueintq;intn;//是否完全二叉树boolisComplettreetrue;//是否遇到过空结点boolmetNullfalse;voidbfs(){// 根结点入队q.push(1);while(!q.empty()){intidq.front();q.pop();if(id-1)//是空节点metNulltrue;else{//不是空节点if(metNull){//并且之前已经遇到过空节点//这不是完全二叉树isComplettreefalse;return;//层序遍历可以终止}// 先左后右,子结点(编号)入队q.push(tree[id].ls);q.push(tree[id].rs);}}}【注意】判断完全二叉树时,子节点不管是否为空都入队突现主函数main函数:1)读入输入并保存到树2)从根结点开始层序遍历3)输出结果intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出结果if(isComplettree)coutYES;elsecoutNO;return0;}完整代码#includeiostream#includequeueusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号}tree_node tree[11];queueintq;//为了节约空间,队列中只保存树的编号intn;boolisComplettreetrue;//是否完全二叉树boolmetNullfalse;//是否遇到过空结点voidbfs(){// 根结点,入队q.push(1);while(!q.empty()){intidq.front();q.pop();if(id-1)//是空节点metNulltrue;else{//不是空节点if(metNull){//并且之前已经遇到过空节点isComplettreefalse;//判断出这不是完全二叉树return;//层序遍历可以终止}// 先左后右,子结点(编号)入队q.push(tree[id].ls);q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出结果if(isComplettree)coutYES;elsecoutNO;return0;}本次分享的知识点二叉树的定义和基本性质二叉树的表示和存储完全二叉树的定义与基本性质完全二叉树的数组表示法二叉树的层序遍历1、以下关于满二叉树的描述,哪一个是准确的?CA、满二叉树的所有节点都有两个子节点B、满二叉树的所有叶子节点都不在同一层C、满二叉树的每一层都完全填满D、满二叉树的节点数必须是2的幂2、根结点的深度为1,具有61个结点的完全二叉树的深度为?DA、7B、8C、5D、6【提示】可以用画图法,从根结点一层一层添加结点,累加结点数。也可以直接用公式:深度为h的二叉树最多有2h-1个结点(根结点深度为1)。二叉树的深度(层序遍历法)给定一棵二叉树,要求用层序遍历的方式求该二叉树的深度。二叉树深度的定义:从根结点到最远叶结点依次经过的结点个数(含根、叶结点)。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n 10。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】输出一个整型数,表示树的深度。【输出样例】32 3-1-1-1-1【输入样例】2#includeiostream#includequeueusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号intdepth;//深度};tree node tree[11];queueintq;//为了节约空间,队列中只保存树的编号intn;intans;//深度最大值voidbfs(){// 根结点编号1,入队tree[1].depth1;q.push(1);while(!q.empty()){intidq.front();q.pop();intdepthtree[id].depth;ansmax(ans,depth);//更新深度最大值// 先左后右,子结点(编号)入队if(tree[id].1s!-1){tree[tree[id].ls].depthdepth1;//设置左子节点的深度q.push(tree[id].1s);}if(tree[id].rs!-1){tree[tree[id].rs].depthdepth1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出coutansendl;return0;} 
长河君 · 2026/8/16 8:22:13 · 阅读 1.2k C++二叉树(一)
分享目标二叉树、完全二叉树的定义二叉树、完全二叉树的表示和存储二叉树的层序遍历二ヌ树的定义二叉树(Binary tree)是每个结点最多只有两个子结点的树结构。● 树中结点的度都不大于2● 两个子结点分别称为树的左子结点和右子结点● 两个子结点是有左右之分的例如,图的树就是一棵二叉树。2是1的左子结点,3是1的右子结点。2、3的左右子结点都是空。1、下图的树是二叉树吗?NO二叉树所有结点的度都不大于2。而本题结点3的度是3,所有这不是二叉树。2、下面两颗二叉树相同吗?不同二叉树的子结点是有左右之分的。子结点换位置后得到的是一棵新的二叉树。二叉树的基本形态二叉树的基本性质(1)二叉树的基本性质(2)树的深度有两种不同的定义(一般题目中会说明)。不同的深度定义,性质2的公式不相同。如果树的深度的定义是从根结点到最远叶结点所经过的边的数量。结点的数量。性质2:深度为h的二叉树最多有2h1-1个结点(根结点深度为0)根结点深度为0。那么深度为4的二叉树,最多有312h1-1 241-1 31个结点。其中第5层最多有_162i-1 25-116 个结点。可以套用公式,也可以用画图的方式,从根结点开始一层一层添加结点,最后数结点总数。二叉树的基本性质(3)性质3:对于任何一棵二叉树,如果它的叶子结点个数为n0,度为2的结点数为n2,那么一定满足:n0n21例如图,叶子结点有6个。两个分支的结点有5个:a、b、d、c、g。651,满足性质3的描述!(这个公式的证明过程不要求掌握)二ヌ树的表示和存储二叉树一般使用孩子表示法1、结点定义为结构体:(每个结点都包含:结点的值、左孩子和右孩子)structtreenode{//结点的值intleftchild,rightchild;//左右子结点在数组中的下标intdata;};2、结点数组用来保存二叉树:tree node tree[maxn];//树3、结点编码,并保存到数组:· 结点的编码从1开始,编码i的结点保存在数组下标i。· leftchild、rightchild保存左右子结点的下标(编号),如果没有子结点,赋值0或-1。例如,图所示的二叉树,保存到数组之后:满二叉树所有叶结点的深度均相同,且所有非叶结点的子结点数量均为2的二叉树称为满二叉树。简而言之,满二叉树的每一层都完全填满。一棵深度为h的满二叉树一定有2h1-1个结点(根结点深度为0时)。满二叉树也叫完美二叉树。完全二ヌ树对于一棵二叉树,除了最后一层外,每一层都被完全填满,并且最后一层所有结点都靠左且连续,这样的二叉树称为完全二叉树。完全二叉树如果去掉最后一层的所有结点,得到的一定是一棵满二叉树。注意,满二叉树也是一种完全二叉树。完全二叉树的基本性质完全二叉树的数组表示法首先,完全二叉树可以使用二叉树的孩子表示法(结构体)。其次,基于完全二叉树的基本性质,还有更高效简洁的表示法:数组表示法。完全二叉树的数组表示法,就是使用数组表示和存储一个完全二叉树。具体步骤:第一步编号:根结点编号为1,其他结点从上到下、从左到右依次编号。第二步保存:以编号为下标,依次把结点数据存放到一维数组中。例如,使用数组表示法存储右图的完全二叉树:第一步编号:根结点编号为1,其他结点从上到下、从左到右依次编号第二步保存:以编号为下标,依次把结点数据存放到数组中【注意】如果不是完全二叉树,不推荐使用数组表示法。数组表示法的优点:可以方便地访问指定结点的父结点和子结点。完全二叉树的基本性质(1)编号×大于1的结点,它的父结点编号为x/2。(2)结点x的左孩子是2x(2x n时),右孩子是2x1(2x1 n时)。二叉树的深度给定一棵二叉树,求该二叉树的深度。二叉树深度的定义:从根结点到叶结点依次经过的结点形成树的一条路径。最长路径的结点个数(含根、叶结点)为树的深度。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n 10。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】输出一个整型数,表示树的深度。本题要求根据题目给出的每个结点的左右子结点,存储这棵二叉树,然后求出树的深度。树的深度可以使用深度优先搜索(DFS)遍历树来找到最长路径,就是树的深度。· 从根结点出发· 每走一层深度1· 所有结点深度的最大值就是树的深度深搜找二叉树深度的具体步骤:从根结点出发开始搜索(深度为1)如果访问的是空节点(编号为-1),进行回溯。如果访问的是一个非空结点:1)先记录并更新深度的最大值。2)然后递归搜索左右孩子(深度1)。搜索完成后保存的深度的最大值就是树的深度。1、定义结点(结构体)和数组由于不需要考虑每个结点的值,因此结构体只需要存储每个结点的左右孩子即可。structtreenode{intls,rs;//ls:左子结点编号,rs:右子结点编号};tree node tree[11];数组的大小为n1(结点编号从1开始)2、实现dfs递归函数intans;//结点深度的最大值// id:当前结点的编号,depth:这个结点的深度voiddfs(intid,intdepth){if(id1)return;//是空结点,回溯,试其他路径ansmax(ans,depth);//更新最大值// 分别对左右子结点进行dfs,传入子结点的编号和深度// 子结点的深度当前结点深度1dfs(tree[id].ls,depth1);dfs(tree[id].rs,depth1);}3、main函数1)读入输入并保存到树(数组)2)从根结点开始深搜3)输出深度值题目按顺序给出每个结点的左右孩子,因此读入和建树也非常方便,直接按顺序读入即可。intn;// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始深搜//根结点编号1,深度1dfs(1,1);// 输出深度coutans;完整代码#includeiostreamusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号};tree_node tree[11];//数组长度n1,节点编号从1 开始intn,ans;// ans:结点深度的最大值// dfs// id:当前结点的编号,depth:这个结点的深度voiddfs(intid,intdepth){if(id-1)return;//是空结点,回溯,试其他路径ansmax(ans,depth);//更新最大值// 分别对左右子结点进行dfs,传入子节点的编号和深度// 子节点的深度当前结点深度1dfs(tree[id].1s,depth1);dfs(tree[id].rs,depth1);}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始深搜dfs(1,1);//根结点编号1,深度1// 输出深度coutans;return0;}二ヌ树的遍历二叉树常用的遍历方式包括:● 层序遍历● 前序(先序)遍历● 中序遍历● 后序遍历层序遍历:从二叉树根结点开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序访问结点。层序遍历的实现层序遍历的核心在于按照树的层次来访问结点。与广搜(BFS)的原理相同,因此二叉树的层序遍历一般通过BFS实现。1)使用队列(Queue)数据结构2)按层处理结点:根结点第一个入队。每次从队列中取出一个结点,访问该结点的值。将该结点的左、右子结点“先左后右”入队。重复步骤23,直到队列为空,即所有结点都被访问过。二叉树的层序遍历,因此也被称为二叉树的广度优先遍历。#includequeuestructtreenode{intls,rs;intvalue;};tree node tree[MAXN];queueintq;本示例代码:· 队列只保存结点的编号 · 编号0表示空结点 · 空结点不入队voidbfs(){// 根结点,入队q.push(1);while(!q.empty()){// 队首出队intidq.front();q.pop();couttree[id].value ;//子结点(非空)先左后右,入队if(tree[id].ls!0)q.push(tree[id].ls);if(tree[id].rs!0)q.push(tree[id].rs);}}层序遍历的应用(一)层序遍历求二叉树的深度structtreenode{intls,rs;intvalue;intdepth;//结点的深度};1、定义结点结构体 增加一个成员:结点的深度值2、层序遍历:根结点第一个入队。根结点深度为1。每次从队列中取出一个结点。用这个结点的深度值更新深度的最大值。将该结点的左、右子结点“先左后右”入队。并设置子节点深度当前节点深度1。重复步骤2、3,直到队列为空,即所有结点都被访问过。深度的最大值就是二叉树的深度。简而言之,在遍历过程中为访问到的结点更新深度值,同时记录最大值。层序遍历的应用(二)层序遍历判断是否完全二叉树根据完全二叉树的定义:除了最后一层外,每一层都被完全填满(每个结点都有左右子结点),并且所有结点都尽可能地向左对齐。在层序遍历中,遇到一个空结点,并且之后的所有结点都是空结点,那么这是完全二叉树。反之,如果在遇到第一个空结点后,又出现了一个非空结点,那么这棵树就不是完全二叉树。判断完全二叉树给定一棵二叉树,请编程判断是否是完全二叉树。完全二叉树的定义:对于一棵二叉树,除了最后一层外,每一层都被完全填满,并且所有结点都尽可能地向左对齐。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n(1 n 10),根结点为1。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】是完全二叉树输出“YES”,否则输出“NO”。本题首先要求保存指定的二叉树,并判断是否完全二叉树。应用层序遍历进行判断:遇到一个空结点,之后不再遇到非空结点,就是完全二叉树。反之,在遇到一个空结点后,又出现了非空结点,那么就不是完全二叉树。● 本题中空结点编号为-1。● 实现时,层序遍历(广搜)过程中需要把输入的空结点也入队。层序遍历判断完全二叉树的步骤://是否完全二叉树boolisComplettreetrue;//是否遇到空结点boolmetNullfalse;根结点第一个入队。每次从队列中取出一个结点进行处理直到队列为空:1)如果这个结点是空节点,设标记metNull为true。2)否则不是空节点,先查看标记:①如果metNull为true,则说明不是完全二叉树,设isComplettree为false。②否则将该结点的左、右子结点“先左后右”入队。实现层序遍历structtreenode{intls,rs;};tree node tree[11];queueintq;intn;//是否完全二叉树boolisComplettreetrue;//是否遇到过空结点boolmetNullfalse;voidbfs(){// 根结点入队q.push(1);while(!q.empty()){intidq.front();q.pop();if(id-1)//是空节点metNulltrue;else{//不是空节点if(metNull){//并且之前已经遇到过空节点//这不是完全二叉树isComplettreefalse;return;//层序遍历可以终止}// 先左后右,子结点(编号)入队q.push(tree[id].ls);q.push(tree[id].rs);}}}【注意】判断完全二叉树时,子节点不管是否为空都入队突现主函数main函数:1)读入输入并保存到树2)从根结点开始层序遍历3)输出结果intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出结果if(isComplettree)coutYES;elsecoutNO;return0;}完整代码#includeiostream#includequeueusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号}tree_node tree[11];queueintq;//为了节约空间,队列中只保存树的编号intn;boolisComplettreetrue;//是否完全二叉树boolmetNullfalse;//是否遇到过空结点voidbfs(){// 根结点,入队q.push(1);while(!q.empty()){intidq.front();q.pop();if(id-1)//是空节点metNulltrue;else{//不是空节点if(metNull){//并且之前已经遇到过空节点isComplettreefalse;//判断出这不是完全二叉树return;//层序遍历可以终止}// 先左后右,子结点(编号)入队q.push(tree[id].ls);q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出结果if(isComplettree)coutYES;elsecoutNO;return0;}本次分享的知识点二叉树的定义和基本性质二叉树的表示和存储完全二叉树的定义与基本性质完全二叉树的数组表示法二叉树的层序遍历1、以下关于满二叉树的描述,哪一个是准确的?CA、满二叉树的所有节点都有两个子节点B、满二叉树的所有叶子节点都不在同一层C、满二叉树的每一层都完全填满D、满二叉树的节点数必须是2的幂2、根结点的深度为1,具有61个结点的完全二叉树的深度为?DA、7B、8C、5D、6【提示】可以用画图法,从根结点一层一层添加结点,累加结点数。也可以直接用公式:深度为h的二叉树最多有2h-1个结点(根结点深度为1)。二叉树的深度(层序遍历法)给定一棵二叉树,要求用层序遍历的方式求该二叉树的深度。二叉树深度的定义:从根结点到最远叶结点依次经过的结点个数(含根、叶结点)。【输入描述】第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n 10。接下来有n行,依次对应二叉树的n个结点。每行有两个整数,分别表示该结点的左儿子和右儿子的结点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子。【输出描述】输出一个整型数,表示树的深度。【输出样例】32 3-1-1-1-1【输入样例】2#includeiostream#includequeueusingnamespacestd;structtreenode{intls,rs;//ls:左孩子结点编号,rs:右孩子结点编号intdepth;//深度};tree node tree[11];queueintq;//为了节约空间,队列中只保存树的编号intn;intans;//深度最大值voidbfs(){// 根结点编号1,入队tree[1].depth1;q.push(1);while(!q.empty()){intidq.front();q.pop();intdepthtree[id].depth;ansmax(ans,depth);//更新深度最大值// 先左后右,子结点(编号)入队if(tree[id].1s!-1){tree[tree[id].ls].depthdepth1;//设置左子节点的深度q.push(tree[id].1s);}if(tree[id].rs!-1){tree[tree[id].rs].depthdepth1;//设置右子节点的深度q.push(tree[id].rs);}}}intmain(){// 读入和保存树cinn;for(inti1;in;i)cintree[i].lstree[i].rs;// 从根结点开始层序遍历bfs();// 输出coutansendl;return0;}