Golang 用于执行中序遍历二叉树操作

在Go编程语言中，树是一种经常使用的数据结构，类似于倒置的树或反向树，节点之间存在父子关系。在树中，每个节点都有一个值和零个或多个后代节点。根节点是没有父节点的节点，而叶子节点是没有子节点的节点。树可以用于各种任务，包括在分层结构中进行数据存储、排序和搜索。我们将使用两种方法执行中序遍历二叉树操作。

语法

func make ([] type, size, capacity)

在Go语言中，make函数用于创建一个数组或映射，它接受要创建的变量类型、尺寸和容量作为参数。

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

append函数用于将值添加到数组切片中。它接受多个参数。第一个参数是我们希望添加值的数组，后面是要添加的值。该函数返回包含所有值的最终切片。

步骤

• 步骤1 - 创建一个主包并在程序中声明fmt（格式化包）和strings包，其中主要产生可执行代码，fmt用于格式化输入和输出。

• 步骤2 - 为了表示包含值、指向左子节点的指针和指向右子节点的指针的二叉树节点，定义一个TreeNode结构。

• 步骤3 - 定义一个inorder_traversal函数，该函数接受指向二叉树根节点的指针，并返回一个显示树中序遍历的数字切片。

• 步骤4 - 如果根节点为nil，则inorder_traversal函数应返回一个空切片。

• 步骤5 - 如果根节点不为null，则将在左子节点上进行的inorder_traversal调用的结果添加到输出切片中。

• 步骤6 - 输出切片应包括当前节点的值。

• 步骤7 - 对右子节点上的inorder_traversal调用的输出进行切片。

• 步骤8 - 将输出切片返回给函数。

• 步骤9 - 在主函数中创建一个二叉树，并在根节点上调用inorder_traversal。

• 步骤10 - 使用fmt.Println()函数在控制台上打印中序遍历的结果，ln表示新行。

示例1

在这个示例中，我们使用递归来执行程序。

package main
import "fmt"

// Definition for a binary tree node
type TreeNode struct {
   Val       int
   Left_val  *TreeNode
   Right_val *TreeNode
}

func inorder_traversal(root *TreeNode) []int {
   output := make([]int, 0)
   if root == nil {
      return output
   }
   output = append(output, inorder_traversal(root.Left_val)...)
   output = append(output, root.Val)
   output = append(output, inorder_traversal(root.Right_val)...)
   return output
}

func main() {
   root := &TreeNode{Val: 10}
   root.Left_val = &TreeNode{Val: 20}
   root.Right_val = &TreeNode{Val: 30}
   root.Left_val.Left_val = &TreeNode{Val: 40}
   root.Left_val.Right_val = &TreeNode{Val: 50}

   output := inorder_traversal(root)
   fmt.Println("The inorder traversal is given as:")
   fmt.Println(output) //print the inorder tree traversal
}

输出

The inorder traversal is given as:
[40 20 50 10 30]

示例2

在这个示例中，我们将使用堆栈来实现中序遍历树。

package main
import "fmt"

// Definition for a binary tree node
type TreeNode struct {
   Val  int
   Left_val  *TreeNode
   Right_val *TreeNode
}

func inorder_traversal(root *TreeNode) []int {
   result := make([]int, 0)
   stack := make([]*TreeNode, 0)
   curr := root

   for curr != nil || len(stack) > 0 {
      for curr != nil {
         stack = append(stack, curr)
         curr = curr.Left_val
      }
      curr = stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      result = append(result, curr.Val)
      curr = curr.Right_val
   }
   return result
}

func main() {
   root := &TreeNode{Val: 10}
   root.Left_val = &TreeNode{Val: 20}
   root.Right_val = &TreeNode{Val: 30}
   root.Left_val.Left_val = &TreeNode{Val: 40}
   root.Left_val.Right_val = &TreeNode{Val: 50}

   result := inorder_traversal(root)
   fmt.Println("The inorder traversal can be represented as:")
   fmt.Println(result)  //print the inorder tree traversal
}

输出

The inorder traversal can be represented as:
[40 20 50 10 30]

结论

我们使用两种方法执行了中序遍历的程序。在第一个示例中，我们使用递归，在第二个示例中我们使用栈。