Golang 实现前序遍历二叉树

在Go编程语言中，前序遍历是一种二叉树遍历技术，首先访问根节点，然后访问左子树，最后访问右子树。使用递归函数，在根节点、左子节点、右子节点和再次左子节点上调用自身。当节点为空时，递归的基本情况发生。在这个程序中，我们将使用两种方法执行前序遍历-使用TreeNode结构和堆栈。

方法1：使用TreeNode结构

这种方法使用了一个含有Value字段、指向左子节点和右子节点的指针的树节点结构。pre_order_traversal函数使用根节点的指针依次递归访问根节点、左子树和右子树中的节点。在创建示例树之后，main函数调用pre_order_traversal方法打印树的前序遍历。

步骤

步骤1 - 创建一个package main，并在程序中声明fmt（格式化包）包，其中main生成可执行代码，fmt用于格式化输入和输出。
步骤2 - 创建一个值类型为int，拥有左子节点和右子节点类型为TreeNode的TreeNode结构。
步骤3 - 创建一个pre_order_traversal函数，在该函数中返回当前节点是否为空，然后打印当前节点的值。
步骤4 - 在下一步中，使用当前节点的左子节点作为参数调用pre_order_traversal来遍历左子树。
步骤5 - 使用当前节点的右子节点作为参数调用pre_order_traversal来遍历右子树。
步骤6 - 对于每个子节点，重复步骤1-4，直到访问完所有节点。
步骤7 - 通过递归，该算法首先访问根节点，然后访问左子树，最后遍历右子树。当遍历一条分支到达末端或者所有节点都被访问完时，递归结束。

示例

在这个示例中，我们将使用TreeNode结构来实现前序遍历。让我们看一下代码。

package main
import "fmt"

// Define a tree node structure
type TreeNode struct {
   Value     int
   Left_val  *TreeNode
   Right_val *TreeNode
}

// Function to traverse the tree in pre-order
func pre_order_traversal(root *TreeNode) {
   if root == nil {
      return
   }
   fmt.Print(root.Value, " ")
   pre_order_traversal(root.Left_val)
   pre_order_traversal(root.Right_val)
}

func main() {
   // Create a tree
   root := &TreeNode{Value: 10}
   root.Left_val = &TreeNode{Value: 20}
   root.Right_val = &TreeNode{Value: 30}
   root.Left_val.Left_val = &TreeNode{Value: 40}
   root.Left_val.Right_val = &TreeNode{Value: 50}

   // Call the pre-order traversal function
   fmt.Print("Pre-order traversal: ")
   pre_order_traversal(root)
   fmt.Println()
}

输出

Pre-order traversal: 10 20 40 50 30

方法2：使用栈

这种方法使用一个栈来跟踪需要访问的节点。该方法重复地从栈中移除一个节点，打印其值，并按照右节点和左节点的顺序将其推入栈中。栈以根节点开始。这将导致对树的先序遍历，其中每个节点的左子节点在右子节点之前被检查。

步骤

步骤1 - 创建一个 main 包，并在程序中声明 fmt（格式化包），其中 main 生成可执行代码，fmt 用于格式化输入和输出。
步骤2 - 创建一个名为 TreeNode 的结构体，其 value 属性为 int 类型，left_val 和 right_val 属性为 TreeNode 类型。
步骤3 - 创建一个名为 pre_order_traversal 的函数，在该函数中如果根节点为空则返回。
步骤4 - 在接下来的步骤中，从根节点开始创建一个栈。
步骤5 - 通过检查栈的长度是否大于0来运行循环，并在栈仍然非空时重复以下操作：

a. 从栈的顶部移除节点并将其赋值给变量 curr。

b. 打印当前值。

步骤6 - 在 main 函数中调用该函数，并使用 fmt.Println() 函数执行打印语句，其中 ln 表示换行。

示例

在这个示例中，我们将使用栈来展示先序遍历。让我们通过代码来看一下执行过程。

package main
import (
   "fmt"
)

// Define a tree node structure
type TreeNode struct {
   Value     int
   Left_val  *TreeNode
   Right_val *TreeNode
}

// Traverse the tree in pre-order using a stack
func pre_order_traversal(root *TreeNode) {
   if root == nil {
      return
   }
   stack := []*TreeNode{root}
   for len(stack) > 0 {
      curr := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      fmt.Print(curr.Value, " ")
      if curr.Right_val != nil {
         stack = append(stack, curr.Right_val)
      }
      if curr.Left_val != nil {
         stack = append(stack, curr.Left_val)
      }
   }
}

func main() {
   // Create a tree
   root := &TreeNode{Value: 10}
   root.Left_val = &TreeNode{Value: 20}
   root.Right_val = &TreeNode{Value: 30}
   root.Left_val.Left_val = &TreeNode{Value: 40}
   root.Left_val.Right_val = &TreeNode{Value: 50}

   // Call the pre-order traversal function
   fmt.Print("Pre-order traversal: ")
   pre_order_traversal(root)
   fmt.Println()
}