數據結構：在二叉搜索樹中插入元素（Insert in a BST）

目錄

插入的本質是什么？

如何尋找“合法”的位置？—— 模擬查找過程

遞歸插入（Recursive Insert）—— 優雅的實現

代碼逐步完善

總結

上一節我們從第一性原理搞清楚了二叉搜索樹（BST）是什么，以及為什么要有它。現在，我們來解決下一個核心問題：如何向一個已有的 BST 中插入一個新元素？

插入的本質是什么？

我們有一個新數字，比如 10，要把它插入到上次創建的這棵樹里：

數據結構：二叉搜索樹（Binary Search Tree）-CSDN博客

    15/  \8    20/ \
3   12

在動手之前，我們必須牢記 BST 的唯一天條（The Golden Rule）：

對于任何節點，其左子樹的所有值都比它小，右子樹的所有值都比它大。

所以，插入一個新節點，本質上就兩個步驟：

  1. 找到一個“合法”的位置：這個位置必須能容納新節點，并且新節點放進去之后，整棵樹依然要滿足 BST 的“天條”。

  2. 執行插入動作：把新節點安家落戶在這個位置上。

如何尋找“合法”的位置？—— 模擬查找過程

這個尋找位置的過程，其實和我們查找一個數的過程一模一樣。我們就像這個新來的數字 10，要在這棵樹里找個家。

    15/  \8    20/ \
3   12

從根節點 15 開始問路：

  • 10 小于 15 (10 < 15)。

  • 根據天條，10 的家一定在 15 的左子樹里。我們往左走。

來到節點 8：

  • 10 大于 8 (10 > 8)。

  • 根據天條，10 的家一定在 8 的右子樹里。我們往右走。

來到節點 12：

  • 10 小于 12 (10 < 12)。

  • 根據天條，10 的家一定在 12 的左子樹里。我們往左走。

12 的左邊是什么？

  • 是 NULL！一個空位！

  • 這是一個“死胡同”，我們沒法再往下走了。

這個“死胡同”（NULL 指針）就是我們夢寐以求的“合法”位置。為什么？

  • 把它放在這里，它會成為 12 的左孩子。因為 10 < 12，這滿足了對于節點 12 的天條。

  • 同時，10 > 8，10 < 15，它也滿足了對于它所有祖先節點的天條。

  • 最重要的是，把它放在一個 NULL 的位置，作為一個新的葉子節點，我們不需要改動樹中任何其他節點的現有連接關系，這是成本最低的操作！

?新節點插入的位置，必然是樹中某個節點的 NULL 的 left 或 right 指針所在的位置。尋找這個位置的過程，就是一個模擬查找的過程。

遞歸插入（Recursive Insert）—— 優雅的實現

現在我們用代碼來實現這個邏輯。遞歸是處理樹結構最自然、最優雅的方式。

遞歸的思想： 我們把一個大問題，分解成一個性質相同、但規模更小的子問題。 對于插入操作：

  • 大問題：在以 root 為根的整棵樹中插入 value。

  • 子問題：

    • 如果 value < root->data，問題就縮小為：在以 root->left 為根的左子樹中插入 value。

    • 如果 value > root->data，問題就縮小為：在以 root->right 為根的右子樹中插入 value。

這個分解過程什么時候結束呢？—— 當我們遇到一個 NULL 的節點時，也就是找到了那個“死胡同”，這就是遞歸的基本情況（Base Case）。

代碼逐步完善

函數簽名和基本情況 (Base Case)

首先，我們需要一個函數。它應該做什么？

  • 它需要知道從哪個節點開始（Node* root）。

  • 它需要知道要插入的值是多少（int value）。

  • 當插入完成后，樹的結構可能發生變化（比如，從一棵空樹變成有一個節點的樹），所以這個函數必須返回新樹的根節點指針。

#include <cstddef> // 為了 NULLstruct Node {int data;Node* left;Node* right;Node(int value) {data = value;left = right = NULL;}
};/** 函數功能：向以 root 為根的樹中插入 value* 返回值：  返回插入新節點后，樹（或子樹）的根節點*/
Node* insert(Node* root, int value) {// 基本情況 (Base Case):// 如果當前的 root 是 NULL (無論是整棵樹為空，還是我們已經走到了一個“死胡同”)// 這就是我們要插入新節點的地方。if (root == NULL) {// 創建一個新節點，它自己就是一棵子樹return new Node(value);}// ... 遞歸的步驟還沒寫 ...
}

思考一下 return new Node(value); 這一行。

它返回一個指向新創建節點（值為value）的指針。誰會接收這個指針呢？是上一層的函數調用。我們馬上就能看到。

加入遞歸步驟

現在，如果 root 不是 NULL，我們就需要決定是往左還是往右。

Node* insert(Node* root, int value) {if (root == NULL) {return new Node(value);}// 遞歸步驟 (Recursive Step):if (value < root->data) {// 新值應該插入到左子樹中// 我們遞歸調用 insert，讓它去處理左子樹的問題// **關鍵一步**: 遞歸調用返回的結果(可能是新的左子樹的根)//            必須被連接到當前節點的左指針上！root->left = insert(root->left, value);} else if (value > root->data) {// 新值應該插入到右子樹中// 同理，連接到當前節點的右指針上root->right = insert(root->right, value);}// ... 還有一種情況：value == root->data ...// ... 以及，這個函數在遞歸調用后應該返回什么？...
}

我們來剖析 root->left = insert(root->left, value); 這句代碼，它是遞歸插入的精髓。

假設我們要在節點 12 的左邊插入 10。

    15/  \8    20/ \
3   12

  • 當前 root 是 12。value 是 10。

  • 10 < 12，所以執行 root->left = insert(root->left, value);

  • 此時 root->left 是 NULL。所以 insert(NULL, 10) 被調用。

  • 根據我們的基本情況，insert(NULL, 10) 會 new Node(10) 并返回指向這個新節點的指針。

  • 這個返回的指針，被賦值給了 root->left (也就是 12 的 left 指針)。

  • 效果達成：新節點 10 被成功地連接為了 12 的左孩子。

處理重復值并完成函數

標準的 BST 通常不允許重復值。如果待插入的值和當前節點的值相等，我們什么都不做，直接返回。

最后，如果當前節點不是 NULL，并且完成了對子樹的插入操作后，當前節點本身（root）的地址沒有變，所以我們要把它返回給它的上層調用，以保持樹的連接。

/** 函數功能：向以 root 為根的樹中插入 value* 返回值：  返回插入新節點后，樹（或子樹）的根節點*/
Node* insert(Node* root, int value) {// 基本情況：如果當前節點是 NULL，說明找到了插入位置。if (root == NULL) {// 創建新節點并返回，上一層的調用會把它連接到樹中。return new Node(value);}// 遞歸步驟：if (value < root->data) {// 向左子樹遞歸插入root->left = insert(root->left, value);} else if (value > root->data) {// 向右子樹遞歸插入root->right = insert(root->right, value);}// else (value == root->data) 的情況:// 我們選擇什么都不做，因為不允許重復值。// 將當前的（可能未改變的）根節點指針返回給上一層。// 這一步確保了樹中未受影響部分的連接保持不變。return root;
}

如何使用這個函數？

主調函數需要一個 Node* 變量來保存整棵樹的根。每次插入，都需要用這個變量來接收 insert 函數的返回值，以防根節點發生改變（比如第一次插入時）。

#include <iostream>// (這里是 Node 結構體和 insert 函數的定義)// 為了方便觀察，我們寫一個中序遍歷函數來打印樹
void inorderTraversal(Node* root) {if (root == NULL) {return;}inorderTraversal(root->left);std::cout << root->data << " ";inorderTraversal(root->right);
}int main() {Node* root = NULL; // 一開始，樹是空的// 第一次插入，root 會從 NULL 變成新節點的地址root = insert(root, 15);root = insert(root, 8);root = insert(root, 20);root = insert(root, 3);root = insert(root, 12);// 現在我們插入新值 10std::cout << "插入 10 之前的中序遍歷: ";inorderTraversal(root); // 輸出: 3 8 12 15 20 std::cout << std::endl;root = insert(root, 10);std::cout << "插入 10 之后的中序遍歷: ";inorderTraversal(root); // 輸出: 3 8 10 12 15 20 std::cout << std::endl;// 嘗試插入一個重復的值 12root = insert(root, 12);std::cout << "插入重復值 12 之后的中序遍歷: ";inorderTraversal(root); // 輸出: 3 8 10 12 15 20 (沒有變化)std::cout << std::endl;return 0;
}

注意：inorderTraversal 只是為了驗證我們插入的正確性，它本身也是遞歸的一個經典應用。

總結

  • 第一性原理：插入操作必須維護 BST 的“左小右大”核心性質。

  • 推導：最簡單、成本最低的插入位置是某個葉子節點的 NULL 孩子位置。這個位置可以通過模擬“查找”過程來找到。

  • 遞歸實現：

    • Base Case (基本情況)：當前節點為 NULL。這是遞歸的終點，也是新節點被創建和“返回”的地方。

    • Recursive Step (遞歸步驟)：比較新值和當前節點的值，決定向左還是向右“委托”任務（遞歸調用）。

    • 關鍵連接：root->left = insert(root->left, ...) 是實現連接的核心。它用遞歸調用的返回值（可能是新節點，也可能是原來的子樹根）來更新自己的孩子指針。

    • 返回值：函數必須返回根節點指針，以確保調用者能正確地更新樹的結構。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/93508.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/93508.shtml
英文地址，請注明出處：http://en.pswp.cn/web/93508.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【論文閱讀】美 MBSE 方法發展分析及啟示(2024)

【論文閱讀】美 MBSE 方法發展分析及啟示(2024)

文章目錄 論文摘要 論文框架 1. MBSE 方法概述 2. 美國防部的 MBSE 方法政策要求 在這里插入圖片描述 3. 美軍兵種的 MBSE 方法政策要求 4. 啟示 5.總結 參考文獻 論文摘要 本文梳理了美國防部基于模型的系統工程（MBSE）方法的發展歷程，并剖析 其技術原理；跟蹤《數字工程戰略…
閱讀更多...
人工智能訓練師復習題目實操題1.1.1 - 1.1.5

人工智能訓練師復習題目實操題1.1.1 - 1.1.5

列出所有的python 庫和 apiimport pandas as pd import numpy as np就這兩個庫pandas 庫 - apinumpy 庫 - apimatplotlib.pyplot - apipd.read_csv()np.where(condition,x,y)fillna(methodffill,inplaceTrue)methodbfill,pd.read_excel()np返回結果 series 對象 data[A列].valu…
閱讀更多...
旅游管理實訓室：旅游教育實踐育人的關鍵支撐

旅游管理實訓室：旅游教育實踐育人的關鍵支撐

在中等職業教育旅游服務與管理專業教學中&#xff0c;旅游管理實訓室并非簡單的教學場所&#xff0c;而是落實專業教學標準、實現 “理實一體化” 育人的核心陣地。它通過模擬真實職業場景、配置專業實訓設備、設計實踐教學活動&#xff0c;將抽象的專業知識轉化為具體的操作技…
閱讀更多...
http工作流程

http工作流程

HTTP&#xff08;Hypertext Transfer Protocol&#xff0c;超文本傳輸協議&#xff09;是互聯網中客戶端與服務器之間傳輸超文本&#xff08;如HTML、圖片、JSON等&#xff09;的核心協議&#xff0c;基于請求-響應模型和TCP/IP協議族工作。其完整工作流程可拆解為以下9個核心步…
閱讀更多...
正則表達式實用面試題與代碼解析專欄

正則表達式實用面試題與代碼解析專欄

正則表達式是前端表單驗證、字符串匹配的核心工具，簡潔高效的正則能大幅提升代碼性能。本專欄整理了7道高頻面試題，包含核心正則表達式、代碼實現及關鍵知識點解析，幫你快速掌握正則實用技巧。 一、正則基礎：核心概念與語法 在學習面試題前，先明確幾個高頻基礎語法，這是…
閱讀更多...
【數據可視化-89】基孔肯雅熱病例數據分析與可視化：Python + pyecharts洞察疫情動態

【數據可視化-89】基孔肯雅熱病例數據分析與可視化：Python + pyecharts洞察疫情動態

&#x1f9d1; 博主簡介&#xff1a;曾任某智慧城市類企業算法總監&#xff0c;目前在美國市場的物流公司從事高級算法工程師一職&#xff0c;深耕人工智能領域&#xff0c;精通python數據挖掘、可視化、機器學習等&#xff0c;發表過AI相關的專利并多次在AI類比賽中獲獎。CSDN…
閱讀更多...
云智智慧停充一體云-allnew全新體驗-路內停車源碼+路外停車源碼+充電樁源碼解決方案

云智智慧停充一體云-allnew全新體驗-路內停車源碼+路外停車源碼+充電樁源碼解決方案

采用Java主流的微服務技術棧&#xff0c;基于 Spring Cloud Alibaba 的微服務解決方案進行封裝的快速開發平臺&#xff0c;包含多種常用開箱即用功能的模塊&#xff0c;通用技術組件與服務、微服務治理&#xff0c;具備RBAC功能、網關統一鑒權、Xss防跨站攻擊、自動生成前后端代…
閱讀更多...
利用pypy加速pyxlsbwriter生成xlsb文件

利用pypy加速pyxlsbwriter生成xlsb文件

上文介紹了python通過DuckDB和pyxlsbwriter模塊生成xlsb文件&#xff0c;因為python是解釋執行&#xff0c;它的速度有點慢&#xff0c;pypy是另一種python解釋器&#xff0c;它使用即時編譯&#xff08;JIT&#xff09;技術來提高執行速度。 因為DuckDB與pypy不兼容&#xff0…
閱讀更多...
【Java后端】Spring Boot 集成 MyBatis-Plus 全攻略

【Java后端】Spring Boot 集成 MyBatis-Plus 全攻略

Spring Boot 集成 MyBatis-Plus 全攻略 1. 為什么選擇 MyBatis-Plus 零侵入&#xff1a;在 MyBatis 基礎上增強&#xff0c;不影響現有功能。內置 CRUD&#xff1a;無需寫 XML/SQL&#xff0c;直接調用 BaseMapper 方法。強大插件&#xff1a;分頁插件、性能分析、樂觀鎖、多租…
閱讀更多...
LangChain 多任務應用開發

LangChain 多任務應用開發

Q: LangChain dify coze是競品關系 都是AI Agent搭建平臺&#xff0c;dify和coze 屬于低代碼&#xff0c;langChain屬于高代碼&#xff0c;coze優于dify Q&#xff1a;向量數據庫是存儲向量&#xff0c;做相似度檢索的&#xff0c;可以用faiss milvus chromdb Q&#xff1a;使用…
閱讀更多...
實用技巧：Oracle中精準查看表占用空間大小

實用技巧：Oracle中精準查看表占用空間大小

目錄實用技巧&#xff1a;Oracle中精準查看表占用空間大小一、為什么需要精準統計表空間占用&#xff1f;二、完整查詢SQL&#xff1a;覆蓋表、LOB、索引三、SQL語句關鍵邏輯解析1. 基礎表&#xff1a;dba_tables 與 dba_tablespaces2. 子查詢1&#xff1a;統計表段空間&#x…
閱讀更多...
openEuler等Linux系統中如何復制移動硬盤的數據

openEuler等Linux系統中如何復制移動硬盤的數據

在 openEuler 系統中，提示 “You should mount volume first” ，意思是需要先掛載移動硬盤的分區才能訪問： 安裝必要軟件（針對特殊文件系統） 如果移動硬盤是 NTFS 等非 Linux 原生支持的文件系統格式，需要安裝對應的支持軟件，以掛載 NTFS 格式移動硬盤為例，需要安裝 …
閱讀更多...
java如何把字符串數字轉換成數字類型

java如何把字符串數字轉換成數字類型

在Java中將字符串數字轉換為數字類型有多種方法&#xff0c;以下是詳細說明和示例代碼&#xff1a; 一、基礎轉換方法 Integer.parseInt() String str "123"; int num Integer.parseInt(str); // 轉換為intDouble.parseDouble() String str "3.14"; dou…
閱讀更多...
WPFC#超市管理系統（6）訂單詳情、顧客注冊、商品銷售排行查詢和庫存提示、LiveChat報表

WPFC#超市管理系統（6）訂單詳情、顧客注冊、商品銷售排行查詢和庫存提示、LiveChat報表

WPF&C#超市管理系統10. 訂單詳情10.1 頁面布局10.2 功能實現11. 顧客注冊12. 商品銷售排行查詢與庫存提示14. LiveChart報表總結10. 訂單詳情 10.1 頁面布局 頁面分三行布置&#xff0c;第一行復用OutstorageView界面的第一行&#xff0c;將屬性和命令修改為顧客相關第二…
閱讀更多...
【Linux】文件基礎IO

【Linux】文件基礎IO

1.關于文件的共識原理 1.文件內容屬性 2.文件分為打開的文件和沒打開的文件 3.打開的文件&#xff1a; 文件被打開必須先被加載到內存&#xff0c;所以本質是研究進程和文件的關系&#xff0c;一個進程可以打開多個文件。操作系統內部一定存在大量被打開的文件&#xff0c;要進…
閱讀更多...
基于微信小程序的生態農產銷售管理的設計與實現/基于C#的生態農產銷售系統的設計與實現、基于asp.net的農產銷售系統的設計與實現

基于微信小程序的生態農產銷售管理的設計與實現/基于C#的生態農產銷售系統的設計與實現、基于asp.net的農產銷售系統的設計與實現

基于微信小程序的生態農產銷售管理的設計與實現/基于C#的生態農產銷售系統的設計與實現、基于asp.net的農產銷售系統的設計與實現
閱讀更多...
Java研學-SpringCloud(五)

Java研學-SpringCloud(五)

一 Nacos 配置中心 1 引入依賴 – services.pom每個微服務都需要<!--配置中心--><dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-nacos-config</artifactId></dependency>2 配置文件 –…
閱讀更多...
.NET 中的延遲初始化：Lazy＜T＞ 與LazyInitializer

.NET 中的延遲初始化：Lazy＜T＞ 與LazyInitializer

標簽&#xff1a;線程安全、延遲初始化、按需初始化、提升啟動性能 項目地址&#xff1a;NitasDemo/12Lazy/LazyDemo at main Nita121388/NitasDemo 目錄Lazy<T>1. 概念2. 基本用法 3. 異常處理 4. 線程安全模式 5. 示例1. 線程安全模式 (ExecutionAndPublication)2. 發…
閱讀更多...
【LLIE專題】LLIE低照度圖像結構先驗提取方法

【LLIE專題】LLIE低照度圖像結構先驗提取方法

Zero-Shot Day-Night Domain Adaptation with a Physics Prior&#xff08;ICCV,2021&#xff09;專題介紹一、研究背景二、方法1. 物理反射模型與顏色不變特征的推導&#xff08;原理推導、物理依據&#xff09;2. 顏色不變特征的計算&#xff08;特征計算公式整個過程&#x…
閱讀更多...
Font Awesome Kit 使用詳解

Font Awesome Kit 使用詳解

在現代網頁設計中&#xff0c;圖標是提升用戶體驗的關鍵元素。而 Font Awesome 作為最受歡迎的圖標庫&#xff0c;其最新版本 Font Awesome 7 通過 Kit 功能提供了更便捷高效的集成方式。本文將帶你全面了解如何使用 Font Awesome Kit&#xff0c;讓你的網站圖標管理變得輕松高…
閱讀更多...
最新文章

Copyright @ 2022~2023