Go语言实现二叉树数据结构

在Go语言中，二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。Go语言内置的数据结构和操作，例如结构体和指针，可以用来创建二叉树。树的节点可以被视为具有字段的结构体，这些字段用于存储每个节点的值以及指向任何左子节点或右子节点的指针。有三种类型的树遍历——前序遍历、中序遍历和后序遍历。我们将使用两种方法来实现二叉树数据结构。第一种方法使用前序遍历，第二种方法使用中序遍历。

方法一：使用前序遍历

此方法生成一个二叉树，它有两个子节点，值分别为20和30，以及一个值为10的根节点。值为20的节点的右子节点的值为50，而值为20的节点的左子节点的值为40。然后打印二叉树的前序遍历。让我们通过代码和算法来理解这个概念。

算法

  • 步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包），其中main生成可执行代码，fmt帮助格式化输入和输出。

  • 步骤2 − 建立一个名为Node的结构体，用于表示二叉树中的一个节点，它具有三个字段：value、left_val和right_val。Value存储节点的值，而left_val和right_val分别存储指向其左子节点和右子节点的指针。

  • 步骤3 − 在main函数中，创建一个值为10的根节点，两个值为20和30的子节点，并将它们分别指定为根节点的左子节点和右子节点。

  • 步骤4 − 为值为20的节点创建两个新的子节点，值分别为40和50，作为其左子节点和右子节点。

  • 步骤5 − 创建preorder函数，以进行前序遍历二叉树。此函数以节点作为参数，打印节点的值。

  • 步骤6 − 如果当前节点有左子节点和右子节点，则preorder函数会递归地调用自身来处理这些节点。通过这种方式，函数会对二叉树中的每个节点进行前序访问。

  • 步骤7 − 要完成二叉树的前序遍历，请在根节点上执行preorder函数。打印访问的节点的值，按访问顺序打印。

  • 步骤8 − 使用fmt.Println()函数执行打印语句，其中ln表示换行。

示例

在这个例子中，我们将打印前序遍历。

package main
import "fmt"

type Node struct {
   value     int
   left_val  *Node  //create and left_val and right_val node
   right_val *Node
}

func main() {
   root := &Node{value: 10} //assign the linked list required elements
   root.left_val = &Node{value: 20}
   root.right_val = &Node{value: 30}
   root.left_val.left_val = &Node{value: 40}
   root.left_val.right_val = &Node{value: 50}
   
   fmt.Println("The pre-order traversal is given as:")
   preOrder(root)
}

func preOrder(node *Node) {
   if node == nil {
      return
   }
   fmt.Println(node.value)
   preOrder(node.left_val)
   preOrder(node.right_val)
}

输出

The pre-order traversal is given as:
10
20
40
50
30

方法二：使用中序遍历

此方法生成一个二叉树，它有两个子节点，值分别为2和6，以及一个值为40的根节点。值为20的节点的右子节点的值为30，而值为20的节点的左子节点的值为10。值为60的节点的右子节点的值为70，而值为60的节点的左子节点的值为50。然后打印二叉树的中序遍历。

算法

  • 步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包），其中main生成可执行代码，fmt帮助格式化输入和输出。

  • 步骤2 − 建立一个名为Node的结构体，用于表示二叉树中的一个节点，它具有三个字段：value、left_val和right_val。Value存储节点的值，而left_val和right_val分别存储指向其左子节点和右子节点的指针。

  • 步骤3 − 在main函数中，创建一个值为40的根节点，两个值为20和60的子节点，并将它们分别指定为根节点的左子节点和右子节点。

  • 步骤4 − 为值为20的节点创建两个新的子节点，值分别为10和30，作为其左子节点和右子节点。

  • 步骤5 − 为值为60的节点创建另外两个新的子节点，值分别为50和70，作为其左子节点和右子节点。

  • 步骤6 − 创建inOrder函数，以进行中序遍历二叉树。此函数以节点作为参数。

  • 步骤7 − 如果当前节点有左子节点，inOrder函数首先递归地调用自身来处理该节点。

  • 步骤8 − 然后打印当前节点的值。

  • 步骤9 − 最后，如果当前节点有右子节点，则该方法递归地调用自身。通过这种方式，该函数会依次访问二叉树中的所有节点。

  • 步骤10 − 要开始二叉树的中序遍历，请在根节点上调用inOrder函数。打印访问的节点的值，按访问顺序打印。

示例

在这个例子中，我们将打印中序遍历。

package main
import "fmt"

type Node struct {
   value     int
   left_val  *Node  //create left_val and right_val elements 
   right_val *Node
}

func main() {
   root := &Node{value: 40} //fill the linked list with the elements
   root.left_val = &Node{value: 20}
   root.right_val = &Node{value: 60}
   root.left_val.left_val = &Node{value: 10}
   root.left_val.right_val = &Node{value: 30}
   root.right_val.left_val = &Node{value: 50}
   root.right_val.right_val = &Node{value: 70}
   
   fmt.Println("The In-order traversal created here is:")
   inOrder(root)
}

func inOrder(node *Node) {
   if node == nil {
      return
   }
   inOrder(node.left_val)
   fmt.Println(node.value)
   inOrder(node.right_val)
}

输出

The In-order traversal created here is:
10
20
30
40
50
60
70

结论

我们使用两种方法执行了实现二叉树数据结构的程序。在第一个例子中，我们打印了二叉树的前序遍历，在第二个例子中，我们打印了二叉树的中序遍历。

更新于：2023年2月22日

2K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告