数据结构
网络
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 次浏览
