Golang程序：在二叉搜索树中查找节点深度

在这篇 Golang 文章中，我们将使用递归和迭代方法在二叉搜索树中查找节点深度。二叉搜索树是一种有用的数据结构，用于高效地搜索、插入和删除元素。二叉搜索树（BST）是二叉树的一种类型，每个节点最多有两个孩子，通常称为左孩子和右孩子。

语法

func (n *Node) Depth(value int) int {…}

Depth() 函数用于查找二叉搜索树中节点的深度。它以整数值作为参数。

算法

第一步 —— 首先，我们需要导入 fmt 包。
第二步 —— 然后，我们需要初始化一个节点结构并为它分配三个变量。第一个变量存储整数值，而第二个和第三个指针变量存储左节点和右节点的地址。
第三步 —— 现在，创建一个 insert() 函数，它接受一个节点和一个要插入的值。此函数将值递归地插入到相应的二叉搜索树中。
第四步 —— 该函数基于二叉搜索树属性递归/迭代地搜索适当位置以插入新节点。
第五步 —— 现在，定义一个名为 Depth() 的函数。它用于查找二叉搜索树中节点的深度。该函数接受一个整数值作为输入，并返回具有给定值的节点的深度。
第六步 —— Depth() 函数使用递归查找具有给定值的节点，并在遍历树时计算节点的深度。
第七步 —— 启动 main() 函数。在 main() 函数内，向二叉搜索树中插入几个节点。
第八步 —— 现在，调用 Depth() 函数并将整数值作为参数传递到函数中。
第九步 —— 进一步地，使用 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)) 
}