Go語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)必會(huì)知識(shí)點(diǎn)總結(jié)
前言
如果你是一個(gè)開(kāi)發(fā)人員,或多或少對(duì)樹(shù)型結(jié)構(gòu)都有一定的認(rèn)識(shí),我個(gè)人對(duì)樹(shù)型數(shù)據(jù)結(jié)構(gòu)是又愛(ài)又恨。二叉樹(shù)作為樹(shù)的一種,是一種重要的數(shù)據(jù)結(jié)構(gòu),也是面試官經(jīng)常考的東西。這篇文章主要分享下關(guān)于二叉樹(shù)相關(guān)的知識(shí)點(diǎn),并用go語(yǔ)言實(shí)現(xiàn)一個(gè)二叉樹(shù)和對(duì)二叉樹(shù)進(jìn)行遍歷。
二叉樹(shù)概念
二叉樹(shù)是具有兩個(gè)節(jié)點(diǎn)的樹(shù)形結(jié)構(gòu),通常左邊的子樹(shù)被稱為左子樹(shù),右邊的子樹(shù)稱為右子樹(shù),圖示如下:
在代碼中我們可以用代碼來(lái)定義一個(gè)二叉樹(shù)結(jié)構(gòu):
type treeNode struct { Val string //節(jié)點(diǎn)值 left *treeNode //左節(jié)點(diǎn) right *treeNode //右節(jié)點(diǎn) }
二叉樹(shù)的性質(zhì)
若二叉樹(shù)結(jié)點(diǎn)的層次從1開(kāi)始,則在二叉樹(shù)第i層最多有2i-1 (i > 0)個(gè)節(jié)點(diǎn)。
深度為k的二叉樹(shù)至少有k個(gè)結(jié)點(diǎn),最多有2i - 1個(gè)結(jié)點(diǎn)。
對(duì)任何一個(gè)二叉樹(shù),如果其葉結(jié)點(diǎn)有n0 個(gè),度為2的非葉結(jié)點(diǎn)有n2 個(gè),則有 n0 = n2 + 1
具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為⌈log2(??+1)⌉
創(chuàng)建二叉樹(shù)
// 創(chuàng)建節(jié)點(diǎn) func CreateBinaryTree(data string) *treeNode { return &treeNode{data, nil, nil} } // 插入節(jié)點(diǎn) 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 }
樹(shù)的遍歷
樹(shù)的遍歷分為三種方式,分別為前序遍歷,中序遍歷,后序遍歷。
前序遍歷(V-L-R)
前序遍歷訪問(wèn)順序?yàn)橄容?root 結(jié)點(diǎn),然后再輸出左子樹(shù),然后再輸出右子樹(shù)。
我們通過(guò)遞歸的方式進(jìn)行遍歷
func preOrder(root *bt) { if root != nil { fmt.Print(root.Val, " ") preOrder(root.Left) preOrder(root.Right) } }
中序遍歷(L-V-R)
中序遍歷訪問(wèn)順序?yàn)橄容敵?root 的左子樹(shù),再輸 root 結(jié)點(diǎn),最后輸出 root 的右子樹(shù)。
func inOrder(root *bt) { if root != nil { inOrder(root.Left) fmt.Print(root.Val, " ") inOrder(root.Right) } }
后序遍歷(L-R-V)
后序遍歷訪問(wèn)順序?yàn)橄容敵?root 的左子樹(shù),最后輸出 root 的右子樹(shù),再輸 root 結(jié)點(diǎn)。
func posOrder(root *bt) { if root != nil { posOrder(root.Left) posOrder(root.Right) fmt.Print(root.Val, " ") } }
到此這篇關(guān)于Go語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)必會(huì)知識(shí)點(diǎn)總結(jié)的文章就介紹到這了,更多相關(guān)Go語(yǔ)言二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
詳解Go語(yǔ)言中select語(yǔ)句的常見(jiàn)用法
這篇文章主要是來(lái)和大家介紹一下Go語(yǔ)言中select?語(yǔ)句的常見(jiàn)用法,以及在使用過(guò)程中的注意事項(xiàng),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-07-07Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)flag的具體實(shí)現(xiàn)
Go語(yǔ)言的flag庫(kù)提供了一套簡(jiǎn)單而強(qiáng)大的接口,用于解析命令行參數(shù),本文主要介紹了Go語(yǔ)言標(biāo)準(zhǔn)庫(kù)flag的具體實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下2024-03-03golang 數(shù)組去重,利用map的實(shí)現(xiàn)
這篇文章主要介紹了golang 數(shù)組去重,利用map的實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-04-04gorm update傳入struct對(duì)象,零值字段不更新的解決方案
這篇文章主要介紹了gorm update傳入struct對(duì)象,零值字段不更新的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-04-04Go語(yǔ)言學(xué)習(xí)之將mp4通過(guò)rtmp推送流媒體服務(wù)的實(shí)現(xiàn)方法
對(duì)音視頻一直是小白,決定沉下心來(lái),好好研究一下音視頻知識(shí),下面這篇文章主要給大家介紹了關(guān)于Go語(yǔ)言學(xué)習(xí)之將mp4通過(guò)rtmp推送流媒體服務(wù)的實(shí)現(xiàn)方法,需要的朋友可以參考下2022-12-12