二叉树的节点个数以及高度等

发表于

「这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战」

❓ 实现以下接口 ❔

1
2
3
4
5
6
7
8
9
10
c复制代码// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

❗ 实现代码 ❕

  ❤ BinaryTreeSize ❤

    🔑 核心思想1 ：使用前序 || 中序 || 后序遍历，全局变量记录

    ❌ 但是以下代码有 Bug ：如果采用前序重复遍历 2 次

    ✔ 经查，问题出在全局变量上，这里只需要在第 2 次遍历时置 0 即可

    ⚠ 在以后的知识面更大后，其实你会发现这种操作还有线程安全的问题

    🔑 核心思想 2：函数使用带返回值的方式，其内部的递归本质上是一个后序遍厉

  ❤ BinaryTreeLeafSize ❤

    🔑 核心思想 ：以 left 和 right 为标志，如果都为 NULL，则累加

  ❤ BinaryTreeLevelKSize ❤

    🔑 核心思想 ：求当前树的第 k 层 = 左子树的第 k - 1 层 +　右子树的第 k - 1 层 (当 k = 1 时，说明此层就是目标层)

  ❤ BinaryTreeDepth ❤

    🔑 核心思想 ：当前树的深度 = max (左子树的深度，右子树的深度) + 1

  ❤ BinaryTreeFind ❤

    🔑 核心思想 ：

      1、先判断是不是当前节点，是就返回；

      2、先去左树找，找到就返回

      3、左树没找到，再找右树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
c复制代码#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;
}
// 二叉树节点个数
	//1、前序递归遍历
int sz1 = 0;
void BinaryTreeSize1(BTNode* root)
{
	if (root == NULL)
		return;
	else
		sz1++;
	BinaryTreeSize1(root->left);
	BinaryTreeSize1(root->right);
}
//2、中序递归遍历
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++;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子节点个数
int BinaryTreeLeaSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return BinaryTreeLeaSize(root->left) + BinaryTreeLeaSize(root->right);
	}
}
//二叉树第k层节点个数
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);
}
//二叉树的深度/高度 
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;
}
// 二叉树查找值为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()
{
	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()
{
	BTNode* root = CreatBinaryTree();
	//遍厉前中后序输出二叉树节点的个数
	BinaryTreeSize1(root);
	BinaryTreeSize2(root);
	BinaryTreeSize3(root);
	printf("BinaryTreeSize:%d\n", sz1);
	printf("BinaryTreeSize:%d\n", sz2);
	printf("BinaryTreeSize:%d\n", sz3);
	printf("-----------------cur-----------------\n");
	//优化二叉树节点的个数
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("-----------------cur-----------------\n");
	//二叉树叶子节点个数
	printf("BinaryTreeLeaSize:%d\n", BinaryTreeLeaSize(root));
	printf("-----------------cur-----------------\n");
	//二叉树第k层节点个数
	printf("BinaryTreeLeveLKSize:%d\n", BinaryTreeLeveLKSize(root, 3));
	printf("-----------------cur-----------------\n");
	//二叉树的深度/高度 
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
	printf("-----------------cur-----------------\n");
	// 二叉树查找值为x的节点
	BTNode* ret = BinaryTreeFind(root, 'D');
	if(ret)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}

	PreOrder(root);
	return 0;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%