Golang程序执行前序树形遍历

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

方法1：使用TreeNode结构

这个方法建立了一个树节点结构，它有一个Value字段，一个指向左子节点的指针，以及一个指向右子节点的指针。pre_order_traversal函数使用指向根节点的指针来递归访问根节点、左子树、然后是树中的右子树，并以预设顺序进行访问。pre_order_traversal方法被main函数调用，以便在创建一个样本树后打印树的预顺序遍历。

算法

第1步 – 创建一个包main，并在程序中声明fmt(格式包)包，其中main产生可执行代码，fmt帮助格式化输入和输出。
第2步 – 创建一个TreeNode结构，其值为int类型，left_val和right_val为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结构，其值为int类型，left_val和right_val为TreeNode类型。
第3步– 创建一个函数pre_order_traversal，在该函数中，如果根节点为空，则返回。
第4步– 在下一步中，从根节点向上创建一个堆栈。
第5步– 通过检查堆栈的长度是否大于0来运行一个循环，只要堆栈仍然是满的，就重复以下动作—-。

a. 从堆栈的顶部删除节点，并将其分配给一个名为curr的变量。

b. 打印当前值。

第6步 – 在主函数中，将调用该函数，并使用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()
}