2025_2_13 二叉搜索树（一）

1.完全二叉树和满二叉树的概念

满二叉树：每一层都达到最大值
在这里插入图片描述
完全二叉树：只能右下角空，其他位置满，即最后一排从左到右的中间不能由缺

2.二叉搜索树

左子树中所有结点的 key 值都比根结点的 key 值小，并且左子树也是二叉搜索树。
右子树中所有结点的 key 值都比根结点的 key 值大，并且右子树也是二叉搜索树。

它是一种天然的递归结构

2.1 结构体创建的注意点

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>typedef int K;typedef struct node {K key;	// 结点的唯一性标识,key是不重复的struct node* left;  // 左子树struct node* right; // 右子树
} TreeNode;// 推荐定义一个二叉搜索树的结构体,这样更便于扩展
typedef struct {TreeNode* root; // 根结点
}BST;// 基础操作
BST* bst_create();
void bst_destroy(BST* tree);bool bst_insert(BST* tree, K key);
TreeNode* bst_search(BST* tree, K key);
bool bst_delete(BST* tree, K key);void bst_preorder(BST* tree); // 先序遍历
void bst_inorder(BST* tree);  // 中序遍历
void bst_postorder(BST* tree);  // 后序遍历
void bst_levelorder(BST* tree); // 层次遍历

上述是创建结构体操作的代码，有以下注意点：

使用K作为int的宏定义，提高代码的可修改性
使用BST结构体创建根节点指针，避免传入二级指针，而且这样可读性高

2.2 插入操作的注意点

bool bst_insert(BST* tree, K key) {TreeNode* curr = tree->root;TreeNode* parent = NULL;int diff;while (curr != NULL) {diff = curr->key - key;if (diff > 0) {//往左走parent = curr;curr = curr->left;}else if (diff < 0) {//往右走parent = curr;curr = curr->right;}else {printf("error:key is overlap\n");return false;}}//现在curr指向待插入的位置，为NULL，parent指向其父节点//使用calloc创建新节点，可以避免忘记初始化TreeNode* new_node = calloc(1, sizeof(TreeNode));if (new_node == NULL) {printf("calloc failed in bst_insert\n");return false;}new_node->key = key;//如果插入的是第一个节点if (parent == NULL) {tree->root = new_node;return true;}//左边插入if (diff > 0) {parent->left = new_node;}//右边插入if (diff < 0) {parent->right = new_node;}return true;
}