当前位置：首页 > news >正文

求链式二叉树第K层的结点数

news 来源：原创 2024/5/2 7:07:18

之前我们写过怎么求叶子结点的个数，叶子结点个数就是求它的左子树的叶子结点，加上柚子树的叶子结点，依次递归下去，可能最难得就是跳出递归的条件，由于是求叶子结点，所以当它的左右子树都为空的时候就返回1，如果是空的树就返回零。同样的，我们要找K层的节点数，所以我们每遍历一层就k-1最后当k==1的时候，就到了第K层了，所以这就是我们的终止递归的条件。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode//创建一个链式结构体
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode*BuyNode(BTDataType x)//创建一个新的结点
{
	BTNode*newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* CreatBinaryTree()//手动创建一个链式结构的二叉树，
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node2->right = node7;
	return node1;
}

首先我们手动的构造一个链式二叉树，如上所示。

int BrinaryKLeverSize(BTNode*root,int k)
{
	assert(k >= 1);//防止我们的K小于1
	if (root == NULL)
	{
		return 0;//当为空的时候，就返回零
	}
	if (k == 1)
	{
		return 1;
	}
	return BrinaryKLeverSize(root->left, k - 1) + BrinaryKLeverSize(root->right, k - 1);加上左子树的节点数和右子树的节点数
}
int main()
{
	BTNode*node = CreatBinaryTree();
	int size = BrinaryKLeverSize(node,3);
	printf("%d ", size);

	return 0;
}