跟着动画学 Go 数据结构之二叉树

树可以有许多不同的形状，并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同。 而在其中最常用的树之一是二叉树。 二叉树是一棵树，其中每个节点最多可以有两个孩子。 一个孩子被识别为左孩子，另一个孩子被识别为右孩子。

二叉树是一种数据结构，在每个节点下面最多存在两个其他节点。即一个节点要么连接至一个、两个节点或不连接其他节点。

树形结构的深度（也被称作高度）则被定义为根节点为根节点至某个节点间的最长路径，而节点的深度则表示当当前节点至树根节点间的边数。二叉树有许多不同的形状和大小。 形状取决于节点的数量和节点的链接方式。 下图说明了由九个节点组成的二叉树的三种不同形状：

Go 语言实现二叉树

1. 定义二叉树的结构

package main

import (
  "fmt"
  "math/rand"
  "time"
)

type Tree struct {
  Left *Tree
  Value int
  Right *Tree
}

1. 二叉树遍历

func traverse(t *Tree) {
  if t == nil {
    return
  }
  
  traverse(t.Left)
  fmt.Print(t.Value, " ")
  traverse(t.Right)
}

traverse() 函数通过递归方式访问二叉树的全部节点。

1. 创建二叉树

利用 create() 函数利用随机整数填写二叉树：

func create(n int) *Tree {
  var t *Tree
  rand.Seed(time.Now().Unix())
  for i := 0; i < 2 * n; i++ {
    temp := rand.Intn(n * 2)
    t = insert(t, temp)
  }
  return t
}

1. 插入值

insert 函数：

• 第一个 if 语句在插入时如果是空树，就把插入的节点设置为根节点，并创建为 &Tree{nil, v, nil}

• 第二个 if 语句确定插入值是否已在二叉树中存在。若存在，函数将直接返回且不执行任何操作

• 第三个 if 语句检查插入的值位于当前节点的左孩子节点还是右孩子节点，并插入到相应的位置。

func insert(t *Tree, v int) *Tree {
  if t == nil {
    return &Tree{nil, v, nil}
  }
  if v == t.Value {
    return t
  }
  if v < t.Value {
    t.Left = insert(t.Left, v)
    return t
  }
  
  t.Right = insert(t.Right, v)
  return t
}

测试

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

func traverse(t *Tree) {
	if t == nil {
		return
	}

	traverse(t.Left)
	fmt.Print(t.Value, " ")
	traverse(t.Right)
}

func create(n int) *Tree {
	var t *Tree
	rand.Seed(time.Now().Unix())
	for i := 0; i < 2*n; i++ {
		temp := rand.Intn(n * 2)
		t = insert(t, temp)
	}
	return t
}

func insert(t *Tree, v int) *Tree {
	if t == nil {
		return &Tree{nil, v, nil}
	}
	if v == t.Value {
		return t
	}
	if v < t.Value {
		t.Left = insert(t.Left, v)
		return t
	}

	t.Right = insert(t.Right, v)
	return t
}

func main() {

	tree := create(10)

	fmt.Println("The value of the root of the tree is", tree.Value)

	traverse(tree)

	fmt.Println()

	tree = insert(tree, -10)
	tree = insert(tree, -2)

	traverse(tree)
	fmt.Println()

	fmt.Println("The value of the boot of the the tree is", tree.Value)
}

运行结果：

The value of the root of the tree is 18
0 1 4 5 6 8 9 10 12 14 15 18 19 
-10 -2 0 1 4 5 6 8 9 10 12 14 15 18 19 
The value of the boot of the the tree is 18