Golang程序 无序树的遍历

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

语法

func make ([] type, size, capacity)

Go语言中的make函数是用来创建数组/映射的，它接受要创建的变量类型、其大小和容量作为参数。

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

append函数用于向一个数组片断添加值。它需要一些参数。第一个参数是我们希望添加的数组，后面是要添加的值。然后，该函数返回包含所有值的数组的最终片断。

算法

• 第1步 – 创建一个包main，并在程序中声明fmt(格式包)和strings包，其中main产生可执行代码，fmt帮助格式化输入和输出。

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

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

• 第4步 – 如果根节点为零，inorder_traversal函数应该返回一个空片。

• 第 5步– 如果根节点不是空的，就把对左边子节点的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]

结论

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