The number of nodes and the height of the binary tree

“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

❓ Implements the following interfaces ❔

// Number of nodes in binary tree
int BinaryTreeSize(BTNode* root);
// Number of binary tree leaves
int BinaryTreeLeafSize(BTNode* root);
// Number of nodes at layer K of binary tree
int BinaryTreeLevelKSize(BTNode* root, int k);
// Binary tree depth/height
int BinaryTreeDepth(BTNode* root)
// The binary tree finds the node with the value x
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
Copy the code

❗ Implementation code ❕

❤ BinaryTreeSize ❤

🔑 core idea 1: before using sequence | sequence | in the | | after sequence traversal, global variables

❌ But there is a Bug in the following code: if the previous sequence is repeated twice

➤ The problem is in global variables, where you only need to set 0 in the second run

⚠ as you learn more about this operation in the future, you will actually find thread-safety issues as well

🔑 Core idea 2: functions use return values, and the internal recursion is essentially a back-order recursion

❤ BinaryTreeLeafSize ❤

🔑 Core idea: Left and right are marked. If both are NULL, the sum is added

❤ BinaryTreeLevelKSize ❤

🔑 Core idea: find the k-th layer of the current tree = k-1st layer of the left subtree + k-1st layer of the right subtree (when k = 1, it means that this layer is the target layer)

❤ BinaryTreeDepth ❤

🔑 Core idea: current tree depth = Max (left subtree depth, right subtree depth) + 1

❤ BinaryTreeFind ❤

🔑 Core Idea:

1. Check whether it is the current node and return if it is;

2. Go to the left tree first and return if you find it

The left tree is not found, and then look for the right tree

#include<stdio.h>
#include<stdlib.h>

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
// Number of nodes in binary tree
	//1
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
	if (root == NULL)
		return;
	else
		sz1++;
	BinaryTreeSize1(root->left);
	BinaryTreeSize1(root->right);
}
//2, middle order recursive traversal
int sz2 = 0;
void BinaryTreeSize2(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize2(root->left);
	if(root ! =NULL)
		sz2++;
	BinaryTreeSize2(root->right);
}
//3
int sz3 = 0;
void BinaryTreeSize3(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeSize3(root->left);
	BinaryTreeSize3(root->right);
	if(root ! =NULL)
		sz3++;
}
// Number of nodes in binary tree
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// Number of binary tree leaves
int BinaryTreeLeaSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		returnBinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right); }}// Number of nodes at layer K of binary tree
int BinaryTreeLeveLKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLeveLKSize(root->left, k - 1) + BinaryTreeLeveLKSize(root->right, k - 1);
}
// The depth/height of the binary tree
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// The binary tree finds the node with the value x
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* retleft = BinaryTreeFind(root->left, x);
	if (retleft)
	{
		return retleft;
	}
	BTNode* retright = BinaryTreeFind(root->right, x);
	if (retright)
	{
		return retright;
	}
	return NULL;
}
BTNode* CreatBinaryTree(a)
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;

	return node1;
}

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
int main(a)
{
	BTNode* root = CreatBinaryTree();
	// Print the number of nodes in the binary tree
	BinaryTreeSize1(root);
	BinaryTreeSize2(root);
	BinaryTreeSize3(root);
	printf("BinaryTreeSize:%d\n", sz1);
	printf("BinaryTreeSize:%d\n", sz2);
	printf("BinaryTreeSize:%d\n", sz3);
	printf("-----------------cur-----------------\n");
	// Optimize the number of nodes in the binary tree
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("-----------------cur-----------------\n");
	// Number of binary tree leaves
	printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
	printf("-----------------cur-----------------\n");
	// Number of nodes at layer K of binary tree
	printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
	printf("-----------------cur-----------------\n");
	// The depth/height of the binary tree
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
	printf("-----------------cur-----------------\n");
	// The binary tree finds the node with the value x
	BTNode* ret = BinaryTreeFind(root, 'D');
	if(ret)
	{
		printf("Found \n");
	}
	else
	{
		printf("Not found \n");
	}

	PreOrder(root);
	return 0;
}
Copy the code