Go語言數(shù)據(jù)結構之二叉樹必會知識點總結
前言
如果你是一個開發(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 數(shù)組去重,利用map的實現(xiàn)
這篇文章主要介紹了golang 數(shù)組去重,利用map的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-04-04gorm update傳入struct對象,零值字段不更新的解決方案
這篇文章主要介紹了gorm update傳入struct對象,零值字段不更新的解決方案,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04Go語言學習之將mp4通過rtmp推送流媒體服務的實現(xiàn)方法
對音視頻一直是小白,決定沉下心來,好好研究一下音視頻知識,下面這篇文章主要給大家介紹了關于Go語言學習之將mp4通過rtmp推送流媒體服務的實現(xiàn)方法,需要的朋友可以參考下2022-12-12