Golang 打印二叉树的高度

二叉树是一种最多有两个子节点的树，高度指的是树中的层数。在本文中，我们将使用两个示例来找到二叉树的高度。在这篇Golang文章中，我们将编写程序来打印二叉树的高度。

语法

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组片段添加值。它接受一定数量的参数。第一个参数是要添加值的数组，其后是要添加的值。函数然后返回包含所有值的最终数组片段。

funclen(v Type) int

len()函数用于获取任何参数的长度。它接受一个参数作为我们希望获取长度的数据类型变量，并返回整数值，该值为变量的长度。

步骤

步骤1 - 创建一个Node结构，在该结构中创建三个字段，left和right为节点类型，data为整数类型。
步骤2 - 创建一个名为get_height的函数，以根节点作为参数。
步骤3 - 在函数中，检查如果根节点为空，则返回0。
步骤4 - 如果条件不成立，则使用root.left递归地找到左子树的高度。
步骤5 - 类似地，使用root.right递归地找到右子树的高度。
步骤6 - 然后，使用if条件检查如果左子树的高度大于右子树的高度，则返回left height + 1，其中1代表根元素。
步骤7 - 但是，如果左子树的高度小于右子树的高度，则返回right height + 1。
步骤8 - 在主函数中，创建一棵树，设置左子树和右子树中的数据。
步骤9 - 调用get_height函数，以根节点为输入参数，计算树的高度。

示例1

在这个示例中，将递归地调用左子树和右子树来计算树的高度。将创建树，并在左子树和右子树中设置数据。

package main

import "fmt"

type Node struct {
   data  int
   left  *Node
   right *Node
}

func get_height(root *Node) int {
   if root == nil {
      return 0
   } else {
      left_height := get_height(root.left)
      right_height := get_height(root.right)

      if left_height>right_height {
         return left_height + 1
      } else {
         return right_height + 1
      }
   }
}

func main() {

   root := &Node{
      data: 10,
      left: &Node{
         data: 20,
         left: &Node{
            data:  40,
            left:  nil,
            right: nil,
         },
         right: &Node{
            data:  50,
            left:  nil,
            right: nil,
         },
      },
      right: &Node{
         data:  30,
         left:  nil,
         right: nil,
      },
   }

   fmt.Println("Height of the binary tree is:", get_height(root))
}

输出

Height of the binary tree is: 3

示例2

在这个示例中，队列将被用来添加树的当前层级中的节点，即左子树和右子树。然后这些节点稍后被出队，并返回树的高度。

package main

import "fmt"

type Node struct {
   data  int
   left  *Node
   right *Node
}

func get_height(root *Node) int {
   if root == nil {
      return 0
   }

   var v []*Node
   var level_size int
   height := 0

   v = append(v, root)

   for len(v) > 0 {

      level_size = len(v)

      height++

      for i := 0; i<level_size; i++ {
         node := v[0]
         v = v[1:]

         if node.left != nil {
            v = append(v, node.left)
         }
         if node.right != nil {
            v = append(v, node.right)
         }
      }
   }

   return height
}

func main() {

   root := &Node{
      data: 10,
      left: &Node{
         data: 20,
         left: &Node{
            data:  40,
            left:  nil,
            right: nil,
         },
         right: &Node{
            data:  50,
            left:  nil,
            right: nil,
         },
      },
      right: &Node{
         data:  30,
         left:  nil,
         right: nil,
      },
   }

   fmt.Println("Height of the binary tree is:", get_height(root))
}