資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Go語言程式檢查二叉樹是否為二叉搜尋樹
二叉樹最多有兩個子節點，而二叉搜尋樹則要求樹的左側元素小於右側元素。在本文中，我們將編寫 Go 語言程式來檢查二叉樹是否為二叉搜尋樹。我們將使用不同的示例來更好地理解這個概念。
演算法
步驟 1 − 建立一個 Node 結構體，包含三個欄位：節點資料（型別為 int），左子樹節點（型別為 Node）和右子樹節點（型別為 Node）。
步驟 2 − 建立一個名為 is_valid_bstNode 的函式，該函式接受節點、最小元素和最大元素作為引數，並返回一個布林值。
步驟 3 − 如果節點為空，則函式返回 true。
步驟 4 − 如果節點的值小於最小元素或大於最大元素，則返回 false。
步驟 5 − 如果上述條件都不滿足，則函式將遞迴檢查左右子樹，以確保它們都是二叉搜尋樹。
步驟 6 − 在此步驟中，建立一個名為 isBinary_search_tree 的函式，該函式以根節點作為輸入元素。
步驟 7 − 如果根節點為空，則返回 true；否則，呼叫 is_valid_bstNode 函式，並將根節點、負無窮大和正無窮大作為輸入。
步驟 8 − 在 main 函式中，使用樹的左節點和右節點建立一個樹，並呼叫 isBinary_search_tree 函式，並將根節點作為引數。
步驟 9 − 如果輸出為 true，則二叉樹是二叉搜尋樹，否則不是。
示例
在這個例子中，bstNode() 函式將用於比較節點元素與最大和最小元素，而 isBinary_search_tree 函式將透過呼叫 bstNode 函式來確定樹是否為二叉搜尋樹。
package main
import (
"fmt"
)
type Node struct {
num int
Left *Node
Right *Node
}
func is_valid_bstNode(node *Node, min int, max int) bool {
if node == nil {
return true
}
if node.num<= min || node.num>= max {
return false
}
return is_valid_bstNode(node.Left, min, node.num) &&is_valid_bstNode(node.Right, node.num, max)
}
func isBinary_search_tree(root *Node) bool {
if root == nil {
return true
}
return is_valid_bstNode(root, -999999, 999999)
}
func main() {
root := &Node{num: 40}
root.Left = &Node{num: 20}
root.Right = &Node{num: 50}
root.Left.Left = &Node{num: 10}
root.Left.Right = &Node{num: 30}
if isBinary_search_tree(root) {
fmt.Println("The binary tree is a binary search tree")
} else {
fmt.Println("The binary tree is not a binary search tree")
}
}
輸出
The binary tree is a binary search tree
結論
在本文中，我們瞭解瞭如何使用示例執行檢查二叉樹是否為二叉搜尋樹的程式。在這個示例中，我們建立了兩個函式：isBinary_search_tree 用於檢查樹是否為二叉搜尋樹，以及 is_valid_bstNode 用於檢查節點是否為有效的二叉搜尋樹節點。
305 次瀏覽
