用golang實現二叉搜索樹(BST)

目錄

  • 一、概念、性質
  • 二、二叉搜索樹的實現
    • 1. 結構
    • 2. 查找
    • 3. 插入
    • 4. 刪除
    • 5. 中序遍歷
  • 中序前驅/后繼結點

一、概念、性質

二叉搜索樹(Binary Search Tree),簡寫BST,又稱為二叉查找樹

它滿足:

  • 空樹是一顆二叉搜索樹
  • 對于任意結點 node ,它的左右孩子如果不為空 ,滿足:
    • 左子樹上所有結點的值都小于node的值
    • 右子樹上所有結點的值都大于node的值
  • 不存在數值重復的結點

如下圖,圖(1)是二叉搜索樹,圖(2)、圖(3)不是二叉搜索樹
圖(2)中不滿足 70 < 50
圖(3)中不滿足 30 < 10

在這里插入圖片描述


之所以叫做二叉搜索樹,是因為在BST中搜索一個值是很簡單的

例如圖(1)中要查找40
從根結點出發,40比50小,來到根結點的左孩子30,40比30大,來到30的右孩子40,40等于40,這樣就找到了

例如圖(1)中要查找10
從根結點出發,10比50小,來到根節點的左孩子30,10比30小,來到30的左孩子20,10比20小,來到20的左孩子null,所以沒有10這個結點


在這里插入圖片描述

對圖(1)進行中序遍歷,得到 20 30 40 50 60
發現是一個有序的序列

所以對二叉搜索樹進行中序遍歷,會得到一個有序的序列

二、二叉搜索樹的實現

1. 結構

定義一個二叉搜索樹很簡單,就和定義一個二叉樹的結構一樣,需要包含 數據、左右孩子指針

// 定義結點結構
type TSNode struct {data  intleft  *TSNoderight *TSNode
}

2. 查找

查找一個值target,從根結點開始,遞歸進行比較。

如果等于根結點,找到返回
如果小于根結點則走到左子樹,在左子樹中找
如果大于根結點則走到右子樹,在右子樹中找

// 判斷結點是否存在
func (t *TSNode) Search(data int) *TSNode {if t == nil {return nil}if t.data == data { //找到了 返回結點return t}if data < t.data { //要找的數據小于根結點 向左找return t.left.Search(data)} else { //要找的數據大于根結點  向右找return t.right.Search(data)}
}

3. 插入

向二叉搜索樹插入數據data ,分為兩種情況

  • 樹為空,定義一個新結點儲存data,直接 根結點 = 新結點
  • 樹不為空,和結點進行比較(和查找數據步驟一樣),直到結點為空,將新結點插入

如向圖(1)中插入數據35
在這里插入圖片描述

  1. 首先和根結點50進行比較,小于50,走到左孩子30
  2. 和30進行比較,大于30,走到30的右孩子40
  3. 和40進行比較,小于40,走到40的左孩子 null,將35 插入40 左孩子

最終得到
在這里插入圖片描述

// 插入數據
func (t *TSNode) Insert(data int) {newNode := &TSNode{data,nil,nil,}//如果根結點為空 直接插入if t == nil {t = newNodereturn}//根結點不為空 判斷if data < t.data { //小于根結點數據 向左找if t.left == nil { //左孩子為空 直接賦值t.left = newNode} else {t.left.Insert(data) //左孩子不為空 遍歷左孩子 找}} else {if t.right == nil {t.right = newNode} else {t.right.Insert(data)}}
}

4. 刪除

刪除二叉搜索樹的數據分為三種情況

  • 要刪除的結點沒有左右孩子
  • 要刪除的結點沒有左孩子或右孩子
  • 要刪除的結點既有左孩子也有右孩子

有這樣一顆二叉搜索樹,下面第一二種拿這個舉例子

在這里插入圖片描述

  1. 刪除的結點沒有左右孩子

直接刪除結點就可以
例如刪除上圖中的25,直接刪除25得到
在這里插入圖片描述

  1. 要刪除的結點只有左孩子或只有右孩子

如果只有右孩子,比如刪除圖中的60
直接讓60父結點與60的右孩子連接,將60刪除就可以
得到:
在這里插入圖片描述
3. 要刪除的結點既有左孩子也有右孩子

這里要引入中序后繼中序前驅的概念,我把這兩個概念放在最后了

blog.csdnimg.cn/direct/e37cc3938fe3426b925afd7c3c2237fd.png)

比如要刪除30,找到30的中序后繼結點或者中序前驅結點,哪個都可以,就拿中序后繼結點舉例子

30的中序后繼結點是35,將35的值賦給30這個節點,再對30的右子樹進行刪除中序后繼結點的操作就可以了

在這里插入圖片描述

使用中序前驅結點一樣,將中序前驅節點的值賦給要刪除的節點的值,再對要刪除的節點的左子樹進行刪除中序前驅節點的操作


實現刪除操作的代碼:

首先要找到要刪除的結點, if、else if、else 就是在找要刪除的結點

// 刪除結點
func (t *TSNode) Delete(data int) *TSNode {//查找結點 -- 查找到要找的結點,分情況對結點進行刪除操作if t == nil {return nil}if data < t.data { //要刪除的數據小于根結點//遞歸查找左子樹t.left = t.left.Delete(data)} else if data > t.data {//遞歸查找右子樹t.right = t.right.Delete(data)} else { //查找到了要刪除的數據//此時t是要刪除的結點 分情況if t.left == nil && t.right == nil { //如果左右孩子都是空 直接刪除 返回空return nil}//只有一個結點if t.left == nil { //只有一個右結點  父結點和左孩子結點相連return t.right}if t.right == nil { //只有一個左結點  父結點和右孩子結點相連return t.left}//左右孩子結點都存在//找到 中序后繼結點 -- 右孩子一直向左找minNode := t.right.MinNode()//用這個結點替換要刪除的結點t.data = minNode.data//刪除中序后繼結點--因為是查找的右孩子的中序后繼,所以調整右子樹t.right = t.right.Delete(minNode.data)}return t
}// 查找中序后繼結點  
func (t *TSNode) MinNode() *TSNode {if t.left == nil {return t}return t.left.MinNode()
}

5. 中序遍歷

使用遞歸遍歷,和二叉樹的中序遍歷一樣
先遞歸左子樹,再打印節點的值,最后遞歸右子樹

// 中序遍歷
func (t *TSNode) InOrder() {if t == nil {return}t.left.InOrder()fmt.Printf("%d ", t.data)t.right.InOrder()
}

中序前驅/后繼結點

在這里插入圖片描述

  • 中序后繼結點:在中序遍歷中緊跟在某個節點后面的節點
    怎么找中序后繼結點呢?
    先走到一個結點Node 的右孩子,再從右孩子不斷向左走,直到某個節點的左孩子為空,那這個結點就是Node 的中序后繼結點
    比如要找30的中序后繼結點,30走到40,40向左走到35,35的左孩子為空,那35就是30的后繼結點

  • 中序前驅結點:在中序遍歷中在某個結點前一個的結點
    怎么找中序前驅結點呢?
    先走到一個結點Node 的左孩子,再從左孩子不斷向右走,直到某個節點的右孩子為空,那這個結點就是Node 的中序前驅結點
    比如要找30的中序前驅結點,30走到左孩子20,20向右走到25,25的右孩子為空,所以25就是30的中序前驅結點

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

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

相關文章

自動化:批量文件重命名

自動化&#xff1a;批量文件重命名 1、前言 2、效果圖 3、源碼 一、前言 今天來分享一款好玩的自動化腳&#xff1a;批量文件重命名 有時候呢&#xff0c;你的文件被下載下來文件名都是亂七八糟毫無規律&#xff0c;但是當時你下載的時候沒辦法重名或者你又不想另存為重新重…

VueUse/Core:提升Vue開發效率的實用工具庫

文章目錄 引言什么是VueUse/Core&#xff1f;為什么選擇VueUse/Core&#xff1f;核心功能詳解1. 狀態管理2. 元素操作3. 實用工具函數4. 瀏覽器API封裝5. 傳感器相關 實戰示例&#xff1a;構建一個拖拽上傳組件性能優化技巧與原生實現對比常見問題解答總結 引言 在現代前端開發…

stm32 ADC單通道轉換

stm32c8t6僅有12位分辨率 1、單次轉換 非掃描 1、初始化 void Ad_Init() {RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA, ENABLE);RCC_APB2PeriphClockCmd(RCC_APB2Periph_ADC1, ENABLE);//配置ADCCLK時鐘分頻,ADC的輸入時鐘不得超過14MHzRCC_ADCCLKConfig(RCC_PCLK2_Div6);G…

2KW壓縮機驅動參考設計【SCH篇】

實物展示&#xff1a; ACDC: VAC和VAC-為交流電壓檢測&#xff1a; 1.C33 C34作為Y電容走線寬度要求&#xff1a; Y電容一般用于L/N到地之間&#xff08;L-PE 或 N-PE&#xff09;&#xff0c;主要作用是抑制共模干擾。其走線的電流非常小&#xff0c;推薦使用 ≥ 1mm 寬的走…

python05——循環結構

1、while循環 n0 #初始條件 while n<5: #判斷print(hello python) #要重復執行的代碼print(n) #注意同級代碼縮進相同n1 #計數器結果&#xff1a; hello python 0 hello python 1 hello python 2 hello python 3 hello python 4 hello python 5 #求階乘和 sum0 n1 whil…

LINUX編譯、運行、測試lowcoder_CN

參考 二者沒有太大差異。 LINUX編譯、運行、測試lowcoder-CSDN博客 下載 git clone https://github.com/mousheng/lowcoder_CN 或 git clone https://gitcode.com/gh_mirrors/lo/lowcoder_CNcd lowcoder_CN三個模塊 node-service api-service client 每個模塊都有自己的…

Python 基礎之函數命名

幾個問題 使用描述性蛇形命名法&#xff08;snake_case&#xff09;Python函數名應使用什么大小寫格式&#xff1f;為什么函數名要具有描述性&#xff1f;方法的命名規范是什么&#xff1f;函數、變量和類的命名有何區別&#xff1f; Python函數的命名有一些不可違背的硬性規…

redis 命令大全整理

http://doc.redisfans.com/ 原網址 Redis 命令分類 Key(鍵) Key(鍵)命令 exists/del/keys/type/scanobject/move/dump/migratettl/pttl/persist/expireat/pexpireat/expire/pexpirerename/renamenxsort/randomkey/restoreexists 語法:exists key [key ...] 檢查一個或多…

React中useDeferredValue與useTransition終極對比。

文章目錄 前言一、核心差異對比二、代碼示例對比1. useDeferredValue&#xff1a;延遲搜索結果更新2. useTransition&#xff1a;延遲路由切換 三、應用場景總結四、注意事項五、原理剖析1. 核心機制對比2. 關鍵差異3. 代碼實現原理 總結 前言 在React的并發模式下&#xff0c…

高并發內存池|定長內存池的設計

二、定長內存池的設計 設計一個定長的內存池&#xff0c;這個內存池的定長在于&#xff0c;當剩余空間使用完畢后&#xff0c;總是開辟相同長度的新空間來使用。我們會使用到一個指針來切割劃分大空間為小空間。大空間是內存池向系統申請的內存大小&#xff0c;而小空間是程序…

微信小程序 自定義圖片分享-繪制數據圖片以及信息文字

一 、需求 從數據庫中讀取頭像&#xff0c;姓名電話等信息&#xff0c;當分享給女朋友時&#xff0c;每個信息不一樣 二、實現方案 1、先將數據庫中需要的頭像姓名信息讀取出來加載到data 數據項中 data:{firstName:, // 姓名img:, // 頭像shareImage:,// 存儲臨時圖片 } 2…

從零開始理解Jetty:輕量級Java服務器的入門指南

目錄 一、Jetty是什么&#xff1f;先看一個生活比喻 二、5分鐘快速入門&#xff1a;搭建你的第一個Jetty服務 步驟1&#xff1a;Maven依賴配置 步驟2&#xff1a;編寫簡易Servlet&#xff08;廚房廚師&#xff09; 步驟3&#xff1a;組裝服務器&#xff08;餐廳開業準備&am…

深入淺出IIC協議 - 從總線原理到FPGA實戰開發 -- 第一篇:I2C總線協議深度解剖

第一篇&#xff1a;I2C總線協議深度解剖 副標題 : 兩根線如何征服千億設備&#xff1f;詳解硬件工程師必須掌握的通信奧義 1. 為什么I2C仍是嵌入式經典&#xff1f; 1.1 總線拓撲的哲學 拓撲對比圖 SPI需4線N片選 vs I2C僅2線級聯 UART點對點 vs I2C多主從架構 成本控制實…

MySQL 索引優化以及慢查詢優化

在數據庫性能優化中&#xff0c;索引優化和慢查詢優化是兩個關鍵環節。合理使用索引可以顯著提高查詢效率&#xff0c;而識別和優化慢查詢則能提升整體數據庫性能。本文將詳細介紹MySQL索引優化和慢查詢優化的方法和最佳實踐。 一、MySQL 索引優化 1.1 索引的基本概念 索引是…

vue使用Pinia實現不同頁面共享token

文章目錄 一、概述二、使用步驟安裝pinia在vue應用實例中使用pinia在src/stores/token.js中定義store在組件中使用store登錄成功后&#xff0c;將token保存pinia中向后端API發起請求時&#xff0c;攜帶從pinia中獲取的token 三、參考資料 一、概述 Pinia是Vue的專屬狀態管理庫…

通俗版解釋CPU、核心、進程、線程、協程的定義及關系

通俗版解釋&#xff08;比喻法&#xff09; 1. CPU 和核心 CPU 一個工廠&#xff08;負責干活的總部&#xff09;。核心 工廠里的車間&#xff08;比如工廠有4個車間&#xff0c;就能同時處理4個任務&#xff09;。 2. 進程 進程 一家獨立運營的公司&#xff08;比如一家…

用 VS Code / PyCharm 編寫你的第一個 Python 程序

用ChatGPT做軟件測試 編寫你的第一個 Python 程序——不只是“Hello, World”&#xff0c;而是構建認知、習慣與未來的起點 “第一行代碼&#xff0c;是一個開發者認知世界的方式。” 編程的入門&#xff0c;不只是運行一個字符串輸出&#xff0c;更是開始用計算機思維來理解、…

amd架構主機構建arm架構kkfileview

修改本機使用鏡像倉庫地址 vim /etc/docker/daemon.json {“experimental”: true, “registry-mirrors”: [ “https://docker.m.daocloud.io”, “https://docker.1panel.live”, “http://mirrors.ustc.edu.cn/”, “http://mirror.azure.cn/”, “https://docker.hpcloud.c…

[Linux] vim及gcc工具

目錄 一、vim 1.vim的模式 2.vim的命令集 (1):命令模式 (2):底行模式 3.vim配置 二、gcc 1.gcc格式及選項 2.工作布置 三、自動化構建工具makefile 1.基本使用方法 2.配置文件解析 3.拓展 在linux操作系統的常用工具中&#xff0c;常用vim來進行程序的編寫&#xff1b…

數據庫3——視圖及安全性

視圖及安全性 學習內容學習感受 學習內容 一、實驗目的與要求&#xff1a; 1、設計用戶子模式 2、根據實際需要創建用戶角色及用戶&#xff0c;并授權 3、針對不同級別的用戶定義不同的視圖&#xff0c;以保證系統的安全性 二、實驗內容&#xff1a; 1、 先創建四類用戶角色&…