Golang 实现二叉树数据结构

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

方法1：使用前序遍历

该方法生成一个带有值为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：使用中序遍历

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

步骤

• 步骤1 - 在程序中创建一个main包并声明fmt（格式化包）包。主函数产生可执行代码，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

结论

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