BST（二叉搜索树）的笔试大题（C语言）

前言

二叉搜索树在笔试的题目里大多数是客观题，但是也有概率出现在主观题中，所以我们也要学会基本的实现，插入节点，前中后序遍历节点，还有节点个数，叶子节点个数，二叉树深度，这些算法基本都是用到递归的思想，所以我们要掌握。你如果对二叉搜索树不是很了解可以看这个这两期博文概念和算法题。

一、代码实现二叉搜索树

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

typedef int DataType_t;

typedef struct BSTNode_t {
	DataType_t data;
	struct BSTNode_t* lchild;
	struct BSTNode_t* rchild;
}BSTNode_t;

BSTNode_t* CreateTreeNode(DataType_t val) {
	BSTNode_t* root = (BSTNode_t*)calloc(1, sizeof(BSTNode_t));
	root->data = val;
	root->lchild = NULL;
	root->rchild = NULL;
	return root;
}

//循环实现插入
bool InsertNode(BSTNode_t* root, DataType_t val) {
	BSTNode_t* NewNode = CreateTreeNode(val);
	if (!root) {
		root = NewNode;
		return true;
	}
	BSTNode_t* curr = root;
	while (curr) {
		if (curr->data == val) {
			printf("Insert failed!\n");
			return false;
		}
		else {
			if (val < curr->data) {
				if (!curr->lchild) {
					curr->lchild = NewNode;
					break;
				}
				curr = curr->lchild;
			}
			else {
				if (!curr->rchild) {
					curr->rchild = NewNode;
					break;
				}
				curr = curr->rchild;
			}
		}
	}
	return true;
}

//递归实现插入
BSTNode_t* Insert(BSTNode_t* root, DataType_t val) {
	if (!root) {
		return CreateTreeNode(val);
	}
	if (val < root->data) {
		root->lchild = Insert(root->lchild, val);
	}
	else if (val > root->data) {
		root->rchild = Insert(root->rchild, val);
	}
	return root;
}

void PreOrder(BSTNode_t* root) {
	if (!root) {
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->lchild);
	PreOrder(root->rchild);
}

void InOrder(BSTNode_t* root) {
	if (!root) return;
	InOrder(root->lchild);
	printf("%d ", root->data);
	InOrder(root->rchild);
}

void PostOrder(BSTNode_t* root) {
	if (!root) return;
	PostOrder(root->lchild);
	PostOrder(root->rchild);
	printf("%d ", root->data);
}

//节点个数
int TreeCount(BSTNode_t* root) {
	if (!root)return 0;
	return TreeCount(root->lchild) + TreeCount(root->rchild) + 1;
}

//叶子节点个数
int LeafCount(BSTNode_t* root) {
	if (!root)return 0;
	if (!root->lchild && !root->rchild) return 1;
	return LeafCount(root->lchild) + LeafCount(root->rchild);
}

int MaxDepth(BSTNode_t* root) {
	if (!root)return 0;
	int n1 = MaxDepth(root->lchild);
	int n2 = MaxDepth(root->rchild);
	return ((n1 > n2) ? n1 : n2) + 1;
}

void Destroyed(BSTNode_t* root) {
	if (!root) {
		return;
	}

	Destroyed(root->lchild);
	Destroyed(root->rchild);
	free(root);

	return;
}

int main() {
	BSTNode_t* root = CreateTreeNode(10);

	InsertNode(root, 13);
	InsertNode(root, 9);
	InsertNode(root, 25);
	InsertNode(root, 7);
	InsertNode(root, 2);
	InsertNode(root, 17);
	InsertNode(root, 54);

	PreOrder(root);
	printf("\n节点个数:\n");
	printf("%d\n", TreeCount(root));

	printf("\n叶子节点个数:\n");
	printf("%d\n", LeafCount(root));

	printf("\n二叉树深度:\n");
	printf("%d\n", MaxDepth(root));

	Destroyed(root);
	return 0;
}

二、求节点个数

代码实现

int TreeCount(BSTNode_t* root) {
	if (!root)return 0;
	return TreeCount(root->lchild) + TreeCount(root->rchild) + 1;
}

三、求叶子节点个数

代码实现

int LeafCount(BSTNode_t* root) {
	if (!root)return 0;
	if (!root->lchild && !root->rchild) return 1;
	return LeafCount(root->lchild) + LeafCount(root->rchild);
}

四、求深度

代码实现

int MaxDepth(BSTNode_t* root) {
	if (!root)return 0;
	int n1 = MaxDepth(root->lchild);
	int n2 = MaxDepth(root->rchild);
	return ((n1 > n2) ? n1 : n2) + 1;
}

结语

大家千万不要自以为是，不要小瞧了这些题目，你不要以为自己都懂了，你能手搓出来那才是真的懂，在笔试的题目里绝大多数都是基础题，都是你如果连基础都不掌握你说你能做出很庞大的项目，那绝对是扯淡，所以一定要自己动手多写。同时大家也不要妄自菲薄，你们要相信这些东西别人能做出来你也能，别人能解决的问题，你也能解决，只是时间问题

希望各位靓仔靓女点赞，收藏，关注多多支持，我们共同进步，后续我会更新更多的面试真题，你们的支持将是我前进最大的动力。