前言

如果你是一個(gè)開發(fā)人員，或多或少對(duì)樹型結(jié)構(gòu)都有一定的認(rèn)識(shí)，我個(gè)人對(duì)樹型數(shù)據(jù)結(jié)構(gòu)是又愛又恨。二叉樹作為樹的一種,是一種重要的數(shù)據(jù)結(jié)構(gòu),也是面試官經(jīng)?？嫉臇|西。這篇文章主要分享下關(guān)于二叉樹相關(guān)的知識(shí)點(diǎn)，并用go語(yǔ)言實(shí)現(xiàn)一個(gè)二叉樹和對(duì)二叉樹進(jìn)行遍歷。

二叉樹概念

二叉樹是具有兩個(gè)節(jié)點(diǎn)的樹形結(jié)構(gòu)，通常左邊的子樹被稱為左子樹，右邊的子樹稱為右子樹，圖示如下：

在代碼中我們可以用代碼來(lái)定義一個(gè)二叉樹結(jié)構(gòu)：

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

二叉樹的性質(zhì)

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

深度為k的二叉樹至少有k個(gè)結(jié)點(diǎn)，最多有2i - 1個(gè)結(jié)點(diǎn)。

對(duì)任何一個(gè)二叉樹，如果其葉結(jié)點(diǎn)有n0 個(gè)，度為2的非葉結(jié)點(diǎn)有n2 個(gè)，則有 n0 = n2 + 1

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為⌈log2(??+1)⌉

創(chuàng)建二叉樹

// 創(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
}

樹的遍歷

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

前序遍歷(V-L-R)

前序遍歷訪問(wèn)順序?yàn)橄容?root 結(jié)點(diǎn)，然后再輸出左子樹，然后再輸出右子樹。

我們通過(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 的左子樹，再輸 root 結(jié)點(diǎn)，最后輸出 root 的右子樹。

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 的左子樹，最后輸出 root 的右子樹，再輸 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)之二叉樹必會(huì)知識(shí)點(diǎn)總結(jié)的文章就介紹到這了,更多相關(guān)Go語(yǔ)言二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論