資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go 語言程式查詢二叉搜尋樹中節點的深度
在這篇 Go 語言文章中，我們將使用遞迴和迭代方法查詢二叉搜尋樹中節點的深度。二叉搜尋樹是一種有用的資料結構，可以有效地搜尋、插入和刪除元素。二叉搜尋樹 (BST) 是一種二叉樹，其中每個節點最多有兩個子節點，通常稱為左子節點和右子節點。
語法
func (n *Node) Depth(value int) int {…}
Depth() 函式用於查詢二叉搜尋樹中節點的深度。它接受一個整數值作為引數。
演算法
步驟 1 − 首先，我們需要匯入 fmt 包。
步驟 2 − 然後，初始化一個節點結構體並在其中分配三個變數。第一個變數儲存整數值，而第二個和第三個指標變數分別儲存指向左節點和右節點的地址。
步驟 3 − 現在，建立一個 insert() 函式，它接受一個節點和一個要插入的值。此函式遞迴地將值插入到相應的二叉搜尋樹中。
步驟 4 − 此函式遞迴/迭代搜尋插入新節點的適當位置，基於二叉搜尋樹的特性。
步驟 5 − 現在，定義一個名為 Depth() 的函式。它用於查詢二叉搜尋樹中節點的深度。此函式接受一個整數值作為輸入並返回具有給定值的節點的深度。
步驟 6 − Depth() 函式使用遞迴搜尋具有給定值的節點，並在遍歷樹時計算節點的深度。
步驟 7 − 啟動 main() 函式。在 main() 函式內部，將多個節點插入到二叉搜尋樹中。
步驟 8 − 現在，呼叫 Depth() 函式並將整數值作為引數傳遞給函式。
步驟 9 − 此外，使用 fmt.Println() 函式在螢幕上列印二叉搜尋樹中節點的深度。
示例 1
在此示例中，我們將使用遞迴定義一個 Depth() 函式，該函式用於查詢二叉搜尋樹中節點的深度。節點的深度定義為從根到節點的邊的數量。
package main
import (
"fmt"
)
type Node struct {
value int
left *Node
right *Node
}
func (n *Node) Insert(value int) *Node {
if n == nil {
return &Node{value, nil, nil}
}
if value < n.value {
n.left = n.left.Insert(value)
} else {
n.right = n.right.Insert(value)
}
return n
}
func (n *Node) Depth(value int) int {
if n == nil {
return -1
}
if value == n.value {
return 0
}
if value < n.value {
return n.left.Depth(value) + 1
}
return n.right.Depth(value) + 1
}
func main() {
root := &Node{5, nil, nil}
root.Insert(5).Insert(3).Insert(7).Insert(2).Insert(4)
fmt.Println(root.Depth(5))
fmt.Println(root.Depth(7))
}
輸出
0 2
示例 2
在此示例中，我們將使用迭代方法定義一個 Depth() 函式，該函式用於查詢二叉搜尋樹中節點的深度。節點的深度定義為從根到節點的邊的數量。
package main
import (
"fmt"
)
type Node struct {
value int
left *Node
right *Node
}
func (n *Node) Insert(value int) {
if n == nil {
return
}
if value < n.value {
if n.left == nil {
n.left = &Node{value: value}
} else {
n.left.Insert(value)
}
} else {
if n.right == nil {
n.right = &Node{value: value}
} else {
n.right.Insert(value)
}
}
}
func (n *Node) Depth(value int) int {
depth := 0
for n != nil {
if n.value == value {
return depth
} else if value < n.value {
n = n.left
} else {
n = n.right
}
depth++
}
return -1
}
func main() {
root := &Node{value: 5}
root.Insert(5)
root.Insert(8)
root.Insert(3)
root.Insert(4)
root.Insert(2)
fmt.Println(root.Depth(8))
fmt.Println(root.Depth(5))
fmt.Println(root.Depth(2))
}
輸出
2 0 2
結論
我們已成功編譯並執行了一個 Go 語言程式，以使用遞迴和迭代方法查詢二叉搜尋樹中節點的深度，並附帶兩個示例。在第一個示例中，我們使用了遞迴方法，在第二個示例中，我們使用了迭代方法。BST 中節點的最終深度將作為輸出列印到控制檯。
475 次瀏覽
