2025_2_13 二叉搜索树（一）

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

满二叉树：每一层都达到最大值

完全二叉树：只能右下角空，其他位置满，即最后一排从左到右的中间不能由缺

2.二叉搜索树

1. 左子树中所有结点的 key 值都比根结点的 key 值小，并且左子树也是二叉搜索树。
2. 右子树中所有结点的 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;
}

上述是插入操作的代码，有以下注意点：

• 二叉搜索树的插入一定是插入NULL位置，而不会是节点与节点之间，如果插入到节点之间，会破坏BST的性质，导致树不再有序。
• 要设置当前节点和父节点用于遍历二叉树，因为父节点来做链接操作。
• 可以用差值的形式来判断走哪边。
• 创建新节点一定一定使用calloc来初始化，因为使用malloc极有可能会忘记初始化，导致下次在这个节点之后插入会报错。