模具配件东莞网站建设技术支持,两学一做网站答题网址,ps制作网站导航图片,企业网站框架图用按层次顺序遍历二叉树的方法#xff0c;设计算法统计树中度为1的结点数目
代码思路#xff1a; 层序遍历的实现需要借助一个辅助队列 首先将根结点入队#xff0c;然后根出队#xff0c;把根的两个子树入队 然后下面循环执行#xff1a;队头元素出队#xff0c;队头元…用按层次顺序遍历二叉树的方法设计算法统计树中度为1的结点数目
代码思路 层序遍历的实现需要借助一个辅助队列 首先将根结点入队然后根出队把根的两个子树入队 然后下面循环执行队头元素出队队头元素的左右子树入队
举例如下
题目和普通层序遍历唯一不同的就是要统计树中度为1的结点那么我们每次出队头元素入队尾元素时判断一下这个出队的元素它的左右孩子是不是只有一个如果只有一个则count即可
//层次遍历int LevelOrder(BiTNode T) {SqQueue Q;InitQueue(Q);//初始化一个辅助队列BiTree p;EnQueue(Q,T)//根结点入队while(!isEmpty(Q)){DeQueue(Q,p);//队头元素出队用p记录出队列的结点if(p-lchild!NULL){EnQueue(Q,p-lchild);//左子树不空左子树入队if(p-rchildNULL){//p结点度为1左孩子不空右孩子空count;}}if(p-rchild!NULL){EnQueue(Q,p-rchild);//右子树不空右子树入队if(p-lchildNULL){//p结点度为1左孩子空右孩子不空count;}}}return count;
}
