二叉树k层的叶子结点个数

news/2024/12/29 19:47:35/

文章目录

  • 1 题目
  • 2 思路
    • 2.1 思路1
    • 2.2 思路2
  • 3 代码实现
    • 3.1 思路1
    • 3.2 思路2
    • 3.3 完整的代码案例

1 题目

假设二叉树采用二叉链表存储结构，设计一个算法求其指定的第k层（k>1，跟是第1层）的叶子结点个数。

2 思路

2.1 思路1

设置一个全局变量记录某层叶子结点个数，前序遍历二叉树，并在遍历的过程中记录结点的层数。

2.2 思路2

层序遍历二叉树，记录某层的二叉树叶子结点个数。没有目标层时，让该层结点的孩子结点入队；到达目标层时，不再让该层的孩子结点入队，统计队中（该层）叶子结点的个数。

  • 具体流程
    • 设置两个指针分别指该层的最后一个结点lastNode（初始为根结点）和下一层的最后一个非叶结点newNode。
    • 每遍历到结点的左/右孩子为非叶结点时，把newNode更新为当前结点的左/右孩子；
    • 当遍历的结点为该层的最后结点时，把lastNode更新为最新的newNode。

3 代码实现

二叉树的存储结构：

template <typename T>
class BiTNode {
public:T data;BiTNode* left;BiTNode* right;BiTNode():data(NULL),left(NULL),right(NULL){};
};template <>
class BiTNode<int> {
public:int data;BiTNode* left;BiTNode* right;BiTNode() : data(0), left(nullptr), right(nullptr) {}BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};template <>
class BiTNode<char> {
public:char data;BiTNode* left;BiTNode* right;BiTNode() : data('\0'), left(nullptr), right(nullptr) {}BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};

3.1 思路1

template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){if(level < k){if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);}else if(level == k && root->left == nullptr && root->right == nullptr){leafNum++;}
} template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){calLevelLeaf(root, 1,  k);return leafNum;
}

3.2 思路2

template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){deque<BiTNode<T>*> q;//双端队列BiTNode<T> *newNode = nullptr, *lastNode = root;  int level = 1;//层数int leafNum = 0;//该层的叶子结点个数q.push_back(root);while(!q.empty()){BiTNode<T>* p;if(level == k){while(!q.empty()){p = q.front();q.pop_front();if(p->left == nullptr && p->right == nullptr){leafNum++;}}break;}else{p = q.front();q.pop_front();if(p->left != nullptr){q.push_back(p->left);newNode = p->left;}if(p->right != nullptr){q.push_back(p->right);newNode = p->right;}if(lastNode == p){lastNode = newNode;level += 1;}}}return leafNum;
}

3.3 完整的代码案例

#include <iostream>
#include <stack>
#include <deque>
#include <queue>
using namespace std;template <typename T>
class BiTNode {
public:T data;BiTNode* left;BiTNode* right;BiTNode():data(NULL),left(NULL),right(NULL){};
};template <>
class BiTNode<int> {
public:int data;BiTNode* left;BiTNode* right;BiTNode() : data(0), left(nullptr), right(nullptr) {}BiTNode(int x) : data(x), left(nullptr), right(nullptr) {}BiTNode(int x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};template <>
class BiTNode<char> {
public:char data;BiTNode* left;BiTNode* right;BiTNode() : data('\0'), left(nullptr), right(nullptr) {}BiTNode(char x) : data(x), left(nullptr), right(nullptr) {}BiTNode(char x, BiTNode *left, BiTNode *right) : data(x), left(left), right(right) {}
};template <typename T>
void createBiTNode(BiTNode<T>** treeNode, deque<T>dataDeq) {//层序遍历建立二叉树//特殊处理根结点T data;data = dataDeq.front();dataDeq.pop_front();BiTNode<T> * node = new BiTNode<T>();*treeNode = node;(*treeNode)->data = data;deque<BiTNode<T>**> nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index = 2;//用于判定左右孩子（左偶，右奇）while (!dataDeq.empty()){//当数据节点非空时，进行建树BiTNode<T>** nodeParent = nodeDeq.front();nodeDeq.pop_front();for(int i = 0; i < 2;i++){data = dataDeq.front();dataDeq.pop_front();if(data == '#'){//适用于char//if(data == -1){//适用于intif(index%2 == 0) (*nodeParent)->left = nullptr;else (*nodeParent)->right = nullptr;}else{BiTNode<T> * node = new BiTNode<T>();node->data = data;if(index%2 == 0){(*nodeParent)->left = node;nodeDeq.push_back(&(*nodeParent)->left);}else{(*nodeParent)->right = node;nodeDeq.push_back(&(*nodeParent)->right);}}index++;}}
}template <>
void createBiTNode<char>(BiTNode<char>** treeNode, deque<char>dataDeq) {//层序遍历建立二叉树//特殊处理根结点char data;data = dataDeq.front();dataDeq.pop_front();BiTNode<char> * node = new BiTNode<char>();*treeNode = node;(*treeNode)->data = data;deque<BiTNode<char>**> nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index = 2;//用于判定左右孩子（左偶，右奇）while (!dataDeq.empty()){//当数据节点非空时，进行建树BiTNode<char>** nodeParent = nodeDeq.front();nodeDeq.pop_front();for(int i = 0; i < 2;i++){data = dataDeq.front();dataDeq.pop_front();if(data == '#'){if(index%2 == 0) (*nodeParent)->left = nullptr;else (*nodeParent)->right = nullptr;}else{BiTNode<char> * node = new BiTNode<char>();node->data = data;if(index%2 == 0){(*nodeParent)->left = node;nodeDeq.push_back(&(*nodeParent)->left);}else{(*nodeParent)->right = node;nodeDeq.push_back(&(*nodeParent)->right);}}index++;}}
}template <>
void createBiTNode<int>(BiTNode<int>** treeNode, deque<int>dataDeq) {//层序遍历建立二叉树//特殊处理根结点char data;data = dataDeq.front();dataDeq.pop_front();BiTNode<int> * node = new BiTNode<int>();*treeNode = node;(*treeNode)->data = data;deque<BiTNode<int>**> nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index = 2;//用于判定左右孩子（左偶，右奇）while (!dataDeq.empty()){//当数据节点非空时，进行建树BiTNode<int>** nodeParent = nodeDeq.front();nodeDeq.pop_front();for(int i = 0; i < 2;i++){data = dataDeq.front();dataDeq.pop_front();if(data == -1){if(index%2 == 0) (*nodeParent)->left = nullptr;else (*nodeParent)->right = nullptr;}else{BiTNode<int> * node = new BiTNode<int>();node->data = data;if(index%2 == 0){(*nodeParent)->left = node;nodeDeq.push_back(&(*nodeParent)->left);}else{(*nodeParent)->right = node;nodeDeq.push_back(&(*nodeParent)->right);}}index++;}}
}template <typename T>
void inOrder(BiTNode<T>* treeNode){if(treeNode){inOrder(treeNode->left);cout<<treeNode->data<<" ";inOrder(treeNode->right);}
}template <typename T>
void preOrder(BiTNode<T>* treeNode){if(treeNode){cout<<treeNode->data<<" ";preOrder(treeNode->left);preOrder(treeNode->right);}
}template <typename T>
void postOrder(BiTNode<T>* treeNode){if(treeNode){postOrder(treeNode->left);postOrder(treeNode->right);cout<<treeNode->data<<" ";}
}template <typename T>
void preOrder2(BiTNode<T>* treeNode){stack<BiTNode<T>*> s;BiTNode<T>* p = treeNode;while(p || !s.empty()){if(p){cout<<p->data<<" ";s.push(p);p = p->left;}else{p = s.top();s.pop();p = p->right;}}
}template <typename T>
void inOrder2(BiTNode<T>* treeNode){stack<BiTNode<T>*> s;BiTNode<T>* p = treeNode;while(p || !s.empty()){if(p){s.push(p);p = p->left;}else{p = s.top();cout<<p->data<<" ";s.pop();p = p->right;}}
}template <typename T>
void postOrder2(BiTNode<T>* treeNode){stack<BiTNode<T>*> s;BiTNode<T> *p = treeNode, *r = nullptr;while(p || !s.empty()){if(p){s.push(p);p = p->left;}else{p = s.top();if(p->right && p->right != r){//有右孩子且没有访问过p = p->right;}else{cout<<p->data<<" ";s.pop();r = p;p = nullptr;}}}
}template <typename T>
void levelOrder(BiTNode<T>* treeNode) {queue<BiTNode<T>*> nodeQue;BiTNode<T>* p = treeNode;nodeQue.push(p);while(!nodeQue.empty()){p = nodeQue.front();nodeQue.pop();cout<<p->data<<" ";if(p->left) nodeQue.push(p->left);if(p->right) nodeQue.push(p->right);}
}int leafNum = 0;template <typename T>
void calLevelLeaf(BiTNode<T>* root, int level, int k){if(level < k){if(root->left != nullptr) calLevelLeaf(root->left, level+1, k);if(root->right != nullptr) calLevelLeaf(root->right, level+1, k);}else if(level == k && root->left == nullptr && root->right == nullptr){leafNum++;}
} template <typename T>
int getLevelLeaf(BiTNode<T>* root, int k){calLevelLeaf(root, 1,  k);return leafNum;
}template <typename T>
int getLevelLeaf2(BiTNode<T>* root, int k){deque<BiTNode<T>*> q;//双端队列BiTNode<T> *newNode = nullptr, *lastNode = root;  int level = 1;//层数int leafNum = 0;//该层的叶子结点个数q.push_back(root);while(!q.empty()){BiTNode<T>* p;if(level == k){while(!q.empty()){p = q.front();q.pop_front();if(p->left == nullptr && p->right == nullptr){leafNum++;}}break;}else{p = q.front();q.pop_front();if(p->left != nullptr){q.push_back(p->left);newNode = p->left;}if(p->right != nullptr){q.push_back(p->right);newNode = p->right;}if(lastNode == p){lastNode = newNode;level += 1;}}}return leafNum;
}int main() {//使用字符串//deque<char> treeVec{'a', 'b', 'c', 'd', 'e', '#', '#'};//deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', '#','i','#','#','k','l'};deque<char> treeVec{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', '#', 'i', 'j','#','#','k','l','m','n','#','#','o','#','#','p','#','#'};BiTNode<char>* tree = new BiTNode<char>();createBiTNode(&tree, treeVec);//使用数值
//    deque<int> treeVec{1, 2, 3, 4, 5, -1, -1};
//    BiTNode<int>* tree = new BiTNode<int>();
//    createBiTNode(&tree, treeVec);//遍历树//inOrder(tree);//cout<<endl;printf("%d", getLevelLeaf2(tree, 5));//tree,4return 0;    
}

http://www.ppmy.cn/news/1255441.html

相关文章

分享一个国内可用的免费AI-GPT网站

分享一个国内可用的免费AI-GPT网站

背景 ChatGPT作为一种基于人工智能技术的自然语言处理工具&#xff0c;近期的热度直接沸腾&#x1f30b;。 我们也忍不住做了一个基于ChatGPT的网站&#xff0c;可以免登陆&#xff01;&#xff01;国内可直接对话AI&#xff0c;也有各种提供工作效率的工具供大家使用。 可以这…
阅读更多...
【计算机视觉】基于OpenCV计算机视觉的摄像头测距技术设计与实现

【计算机视觉】基于OpenCV计算机视觉的摄像头测距技术设计与实现

基于计算机视觉的摄像头测距技术 文章目录 基于计算机视觉的摄像头测距技术导读引入技术实现原理技术实现细节Python-opencv实现方案获取目标轮廓步骤 1&#xff1a;图像处理步骤 2&#xff1a;找到轮廓步骤完整代码 计算图像距离前置技术背景与原理步骤 1&#xff1a;定义距离…
阅读更多...
如何查看JDK动态代理自动生成的类

如何查看JDK动态代理自动生成的类

JDK提供了一种强大且灵活的机制，可以在运行时生成代理类。这种动态生成的代理类可以在不修改原始类的情况下，对其方法进行拦截和增强。然而，对于初学者来说，了解生成的代理类的内部结构和工作原理可能会很有帮助。 本文将介绍如何查看JDK动态代理生成的代理类。我们将探索一…
阅读更多...
行为型剩余的模式

行为型剩余的模式

1.中介者模式 package com.jmj.pattern.mediator;public abstract class Mediator {public abstract void constact(String message,Person person); }package com.jmj.pattern.mediator;public class MediatorStructure extends Mediator{private HouseOwner houseOwner;priva…
阅读更多...
Elasticsearch 优化查询中获取字段内容的方式，性能提升5倍！

Elasticsearch 优化查询中获取字段内容的方式，性能提升5倍！

1、背景 集群配置为&#xff1a;8 个 node 节点&#xff0c;16 核 32G&#xff0c;索引 4 分片 1 副本。应用程序的查询逻辑是按经纬度排序后找前 200 条文档。 1、应用对查询要求比较高&#xff0c;search 没有慢查询的状态。 2、集群压测性能不能上去&#xff0c;cpu 使用未打…
阅读更多...
常用PHP数学函数 学习资料

常用PHP数学函数 学习资料

常用PHP数学函数 abs($number): 返回一个数的绝对值。sqrt($number): 返回一个数的平方根。pow($base, $exponent): 返回一个数的指定次幂。exp($number): 返回指数函数的值。log($number, $base): 返回一个数的对数。round($number, $precision): 对一个数进行四舍五入。ceil…
阅读更多...
[Java 基础 - 知识点]

[Java 基础 - 知识点]

数据类型 包装类型缓存池String 概览不可变的好处String, StringBuffer and StringBuilderString.intern()运算 参数传递float 与 double隐式类型转换switch继承 访问权限抽象类与接口super重写与重载Object 通用方法 概览equals()hashCode()toString()clone()关键字 finalstat…
阅读更多...
Pytest 的小例子

Pytest 的小例子

一个简单的例子 下面代码保存到test_pytest.py 一个简单的例子 def inc(x):return x 1def test_answer():assert inc(3) 5def test_ask():assert inc(4) 5 pytest 需要安装一下 pip install pytest (Venv) D:\pythonwork>pip install pytest Collecting pytestDown…
阅读更多...
最新文章

Copyright @ 2022~2023