Golang 查找二叉搜索树中节点的深度

在这篇 Golang 文章中，我们将使用递归和迭代方法来查找二叉搜索树中节点的深度。二叉搜索树是一种用于高效搜索、插入和删除元素的有用数据结构。二叉搜索树（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)) 
}