日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Go語言數據結構之二叉樹必會知識點總結_Golang

作者：yi個俗人 ? 更新時間： 2022-10-22 編程語言

前言

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

二叉樹概念

二叉樹是具有兩個節點的樹形結構，通常左邊的子樹被稱為左子樹，右邊的子樹稱為右子樹，圖示如下：

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

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

二叉樹的性質

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

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

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

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

創建二叉樹

// 創建節點
func CreateBinaryTree(data string) *treeNode {
    return &treeNode{data, nil, nil}
}

// 插入節點
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, " ")
	}
}

原文鏈接：https://juejin.cn/post/7135758520955174920

欄目分類
最近更新