首页 > 代码库 > 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层的节点的个树