go语言|数据结构:二叉树(1)创建与遍历方法

简介: go语言|数据结构:二叉树(1)创建与遍历方法

树 Tree


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


image.png


开始写代码前,先复习一遍基本概念:


名词术语


结点 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

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

aa9b205d2a424e1081a1b629fc5a1d6f.png


性质


(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 
*/



二叉树的遍历


层序遍历

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


20210725085538742.png


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

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]
*/


先序遍历

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


20210725082352964.png



中序遍历

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

20210725083710482.png



后序遍历

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


20210725084708331.png


三种遍历的递归打印版:

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]
*/

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


目录
相关文章
|
3月前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
286 86
|
5月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中,企业面临员工泄密风险。本文探讨使用跳表(Skip List)数据结构优化泄密防护系统,提升敏感数据监测效率。跳表以其高效的动态数据处理能力,为企业信息安全管理提供了可靠技术支持。
132 0
|
7月前
|
存储 安全 Go
Map的遍历与判断键是否存在-《Go语言实战指南》
本文介绍了 Go 语言中对 `map` 的常见操作,包括遍历所有项和判断键是否存在。通过 `for range` 可以遍历 `map` 的键值对、仅键或仅值(需忽略键)。注意,`map` 遍历顺序是随机的。判断键是否存在时,使用双赋值语法 `value, ok := map[key]`,其中 `ok` 表示键是否存在。直接访问不存在的键会返回类型的零值,可能导致逻辑错误。掌握这些机制可更安全高效地处理键值对数据。
|
8月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
385 10
|
9月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
288 10
 算法系列之数据结构-二叉树
|
11月前
|
存储 安全 Go
Go语言中的map数据结构是如何实现的?
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构,支持快速查找、插入和删除操作。其原理涉及哈希函数、桶(Bucket)、动态扩容和哈希冲突处理等关键机制,平均时间复杂度为 O(1)。为了确保线程安全,Go 提供了 `sync.Map` 类型,通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能,以及如何使用 `sync.Map` 进行线程安全的操作。
301 9
|
11月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
318 12
|
11月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
192 10
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
291 59