欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Go語言數(shù)據(jù)結構之二叉樹必會知識點總結

 更新時間:2022年08月26日 08:43:52   作者:yi個俗人  
如果你是一個開發(fā)人員,或多或少對樹型結構都有一定的認識。二叉樹作為樹的一種,是一種重要的數(shù)據(jù)結構,也是面試官經(jīng)??嫉臇|西。本文為大家總結了一些二叉樹必會知識點,需要的可以參考一下

前言

如果你是一個開發(fā)人員,或多或少對樹型結構都有一定的認識,我個人對樹型數(shù)據(jù)結構是又愛又恨。二叉樹作為樹的一種,是一種重要的數(shù)據(jù)結構,也是面試官經(jīng)常考的東西。這篇文章主要分享下關于二叉樹相關的知識點,并用go語言實現(xiàn)一個二叉樹和對二叉樹進行遍歷。

二叉樹概念

二叉樹是具有兩個節(jié)點的樹形結構,通常左邊的子樹被稱為左子樹,右邊的子樹稱為右子樹,圖示如下:

在代碼中我們可以用代碼來定義一個二叉樹結構:

type treeNode struct {
    Val string 	    //節(jié)點值
    left *treeNode 	//左節(jié)點
    right *treeNode //右節(jié)點
}

二叉樹的性質(zhì)

若二叉樹結點的層次從1開始,則在二叉樹第i層最多有2i-1 (i > 0)個節(jié)點。

深度為k的二叉樹至少有k個結點,最多有2i - 1個結點。

對任何一個二叉樹,如果其葉結點有n0 個,度為2的非葉結點有n2 個,則有 n0 = n2 + 1

具有n個結點的完全二叉樹的深度為⌈log2(??+1)⌉

創(chuàng)建二叉樹

// 創(chuàng)建節(jié)點
func CreateBinaryTree(data string) *treeNode {
    return &treeNode{data, nil, nil}
}

// 插入節(jié)點
func (node *treeNode) Insert(n *treeNode, data string) bool {
    cur := n
    for cur != nil {
        if cur.Val < data {
            if cur.Right != nil {
                cur = cur.Right
            } else {
                cur.Right = CreateBinaryTree(data)
                return true
            }
        } else {
            if cur.Left != nil {
                cur = cur.Left
            } else {
                cur.Left = CreateBinaryTree(data) 
                return true
            }
        }
    }
    return false
}

樹的遍歷

樹的遍歷分為三種方式,分別為前序遍歷,中序遍歷,后序遍歷。

前序遍歷(V-L-R)

前序遍歷訪問順序為先輸 root 結點,然后再輸出左子樹,然后再輸出右子樹。

我們通過遞歸的方式進行遍歷

func preOrder(root *bt) {
	if root != nil {
		fmt.Print(root.Val, " ")
		preOrder(root.Left)
		preOrder(root.Right)
	}
}

中序遍歷(L-V-R)

中序遍歷訪問順序為先輸出 root 的左子樹,再輸 root 結點,最后輸出 root 的右子樹。

func inOrder(root *bt) {
	if root != nil {
		inOrder(root.Left)
		fmt.Print(root.Val, " ")
		inOrder(root.Right)
	}
}

后序遍歷(L-R-V)

后序遍歷訪問順序為先輸出 root 的左子樹,最后輸出 root 的右子樹,再輸 root 結點。

func posOrder(root *bt) {
	if root != nil {
		posOrder(root.Left)
		posOrder(root.Right)
		fmt.Print(root.Val, " ")
	}
}

到此這篇關于Go語言數(shù)據(jù)結構之二叉樹必會知識點總結的文章就介紹到這了,更多相關Go語言二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!

相關文章

  • GoLang sync.Pool簡介與用法

    GoLang sync.Pool簡介與用法

    這篇文章主要介紹了GoLang sync.Pool簡介與用法,Pool是可伸縮、并發(fā)安全的臨時對象池,用來存放已經(jīng)分配但暫時不用的臨時對象,通過對象重用機制,緩解GC壓力,提高程序性能
    2023-01-01
  • 詳解Go語言中select語句的常見用法

    詳解Go語言中select語句的常見用法

    這篇文章主要是來和大家介紹一下Go語言中select?語句的常見用法,以及在使用過程中的注意事項,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下
    2023-07-07
  • Go語言判斷文件或文件夾是否存在的方法

    Go語言判斷文件或文件夾是否存在的方法

    這篇文章主要介紹了Go語言判斷文件或文件夾是否存在的方法,結合具體實例形式對比分析了Go語言針對文件與目錄判斷的操作技巧與相關注意事項,需要的朋友可以參考下
    2017-05-05
  • Go語言標準庫flag的具體實現(xiàn)

    Go語言標準庫flag的具體實現(xiàn)

    Go語言的flag庫提供了一套簡單而強大的接口,用于解析命令行參數(shù),本文主要介紹了Go語言標準庫flag的具體實現(xiàn),具有一定的參考價值,感興趣的可以了解一下
    2024-03-03
  • Go實現(xiàn)并發(fā)的示例代碼

    Go實現(xiàn)并發(fā)的示例代碼

    Go語言的并發(fā)機制是其強大和流行的一個關鍵特性之一,本文主要介紹了Go實現(xiàn)并發(fā)的示例代碼,具有一定的參考價值,感興趣的可以了解一下
    2023-11-11
  • 淺析Gin框架中路由參數(shù)的使用

    淺析Gin框架中路由參數(shù)的使用

    這篇文章主要為大家介紹了路由參數(shù)的基本語法,以及路由匹配和路由參數(shù)值提取等相關內(nèi)容,以幫助讀者更好地對Gin?框架中路由參數(shù)進行使用,需要的可以參考下
    2023-08-08
  • golang 數(shù)組去重,利用map的實現(xiàn)

    golang 數(shù)組去重,利用map的實現(xiàn)

    這篇文章主要介紹了golang 數(shù)組去重,利用map的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-04-04
  • gorm update傳入struct對象,零值字段不更新的解決方案

    gorm update傳入struct對象,零值字段不更新的解決方案

    這篇文章主要介紹了gorm update傳入struct對象,零值字段不更新的解決方案,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-04-04
  • Go語言學習之將mp4通過rtmp推送流媒體服務的實現(xiàn)方法

    Go語言學習之將mp4通過rtmp推送流媒體服務的實現(xiàn)方法

    對音視頻一直是小白,決定沉下心來,好好研究一下音視頻知識,下面這篇文章主要給大家介紹了關于Go語言學習之將mp4通過rtmp推送流媒體服務的實現(xiàn)方法,需要的朋友可以參考下
    2022-12-12
  • go循環(huán)依賴的最佳解決方案

    go循環(huán)依賴的最佳解決方案

    ? import cycle not allowed(循環(huán)依賴不被允許)相信作為每一個golang語言使用研發(fā),都遇到過這個令人頭痛的報錯,循環(huán)依賴是指兩個或多個模塊之間互相依賴,形成了一個閉環(huán)的情況,本文會結合部分案例對解決方案進行講解,需要的朋友可以參考下
    2023-10-10

最新評論