首页 > 代码库 > C++算法之 求二叉树第k层的节点的个树
C++算法之 求二叉树第k层的节点的个树
思路:
如果树为空或者k< 1,那么节点个数为0;
如果k=1,那么节点个数为1;
如果k>1,那么第k层 总节点的个数等于 左子树k-1层的节点个数+右子树k-1层节点的个数+1
代码如下:
// BTNumOfKLevel.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>using namespace std;class BTree{public: int m_nValue; BTree* m_pLeft; BTree* m_pRight; BTree(int m):m_nValue(m) { m_pLeft = m_pRight = NULL; }};//二叉树的插入实现void Insert(int value, BTree* &root){ if (root == NULL) { root = new BTree(value); } else if(value < root->m_nValue) Insert(value,root->m_pLeft); else if(value > root->m_nValue) Insert(value,root->m_pRight); else ;}int GetNumOfKthLevel(BTree* root, int k){ if(root == NULL || k < 1) return 0; if(k == 1) return 1; int LeftNum = GetNumOfKthLevel(root->m_pLeft,k-1); int RightNum = GetNumOfKthLevel(root->m_pRight,k-1); int ret = LeftNum+RightNum; return ret;}int _tmain(int argc, _TCHAR* argv[]){ BTree* m_pRoot = new BTree(4); Insert(3,m_pRoot); Insert(6,m_pRoot); Insert(1,m_pRoot); Insert(2,m_pRoot); Insert(5,m_pRoot); Insert(8,m_pRoot); Insert(7,m_pRoot); Insert(10,m_pRoot); int number = GetNumOfKthLevel(m_pRoot,4); cout<<"第4层上的节点的个数为:"<<number<<endl; getchar(); return 0;}
C++算法之 求二叉树第k层的节点的个树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。