树 Tree

树是有限结点组成一个具有层次关系的集合。

开始写代码前，先复习一遍基本概念：

名词术语

结点 Node

也有写作“节点”，组成树的集合中的“元素”。

根结点 Root

没有前驱的结点叫做根结点

结点的度 Node degree

一个结点含有子树的个数

树的度 Tree degree

所有结点的度最大的那一个叫做树的度

叶子结点 Leaf

度为0的结点

结点的层次 Level

根为第一层，根的子节点为第二层，依次往下推

深度 Depth

树的总层数，就是高度树的高度Height

二叉树 Binary Tree

一种特殊的树，是结点的一个有限集合，且所有结点最多有2个子结点，即度只能是0,1,2。

满二叉树 Full Binary Tree

除叶子结点外，每一层上的所有结点都有两个子结点二叉树。它的每一个层次的结点数目都达到了最大值。

结点总数M 和总层数N 满足： M = 2^N - 1

每层结点数m 和层数n 满足： m = 2^(n-1)

完全二叉树 Complete Binary Tree

二叉树的叶节点只出现在最下层和次下层，并且最下层的结点都集中在该层的最左边。

性质

(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；

(2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，其所有的叶结点数为：N0，而度为2的所有结点的数量为：N2，则：N0=N2+1，请观察上图；

(4) 具有n个结点的完全二叉树的深度为int（log2n）+1

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I<>1，则其父结点的编号为I/2；

如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；

如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6) 给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

二叉树的创建

结点

数据域 Data，使用 interface{} 好处是可以添加任意类型的数据结点

左、右子树结点指针 Lchild, Rchild

type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}

二叉树

1. type biTree struct {
2.  root *btNode
3. }

创建与访问

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func main() {
  var tree *biTree
  var node1, node2, node3, node4 *btNode
  tree = new(biTree)
  node1 = &btNode{Data: 1}
  node2 = &btNode{Data: 2}
  node3 = &btNode{Data: 3}
  node4 = &btNode{Data: 4}
  tree.root = node1
  node1.Lchild = node2
  node1.Rchild = node3
  node2.Lchild = node4
  fmt.Println(tree.root.Data)
  fmt.Println(tree.root.Lchild.Data)
  fmt.Println(tree.root.Rchild.Data)
  fmt.Println(tree.root.Lchild.Lchild.Data)
}
/*
1
2
3
4
*/

用数组批量创建结点

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func NewTree() *biTree {
  return &biTree{}
}
func newTreeNode(data interface{}) *btNode {
  return &btNode{
    Data:   data,
    Lchild: nil,
    Rchild: nil,
  }
}
func main() {
  list := []interface{}{1, 2, 3, 4, 5, 6}
  node := []*btNode{}
  tree := NewTree()
  for _, data := range list {
    node = append(node, newTreeNode(data))
  }
  tree.root = node[0]
  tree.root.Lchild = node[1]
  tree.root.Rchild = node[2]
  tree.root.Lchild.Lchild = node[3]
  tree.root.Lchild.Rchild = node[4]
  tree.root.Rchild.Lchild = node[5]
  fmt.Println(tree.root.Data)
  fmt.Println(tree.root.Lchild.Data)
  fmt.Println(tree.root.Rchild.Data)
  fmt.Println(tree.root.Lchild.Lchild.Data)
  fmt.Println(tree.root.Lchild.Rchild.Data)
  fmt.Println(tree.root.Rchild.Lchild.Data)
}
/*
1
2
3
4
5
6
*/

追加结点

从上到下逐层且每一层从左到右访问二叉树，遇到首个空结点时就添加一结点。

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func NewTree() *biTree {
  return &biTree{}
}
func newTreeNode(data interface{}) *btNode {
  return &btNode{
    Data:   data,
    Lchild: nil,
    Rchild: nil,
  }
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil { //空树则创建一个根结点
    bt.root = newTreeNode(data)
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = newTreeNode(data)
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = newTreeNode(data)
      break
    }
  }
}
func main() {
  tree := &biTree{}
  list := []interface{}{1, 2, 3, 4, 5, 6}
  for _, data := range list {
    tree.appendNode(data)
  }
  fmt.Println(tree.root.Data)
  fmt.Println(tree.root.Lchild.Data)
  fmt.Println(tree.root.Rchild.Data)
  fmt.Println(tree.root.Lchild.Lchild.Data)
  fmt.Println(tree.root.Lchild.Rchild.Data)
  fmt.Println(tree.root.Rchild.Lchild.Data)
  tree.appendNode(0)
  fmt.Println(tree.root.Rchild.Rchild.Data)
}
/*
1
2
3
4
5
6
0
*/

追加结点时的访问方法称为“层序”，层序访问整个二叉树只要把代码中追加结点的语句换成打印所有结点的数据域，即完成了二叉树的“层序遍历”：

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func NewTree() *biTree {
  return &biTree{}
}
func newTreeNode(data interface{}) *btNode {
  return &btNode{
    Data:   data,
    Lchild: nil,
    Rchild: nil,
  }
}
func levelorderPrint(bt *biTree) {
  cur := bt.root
  if cur == nil {
    fmt.Print("Empty Binary Tree")
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    fmt.Print(cur.Data, " ")
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    }
  }
  fmt.Println()
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil {
    bt.root = newTreeNode(data)
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = newTreeNode(data)
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = newTreeNode(data)
      break
    }
  }
}
func main() {
  tree := &biTree{}
  list := []interface{}{1, 2, 3, 4, 5, 6}
  for _, data := range list {
    tree.appendNode(data)
  }
  levelorderPrint(tree)
  tree.appendNode(0)
  levelorderPrint(tree)
}
/*
1 2 3 4 5 6 
1 2 3 4 5 6 0 
*/

二叉树的遍历

层序遍历

自上而下，自左至右逐层访问树的结点的过程就是层序遍历

上面已写过打印版的层序遍历函数，稍作修改让它变成一个二叉树方法，并返回一个数组。

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func (bt *biTree) levelorder() []interface{} {
  var list []interface{}
  cur := bt.root
  if cur == nil {
    return list
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    list = append(list, cur.Data)
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    }
  }
  return list
}
func createTree(list []interface{}) *biTree {
  btree := &biTree{}
  if len(list) > 0 {
    btree.root = &btNode{Data: list[0]}
    for _, data := range list[1:] {
      btree.appendNode(data)
    }
  }
  return btree
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil {
    bt = &biTree{}
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = &btNode{Data: data}
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = &btNode{Data: data}
      break
    }
  }
}
func main() {
  list := []interface{}{1, 2, 3, 4, 5, 6}
  tree := createTree(list)
  fmt.Println(tree.levelorder())
  tree.appendNode(0)
  fmt.Println(tree.levelorder())
}
/*
[1 2 3 4 5 6]
[1 2 3 4 5 6 0]
*/

先序遍历

先遍历根节点，再遍历左节点，最后遍历右节点

中序遍历

先遍历左节点，再遍历根节点，最后遍历右节点

后序遍历

先遍历左节点，再遍历右节点，最后遍历根节点

三种遍历的递归打印版：

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func preorderPrint(bt *btNode) {
  if bt == nil {
    return
  }
  fmt.Print(bt.Data, " ")
  preorderPrint(bt.Lchild)
  preorderPrint(bt.Rchild)
}
func inorderPrint(bt *btNode) {
  if bt == nil {
    return
  }
  inorderPrint(bt.Lchild)
  fmt.Print(bt.Data, " ")
  inorderPrint(bt.Rchild)
}
func postorderPrint(bt *btNode) {
  if bt != nil { //这样写就不用return语句
    postorderPrint(bt.Lchild)
    postorderPrint(bt.Rchild)
    fmt.Print(bt.Data, " ")
  }
}
func createTree(list []interface{}) *biTree {
  btree := &biTree{}
  if len(list) > 0 {
    btree.root = &btNode{Data: list[0]}
    for _, data := range list[1:] {
      btree.appendNode(data)
    }
  }
  return btree
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil {
    bt = &biTree{}
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = &btNode{Data: data}
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = &btNode{Data: data}
      break
    }
  }
}
func main() {
  list := []interface{}{1, 2, 3, 4, 5, 6, 7, 8}
  tree := createTree(list)
  preorderPrint(tree.root)
  fmt.Println()
  inorderPrint(tree.root)
  fmt.Println()
  postorderPrint(tree.root)
  fmt.Println()
}
/*
1 2 4 8 5 3 6 7 
8 4 2 5 1 6 3 7 
8 4 5 2 6 7 3 1 
*/

三个函数核心代码次序的对比：

先序：“根左右”

fmt.Print(bt.Data, " ")

preorderPrint(bt.Lchild)

preorderPrint(bt.Rchild)

中序：“左根右”

inorderPrint(bt.Lchild)

fmt.Print(bt.Data, " ")

inorderPrint(bt.Rchild)

后序：“左右根”

postorderPrint(bt.Lchild)

postorderPrint(bt.Rchild)

fmt.Print(bt.Data, " ")

递归非打印版：

在打印版的基础上稍作修改，返回一个数组

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func (bt *btNode) preorder() []interface{} {
  var res []interface{} //or: res := make([]interface{}, 0)
  if bt != nil {
    res = append(res, bt.Data)
    res = append(res, bt.Lchild.preorder()...)
    res = append(res, bt.Rchild.preorder()...)
  }
  return res
}
func (bt *btNode) inorder() []interface{} {
  var res []interface{}
  if bt != nil {
    res = append(res, bt.Lchild.inorder()...)
    res = append(res, bt.Data)
    res = append(res, bt.Rchild.inorder()...)
  }
  return res
}
func (bt *btNode) postorder() []interface{} {
  var res []interface{}
  if bt != nil {
    res = append(res, bt.Lchild.postorder()...)
    res = append(res, bt.Rchild.postorder()...)
    res = append(res, bt.Data)
  }
  return res
}
func createTree(list []interface{}) *biTree {
  btree := &biTree{}
  if len(list) > 0 {
    btree.root = &btNode{Data: list[0]}
    for _, data := range list[1:] {
      btree.appendNode(data)
    }
  }
  return btree
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil {
    bt = &biTree{}
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = &btNode{Data: data}
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = &btNode{Data: data}
      break
    }
  }
}
func main() {
  list := []interface{}{1, 2, 3, 4, 5, 6, 7, 8}
  tree := createTree(list)
  fmt.Println(tree.root.preorder())
  fmt.Println(tree.root.inorder())
  fmt.Println(tree.root.postorder())
}
/*
[1 2 4 8 5 3 6 7]
[8 4 2 5 1 6 3 7]
[8 4 5 2 6 7 3 1]
*/

非递归方法：

递推法可以写成二叉树的方法，不像递归法要反复调用只能写成结点的方法。

package main
import "fmt"
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  root *btNode
}
func (bt *biTree) preOrder() []interface{} {
  var res []interface{}
  p := bt.root
  Stack := make([]*btNode, 0)
  for p != nil || len(Stack) > 0 {
    for p != nil {
      res = append(res, p.Data)
      Stack = append(Stack, p)
      p = p.Lchild
    }
    if len(Stack) > 0 {
      p = Stack[len(Stack)-1]
      Stack = Stack[:len(Stack)-1]
      p = p.Rchild
    }
  }
  return res
}
func (bt *biTree) inOrder() []interface{} {
  var res []interface{}
  p := bt.root
  Stack := make([]*btNode, 0)
  for p != nil || len(Stack) > 0 {
    for p != nil {
      Stack = append(Stack, p)
      p = p.Lchild
    }
    if len(Stack) > 0 {
      p = Stack[len(Stack)-1]
      res = append(res, p.Data)
      Stack = Stack[:len(Stack)-1]
      p = p.Rchild
    }
  }
  return res
}
func (bt *biTree) postOrder() []interface{} {
  var res []interface{}
  var cur, pre *btNode
  Stack := make([]*btNode, 0)
  Stack = append(Stack, bt.root)
  for len(Stack) > 0 {
    cur = Stack[len(Stack)-1]
    if cur.Lchild == nil && cur.Rchild == nil ||
      pre != nil && (pre == cur.Lchild || pre == cur.Rchild) {
      res = append(res, cur.Data)
      Stack = Stack[:len(Stack)-1]
      pre = cur
    } else {
      if cur.Rchild != nil {
        Stack = append(Stack, cur.Rchild)
      }
      if cur.Lchild != nil {
        Stack = append(Stack, cur.Lchild)
      }
    }
  }
  return res
}
func createTree(list []interface{}) *biTree {
  btree := &biTree{}
  if len(list) > 0 {
    btree.root = &btNode{Data: list[0]}
    for _, data := range list[1:] {
      btree.appendNode(data)
    }
  }
  return btree
}
func (bt *biTree) appendNode(data interface{}) {
  cur := bt.root
  if cur == nil {
    bt = &biTree{}
    return
  }
  Queue := []*btNode{cur}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    } else {
      cur.Lchild = &btNode{Data: data}
      return
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    } else {
      cur.Rchild = &btNode{Data: data}
      break
    }
  }
}
func main() {
  list := []interface{}{1, 2, 3, 4, 5, 6, 7, 8}
  tree := createTree(list)
  fmt.Println(tree.preOrder())
  fmt.Println(tree.inOrder())
  fmt.Println(tree.postOrder())
}
/*
[1 2 4 8 5 3 6 7]
[8 4 2 5 1 6 3 7]
[8 4 5 2 6 7 3 1]
*/

更多内容请见下集分解......

go语言｜数据结构：二叉树（1）创建与遍历方法

树 Tree

名词术语

结点 Node

根结点 Root

结点的度 Node degree

树的度 Tree degree

叶子结点 Leaf

结点的层次 Level

深度 Depth

二叉树 Binary Tree

满二叉树 Full Binary Tree

完全二叉树 Complete Binary Tree

性质

二叉树的创建

结点

二叉树

创建与访问

用数组批量创建结点

二叉树的遍历

层序遍历

先序遍历

中序遍历

后序遍历

热门文章

最新文章

相关课程

相关电子书