資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Go語言程式查詢樹的直徑
在這篇 Go 語言文章中，我們將使用遞迴和迭代方法來查詢樹的直徑。樹的直徑是指樹中任意兩個葉子節點之間最長路徑上的節點數。
語法
func diameter(root *node) int{…}
diameter() 函式用於查詢樹的直徑。它以指向根節點的指標作為引數。
演算法
**步驟 1** − 首先，我們需要匯入 fmt 包。
**步驟 2** − 現在，建立一個名為 node 的樹的單個節點的結構體。它包含三個欄位，一個是儲存節點的整數資料值，第二個和第三個指向左節點和右節點。
**步驟 3** − 定義 new() 函式來初始化一個新節點。
**步驟 4** − 現在，建立一個 diameter() 函式，它接收一個根節點作為輸入並返回以該節點為根的樹的直徑。
**步驟 5** − 樹的直徑是指樹中任意兩個葉子節點之間最長路徑上的節點數。
**步驟 6** − 如果根節點為 nil，則返回 0。
**步驟 7** − 否則，使用 height 函式計算左子樹和右子樹的高度，並使用 diameter 函式遞迴計算左子樹和右子樹的直徑。
**步驟 8** − 以當前節點為根的樹的直徑是左子樹和右子樹高度之和加一與左子樹和右子樹直徑中的最大值。
**步驟 9** − 現在，建立一個名為 height() 的函式，它接收一個根節點作為輸入並返回以該節點為根的樹的高度。
**步驟 10** − 如果根節點為 nil，則返回 0。否則，遞迴計算左子樹和右子樹的高度，並返回兩者中較大的高度加一。
**步驟 11** − 定義 max() 函式返回兩個整數中較大的一個。
**步驟 12** − 開始 main() 函式。在 main() 函式中，呼叫 new() 函式向二叉樹新增節點。
**步驟 13** − 現在，呼叫 diameter() 函式來查詢樹的直徑。
**步驟 14** − 此外，使用 fmt.Println() 函式將生成的樹的直徑列印到螢幕上。
示例 1
在這個例子中，我們將定義一個使用遞迴方法的 diameter() 函式，該函式用於查詢樹的直徑。
package main
import "fmt"
type node struct {
left *node
right *node
data int
}
func new(data int) *node {
return &node{nil, nil, data}
}
func diameter(root *node) int {
if root == nil {
return 0
}
leftH := height(root.left)
rightH := height(root.right)
leftD := diameter(root.left)
rightD := diameter(root.right)
return max(leftH+rightH+1, max(leftD, rightD))
}
func height(root *node) int {
if root == nil {
return 0
}
return 1 + max(height(root.left), height(root.right))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
root := new(4)
root.left = new(3)
root.right = new(2)
root.left.left = new(1)
root.left.right = new(5)
fmt.Println("Diameter of the tree is: ", diameter(root))
}
輸出
Diameter of the tree is: 4
示例 2
在這個例子中，我們將定義一個使用迭代方法的 diameter() 函式，該函式用於查詢樹的直徑。
package main
import (
"fmt"
)
type TreeNode struct {
val int
left, right *TreeNode
}
func diameter(root *TreeNode) int {
if root == nil {
return 0
}
stack := []*TreeNode{root}
visited := make(map[*TreeNode]bool)
maxDiameters := make(map[*TreeNode]int)
maxDiameter := 0
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
visited[node] = true
leftDiameter := 0
rightDiameter := 0
if node.left != nil {
if _, ok := visited[node.left]; !ok {
stack = append(stack, node.left)
}
leftDiameter = maxDiameters[node.left] + 1
}
if node.right != nil {
if _, ok := visited[node.right]; !ok {
stack = append(stack, node.right)
}
rightDiameter = maxDiameters[node.right] + 1
}
maxDiameter = max(maxDiameter, leftDiameter+rightDiameter)
maxDiameters[node] = max(leftDiameter, rightDiameter)
}
return maxDiameter
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
root := &TreeNode{val: 1}
root.left = &TreeNode{val: 2}
root.right = &TreeNode{val: 3}
root.left.left = &TreeNode{val: 4}
root.left.right = &TreeNode{val: 5}
root.left.left.left = &TreeNode{val: 6}
root.left.left.right = &TreeNode{val: 7}
root.left.left.right.left = &TreeNode{val: 8}
root.left.left.right.left.right = &TreeNode{val: 9}
diameter := diameter(root)
fmt.Printf("The diameter of the tree is: %d.\n", diameter)
}
輸出
The diameter of the tree is: 2
結論
我們已經成功地編譯並執行了一個 Go 語言程式，我們將使用遞迴和迭代方法來查詢樹的直徑，並附帶兩個示例。在第一個示例中，我們使用了遞迴方法；在第二個示例中，我們使用了迭代方法。
225 次檢視
