沒想到 Go 實現排序二叉樹如此簡單！

1、概述

排序二叉樹，也稱爲二叉搜索樹，是一種經典的數據結構。

它不僅是一種二叉樹，還滿足左子樹的所有節點值小於根節點，右子樹的所有節點值大於根節點的條件。

這個特性使得排序二叉樹具有高效的搜索、插入和刪除操作。

2、排序二叉樹的基本概念

排序二叉樹（Binary Search Tree，BST）是一種二叉樹，它的每個節點包含一個鍵值，

同時滿足左子樹的所有節點值小於該節點的值，右子樹的所有節點值大於該節點的值。

這個特性使得 BST 具有快速的搜索、插入和刪除操作。

3、排序二叉樹的實現

在 Go 語言中，可以通過遞歸方式實現排序二叉樹的插入和搜索操作。

以下是一個排序二叉樹的 Go 語言實現示例

package main
import (
  "fmt"
)
type Node struct {
  key   int
  left  *Node
  right *Node
}
type BinarySearchTree struct {
  root *Node
}
func (t *BinarySearchTree) insert(key int) {
  t.root = insertNode(t.root, key)
}
func insertNode(root *Node, key int) *Node {
  if root == nil {
    return &Node{key: key, left: nil, right: nil}
  }
  if key < root.key {
    root.left = insertNode(root.left, key)
  } else if key > root.key {
    root.right = insertNode(root.right, key)
  }
  return root
}
func (t *BinarySearchTree) search(key int) bool {
  return searchNode(t.root, key)
}
func searchNode(root *Node, key int) bool {
  if root == nil {
    return false
  }
  if key == root.key {
    return true
  } else if key < root.key {
    return searchNode(root.left, key)
  } else {
    return searchNode(root.right, key)
  }
}
func main() {
  tree := &BinarySearchTree{}
  tree.insert(8)
  tree.insert(3)
  tree.insert(10)
  tree.insert(1)
  tree.insert(6)
  tree.insert(14)
  tree.insert(4)
  tree.insert(7)
  tree.insert(13)
  searchKey := 6
  if tree.search(searchKey) {
    fmt.Println("找到了關鍵字", searchKey)
  } else {
    fmt.Println("未找到關鍵字", searchKey)
  }
}

主要結構體和方法

  • Node 結構體定義了排序二叉樹的節點，包含鍵值、左右子節點的指針。

  • BinarySearchTree 結構體定義了排序二叉樹，包含根節點的指針。

  • insert 方法用於插入節點到排序二叉樹中，遞歸地在左右子樹中查找合適的位置。

  • search 方法用於在排序二叉樹中搜索指定的鍵值。

4、排序二叉樹的應用

排序二叉樹常用於需要頻繁搜索、插入和刪除操作的場景，比如電話簿、字典等。

由於其高效的搜索性能，使得排序二叉樹在實際應用中廣泛被使用。

func (t *BinarySearchTree) inOrderTraversal() {
  inOrder(t.root)
}
func inOrder(node *Node) {
  if node != nil {
    inOrder(node.left)
    fmt.Print(node.key, " ")
    inOrder(node.right)
  }
}
func main() {
  // ...（在main函數中已經創建了排序二叉樹，省略相關代碼）
  fmt.Print("中序遍歷結果：")
  tree.inOrderTraversal() // 輸出: 1 3 4 6 7 8 10 13 14
}

主要方法

  • inOrderTraversal 方法用於中序遍歷排序二叉樹，實現了對樹的升序遍歷。

通過本文，詳細介紹了排序二叉樹的基本概念、實現方法以及應用場景。

希望通過這些示例代碼，你能更好地理解排序二叉樹這種高效的數據結構，在實際應用中靈活運用。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/FDSWF2N_6NnQz5M_D2BmmQ

猜你喜歡