如何在搜索引擎做网站,舟山做网站公司,wordpress禁用古登堡,河北建设工程信息网一体化平台文章目录 1 题目2 思路2.1 思路12.2 思路2 3 代码实现3.1 思路13.2 思路23.3 完整的代码案例 1 题目
假设二叉树采用二叉链表存储结构#xff0c;设计一个算法求其指定的第k层#xff08;k1#xff0c;跟是第1层#xff09;的叶子结点个数。
2 思路
2.1 思路1
设置… 文章目录 1 题目2 思路2.1 思路12.2 思路2 3 代码实现3.1 思路13.2 思路23.3 完整的代码案例 1 题目
假设二叉树采用二叉链表存储结构设计一个算法求其指定的第k层k1跟是第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 BiTNodeint {
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 BiTNodechar {
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(BiTNodeT* root, int level, int k){if(level k){if(root-left ! nullptr) calLevelLeaf(root-left, level1, k);if(root-right ! nullptr) calLevelLeaf(root-right, level1, k);}else if(level k root-left nullptr root-right nullptr){leafNum;}
} template typename T
int getLevelLeaf(BiTNodeT* root, int k){calLevelLeaf(root, 1, k);return leafNum;
}3.2 思路2
template typename T
int getLevelLeaf2(BiTNodeT* root, int k){dequeBiTNodeT* q;//双端队列BiTNodeT *newNode nullptr, *lastNode root; int level 1;//层数int leafNum 0;//该层的叶子结点个数q.push_back(root);while(!q.empty()){BiTNodeT* 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 BiTNodeint {
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 BiTNodechar {
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(BiTNodeT** treeNode, dequeTdataDeq) {//层序遍历建立二叉树//特殊处理根结点T data;data dataDeq.front();dataDeq.pop_front();BiTNodeT * node new BiTNodeT();*treeNode node;(*treeNode)-data data;dequeBiTNodeT** nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index 2;//用于判定左右孩子左偶右奇while (!dataDeq.empty()){//当数据节点非空时进行建树BiTNodeT** 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{BiTNodeT * node new BiTNodeT();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 createBiTNodechar(BiTNodechar** treeNode, dequechardataDeq) {//层序遍历建立二叉树//特殊处理根结点char data;data dataDeq.front();dataDeq.pop_front();BiTNodechar * node new BiTNodechar();*treeNode node;(*treeNode)-data data;dequeBiTNodechar** nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index 2;//用于判定左右孩子左偶右奇while (!dataDeq.empty()){//当数据节点非空时进行建树BiTNodechar** 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{BiTNodechar * node new BiTNodechar();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 createBiTNodeint(BiTNodeint** treeNode, dequeintdataDeq) {//层序遍历建立二叉树//特殊处理根结点char data;data dataDeq.front();dataDeq.pop_front();BiTNodeint * node new BiTNodeint();*treeNode node;(*treeNode)-data data;dequeBiTNodeint** nodeDeq;//用于层序建立树时访问双亲节点nodeDeq.push_back(treeNode);int index 2;//用于判定左右孩子左偶右奇while (!dataDeq.empty()){//当数据节点非空时进行建树BiTNodeint** 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{BiTNodeint * node new BiTNodeint();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(BiTNodeT* treeNode){if(treeNode){inOrder(treeNode-left);couttreeNode-data ;inOrder(treeNode-right);}
}template typename T
void preOrder(BiTNodeT* treeNode){if(treeNode){couttreeNode-data ;preOrder(treeNode-left);preOrder(treeNode-right);}
}template typename T
void postOrder(BiTNodeT* treeNode){if(treeNode){postOrder(treeNode-left);postOrder(treeNode-right);couttreeNode-data ;}
}template typename T
void preOrder2(BiTNodeT* treeNode){stackBiTNodeT* s;BiTNodeT* p treeNode;while(p || !s.empty()){if(p){coutp-data ;s.push(p);p p-left;}else{p s.top();s.pop();p p-right;}}
}template typename T
void inOrder2(BiTNodeT* treeNode){stackBiTNodeT* s;BiTNodeT* p treeNode;while(p || !s.empty()){if(p){s.push(p);p p-left;}else{p s.top();coutp-data ;s.pop();p p-right;}}
}template typename T
void postOrder2(BiTNodeT* treeNode){stackBiTNodeT* s;BiTNodeT *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{coutp-data ;s.pop();r p;p nullptr;}}}
}template typename T
void levelOrder(BiTNodeT* treeNode) {queueBiTNodeT* nodeQue;BiTNodeT* p treeNode;nodeQue.push(p);while(!nodeQue.empty()){p nodeQue.front();nodeQue.pop();coutp-data ;if(p-left) nodeQue.push(p-left);if(p-right) nodeQue.push(p-right);}
}int leafNum 0;template typename T
void calLevelLeaf(BiTNodeT* root, int level, int k){if(level k){if(root-left ! nullptr) calLevelLeaf(root-left, level1, k);if(root-right ! nullptr) calLevelLeaf(root-right, level1, k);}else if(level k root-left nullptr root-right nullptr){leafNum;}
} template typename T
int getLevelLeaf(BiTNodeT* root, int k){calLevelLeaf(root, 1, k);return leafNum;
}template typename T
int getLevelLeaf2(BiTNodeT* root, int k){dequeBiTNodeT* q;//双端队列BiTNodeT *newNode nullptr, *lastNode root; int level 1;//层数int leafNum 0;//该层的叶子结点个数q.push_back(root);while(!q.empty()){BiTNodeT* 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() {//使用字符串//dequechar treeVec{a, b, c, d, e, #, #};//dequechar treeVec{a, b, c, d, e, f, g, h, #, #,i,#,#,k,l};dequechar treeVec{a, b, c, d, e, f, g, h, #, i, j,#,#,k,l,m,n,#,#,o,#,#,p,#,#};BiTNodechar* tree new BiTNodechar();createBiTNode(tree, treeVec);//使用数值
// dequeint treeVec{1, 2, 3, 4, 5, -1, -1};
// BiTNodeint* tree new BiTNodeint();
// createBiTNode(tree, treeVec);//遍历树//inOrder(tree);//coutendl;printf(%d, getLevelLeaf2(tree, 5));//tree,4return 0;
}
