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() 函数在屏幕上打印二叉搜索树中节点的深度。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例 1

在此示例中，我们将使用递归定义一个 Depth() 函数，该函数用于查找二叉搜索树中节点的深度。节点的深度定义为从根到节点的边的数量。

Open Compiler
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() 函数，该函数用于查找二叉搜索树中节点的深度。节点的深度定义为从根到节点的边的数量。

Open Compiler
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 中节点的最终深度将作为输出打印到控制台。

更新于: 2023年4月3日

475 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告