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步– 创建一个值为10的根节点，两个值为20和30的子节点，并在主函数中将它们分别指定为根节点的左和右子节点。

• 第4步– 为了使值为20的节点的左和右的子节点，分别创建两个值为40和50的新节点。

• 第5步– 创建函数preorder，以预排序方式遍历二叉树。这个函数打印出节点的值作为参数。

• 第6步 – 如果有当前节点的左和右子节点，预排序函数就会在这些节点上递归调用自己。在这种方法中，该函数对二叉树中的每个节点进行预排序访问。

• 第7步 – 为了完成二叉树的预排序遍历，在根节点上执行预排序函数。按照访问的顺序打印所访问的节点的值。

• 第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，数值为20的节点的左边子节点的数值为10。值为60的节点的右子的值为70，而值为60的节点的左子的值为50。然后，二叉树的无序遍历被打印出来。

算法

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

• 第2步 – 建立一个结构 Node用来表示二叉树中的一个节点，有三个字段 – value, left_val, and right_val。Value存储节点的值，而left_val和right_val分别存储指向其左、右子节点的指针。

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

• 第4步– 为了使数值为20的节点的左和右子节点，分别创建两个数值为10和30的新节点。

• 第5步– 为了使值为60的节点的左和右的子节点，分别再创建两个值为50和70的节点。

• 第6步– 创建函数in Order，按顺序遍历二叉树。这个函数的参数是一个节点。

• 第7步– 如果当前节点有一个左边的子节点，in Order函数首先在该节点上递归调用自己。

• 第8步 – 然后打印当前节点的值。

• 第9步- -最后，如果当前节点有一个右边的子节点，该方法将递归调用自己。二叉树的所有节点都是由函数以这种方式依次访问的。

• 第10步 – 要开始二叉树的顺序遍历，在根节点上调用in Order函数。按照访问的顺序打印所访问的节点的值。

例子

在这个例子中，我们将打印按顺序遍历的结果。

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

结论

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