首页 > 代码库 > 求二叉树第K层的叶子节点的个数(假设根节点是第一层)
求二叉树第K层的叶子节点的个数(假设根节点是第一层)
算法思想:采用队列结构按层次遍历,遍历K层时记录叶子的个数
int LeafKlevel(BiTree bt, int k){ //求二叉树bt的第k(k >1)层上叶子的节点个数 if(bt == NULL || k < 1) return 0; BiTree p=bt,Q[]; //Q是队列,元素是二叉树节点的指针 int front = 0,rear = 1,leaf = 0 //front 和 rear 是队头和队尾指针,leaf是叶子节点数 int last = 1,level = 1; //last是二叉树同层最右节点的指针,level是二叉树的层数 Q[1] = p; //根节点进队列 while(front <= rear){ p = Q[++front]; if(level == k && !p->lchild && !p->child) leaf++; //叶子节点 if(p->lchild) Q[++rear] = p->lchild; //左孩子入队 if(p->rchild) Q[++rear] = p->rchild; //右孩子入队 if(front == last){ level++; //二叉树同层最右节点已处理,层数增加一 last = rear; //last移动到下一层的最右一个元素 } if(level > k) return leaf; }//while }
求二叉树第K层的叶子节点的个数(假设根节点是第一层)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。