AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

go语言｜数据结构：二叉树（3）拷贝、镜像和对称

2023-05-25 129
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： go语言｜数据结构：二叉树（3）拷贝、镜像和对称

image.png




拷贝副本


复制一个二叉树副本，广度优先遍历同时设置两个队列，一个遍历一个复制创建。

func Copy(bt *biTree) *biTree {
  root := bt.Root
  if root == nil {
    return &biTree{}
  }
  node := &btNode{Data: root.Data}
  Queue1, Queue2 := []*btNode{root}, []*btNode{node}
  for len(Queue1) > 0 {
    p1, p2 := Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      Node := &btNode{Data: p1.Lchild.Data}
      p2.Lchild = Node
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, Node)
    }
    if p1.Rchild != nil {
      Node := &btNode{Data: p1.Rchild.Data}
      p2.Rchild = Node
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, Node)
    }
  }
  return &biTree{Root: node}
}




相同二叉树


递归法

func Equal(bt1, bt2 *btNode) bool {
  if bt1 == nil && bt2 == nil {
    return true
  } else if bt1 == nil || bt2 == nil {
    return false
  }
  if bt1.Data != bt2.Data {
    return false
  }
  return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
func (bt *biTree) Equal(bt2 *biTree) bool {
  return Equal(bt.Root, bt2.Root)
}



BFS

过程与复制副本类似，设置两个队列，同时遍历只要有一处不同即返回不相同。

func (bt *biTree) SameAs(bt2 *biTree) bool {
  root1, root2 := bt.Root, bt2.Root
  if root1 == nil && root2 == nil {
    return true
  } else if root1 == nil || root2 == nil {
    return false
  }
  Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
  p1, p2 := Queue1[0], Queue2[0]
  for len(Queue1) > 0 && len(Queue2) > 0 {
    p1, p2 = Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, p2.Lchild)
    } else if p2.Lchild != nil {
      if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, p2.Lchild)
    }
    if p1.Rchild != nil {
      if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, p2.Rchild)
    } else if p2.Rchild != nil {
      if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, p2.Rchild)
    }
  }
  return true
}



9c495ad7216d4b29b03b6019caa91e1c.png


镜像二叉树

生成一棵二叉树的镜像：



递归法

func (bt *btNode) InvertNodes() {
  if bt != nil {
    bt.Lchild.InvertNodes()
    bt.Rchild.InvertNodes()
    bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
  }
}
func (bt *biTree) Mirror() {
  bt.Root.InvertNodes()
}


BFS

func Mirror(bt *biTree) *biTree {
  root := bt.Root
  if root == nil {
    return &biTree{}
  }
  node := &btNode{Data: root.Data}
  Queue1, Queue2 := []*btNode{root}, []*btNode{node}
  for len(Queue1) > 0 {
    p1, p2 := Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      Node := &btNode{Data: p1.Lchild.Data}
      p2.Rchild = Node
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, Node)
    }
    if p1.Rchild != nil {
      Node := &btNode{Data: p1.Rchild.Data}
      p2.Lchild = Node
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, Node)
    }
  }
  return &biTree{Root: node}
}


对称二叉树


方法一：判断左子树与右子树的反转是否相等

1. func (bt *biTree) IsSymmetry() bool {
2.  return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
3. }


方法二：判断自身与镜像是否相同

1. func (bt *biTree) IsSymmetry2() bool {
2.  bt2 := Mirror(bt)
3.  return bt.SameAs(bt2)
4. }




判断二棵二叉树是否互为镜像


方法一：生成其中一棵的镜像，判断镜像与另一棵是否相同

1. func (bt *biTree) IsMirror(bt2 *biTree) bool {
2.  return bt.SameAs(Mirror(bt2))
3. }



方法二：分别以此二棵树作左右子树生成一棵新树，判断新树是否左右对称

 

func (bt *biTree) IsMirror(bt2 *biTree) bool {
  root := &biTree{&btNode{1, bt.Root, bt2.Root}}
  return root.IsSymmetry()
}




包biTree函数汇总

至此，《数据结构：二叉树》系列（1~3）已累积了从创建、遍历等功能的20多个函数和方法，汇总如下：

/* The Package biTree
 * https://hannyang.blog.csdn.net/article/details/126556548
 *
 * based on Go program by Hann Yang,
 * modified on 2022/8/31.
 */
package biTree
type btNode struct {
  Data   interface{}
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  Root *btNode
}
func Build(data interface{}) *biTree {
  var list []interface{}
  if data == nil {
    return &biTree{}
  }
  switch data.(type) {
  case []interface{}:
    list = append(list, data.([]interface{})...)
  default:
    list = append(list, data)
  }
  if len(list) == 0 {
    return &biTree{}
  }
  node := &btNode{Data: list[0]}
  list = list[1:]
  Queue := []*btNode{node}
  for len(list) > 0 {
    if len(Queue) == 0 {
      //panic("Given array can not build binary tree.")
      return &biTree{Root: node}
    }
    cur := Queue[0]
    val := list[0]
    Queue = Queue[1:]
    if val != nil {
      cur.Lchild = &btNode{Data: val}
      if cur.Lchild != nil {
        Queue = append(Queue, cur.Lchild)
      }
    }
    list = list[1:]
    if len(list) > 0 {
      val := list[0]
      if val != nil {
        cur.Rchild = &btNode{Data: val}
        if cur.Rchild != nil {
          Queue = append(Queue, cur.Rchild)
        }
      }
      list = list[1:]
    }
  }
  return &biTree{Root: node}
}
func Create(data interface{}) *biTree {
  var list []interface{}
  btree := &biTree{}
  switch data.(type) {
  case []interface{}:
    list = append(list, data.([]interface{})...)
  default:
    list = append(list, data)
  }
  if len(list) > 0 {
    btree.Root = &btNode{Data: list[0]}
    for _, data := range list[1:] {
      btree.AppendNode(data)
    }
  }
  return btree
}
func (bt *biTree) Append(data interface{}) {
  var list []interface{}
  switch data.(type) {
  case []interface{}:
    list = append(list, data.([]interface{})...)
  default:
    list = append(list, data)
  }
  if len(list) > 0 {
    for _, data := range list {
      bt.AppendNode(data)
    }
  }
}
func (bt *biTree) AppendNode(data interface{}) {
  root := bt.Root
  if root == nil {
    bt.Root = &btNode{Data: data}
    return
  }
  Queue := []*btNode{root}
  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 (bt *biTree) Levelorder() []interface{} { //BFS
  var res []interface{}
  root := bt.Root
  if root == nil {
    return res
  }
  Queue := []*btNode{root}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    res = append(res, cur.Data)
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    }
  }
  return res
}
func (bt *biTree) BForder2D() [][]interface{} {
  var res [][]interface{}
  root := bt.Root
  if root == nil {
    return res
  }
  Queue := []*btNode{root}
  for len(Queue) > 0 {
    Nodes := []interface{}{}
    Levels := len(Queue)
    for Levels > 0 {
      cur := Queue[0]
      Queue = Queue[1:]
      Nodes = append(Nodes, cur.Data)
      Levels--
      if cur.Lchild != nil {
        Queue = append(Queue, cur.Lchild)
      }
      if cur.Rchild != nil {
        Queue = append(Queue, cur.Rchild)
      }
    }
    res = append(res, Nodes)
  }
  return res
}
func (bt *biTree) Preorder() []interface{} {
  var res []interface{}
  cur := bt.Root
  Stack := []*btNode{}
  for cur != nil || len(Stack) > 0 {
    for cur != nil {
      res = append(res, cur.Data)
      Stack = append(Stack, cur)
      cur = cur.Lchild
    }
    if len(Stack) > 0 {
      cur = Stack[len(Stack)-1]
      Stack = Stack[:len(Stack)-1]
      cur = cur.Rchild
    }
  }
  return res
}
func (bt *biTree) Inorder() []interface{} {
  var res []interface{}
  cur := bt.Root
  Stack := []*btNode{}
  for cur != nil || len(Stack) > 0 {
    for cur != nil {
      Stack = append(Stack, cur)
      cur = cur.Lchild
    }
    if len(Stack) > 0 {
      cur = Stack[len(Stack)-1]
      res = append(res, cur.Data)
      Stack = Stack[:len(Stack)-1]
      cur = cur.Rchild
    }
  }
  return res
}
func (bt *biTree) Postorder() []interface{} {
  var res []interface{}
  if bt.Root == nil {
    return res
  }
  cur, pre := &btNode{}, &btNode{}
  Stack := []*btNode{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 (bt *btNode) MaxDepth() int {
  if bt == nil {
    return 0
  }
  Lmax := bt.Lchild.MaxDepth()
  Rmax := bt.Rchild.MaxDepth()
  return 1 + Max(Lmax, Rmax)
}
func (bt *btNode) MinDepth() int {
  if bt == nil {
    return 0
  }
  Lmin := bt.Lchild.MinDepth()
  Rmin := bt.Rchild.MinDepth()
  return 1 + Min(Lmin, Rmin)
}
func (bt *biTree) Depth() int { //BFS
  res := 0
  root := bt.Root
  if root == nil {
    return res
  }
  Queue := []*btNode{root}
  for len(Queue) > 0 {
    Levels := len(Queue)
    for Levels > 0 {
      cur := Queue[0]
      Queue = Queue[1:]
      if cur.Lchild != nil {
        Queue = append(Queue, cur.Lchild)
      }
      if cur.Rchild != nil {
        Queue = append(Queue, cur.Rchild)
      }
      Levels--
    }
    res++
  }
  return res
}
func (bt *btNode) Degree() int {
  res := 0
  if bt.Lchild != nil {
    res++
  }
  if bt.Rchild != nil {
    res++
  }
  return res
}
func (bt *biTree) LeafNodeBFS() []interface{} {
  var res []interface{}
  root := bt.Root
  if root == nil {
    return res
  }
  Queue := []*btNode{root}
  for len(Queue) > 0 {
    cur := Queue[0]
    Queue = Queue[1:]
    //if cur.Lchild == nil && cur.Rchild == nil {
    if cur.Degree() == 0 {
      res = append(res, cur.Data)
    }
    if cur.Lchild != nil {
      Queue = append(Queue, cur.Lchild)
    }
    if cur.Rchild != nil {
      Queue = append(Queue, cur.Rchild)
    }
  }
  return res
}
func (bt *biTree) LeafNodeDFS() []interface{} {
  var res []interface{}
  cur := bt.Root
  Stack := []*btNode{}
  for cur != nil || len(Stack) > 0 {
    for cur != nil {
      //if cur.Lchild == nil && cur.Rchild == nil {
      if cur.Degree() == 0 {
        res = append(res, cur.Data)
      }
      Stack = append(Stack, cur)
      cur = cur.Lchild
    }
    if len(Stack) > 0 {
      cur = Stack[len(Stack)-1]
      Stack = Stack[:len(Stack)-1]
      cur = cur.Rchild
    }
  }
  return res
}
func (bt *btNode) InvertNodes() *btNode {
  if bt != nil {
    bt.Lchild.InvertNodes()
    bt.Rchild.InvertNodes()
    bt.Lchild, bt.Rchild = bt.Rchild, bt.Lchild
  }
  return bt
}
func (bt *biTree) Mirror() {
  bt.Root.InvertNodes()
}
func Copy(bt *biTree) *biTree {
  root := bt.Root
  if root == nil {
    return &biTree{}
  }
  node := &btNode{Data: root.Data}
  Queue1, Queue2 := []*btNode{root}, []*btNode{node}
  for len(Queue1) > 0 {
    p1, p2 := Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      Node := &btNode{Data: p1.Lchild.Data}
      p2.Lchild = Node
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, Node)
    }
    if p1.Rchild != nil {
      Node := &btNode{Data: p1.Rchild.Data}
      p2.Rchild = Node
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, Node)
    }
  }
  return &biTree{Root: node}
}
func Mirror(bt *biTree) *biTree {
  root := bt.Root
  if root == nil {
    return &biTree{}
  }
  node := &btNode{Data: root.Data}
  Queue1, Queue2 := []*btNode{root}, []*btNode{node}
  for len(Queue1) > 0 {
    p1, p2 := Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      Node := &btNode{Data: p1.Lchild.Data}
      p2.Rchild = Node
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, Node)
    }
    if p1.Rchild != nil {
      Node := &btNode{Data: p1.Rchild.Data}
      p2.Lchild = Node
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, Node)
    }
  }
  return &biTree{Root: node}
}
func Max(L, R int) int {
  if L > R {
    return L
  } else {
    return R
  }
}
func Min(L, R int) int {
  if L < R {
    return L
  } else {
    return R
  }
}
func Equal(bt1, bt2 *btNode) bool {
  if bt1 == nil && bt2 == nil {
    return true
  } else if bt1 == nil || bt2 == nil {
    return false
  }
  if bt1.Data != bt2.Data {
    return false
  }
  return Equal(bt1.Lchild, bt2.Lchild) && Equal(bt1.Rchild, bt2.Rchild)
}
func (bt *biTree) Equal(bt2 *biTree) bool {
  return Equal(bt.Root, bt2.Root)
}
func (bt *biTree) SameAs(bt2 *biTree) bool {
  root1, root2 := bt.Root, bt2.Root
  if root1 == nil && root2 == nil {
    return true
  } else if root1 == nil || root2 == nil {
    return false
  }
  Queue1, Queue2 := []*btNode{root1}, []*btNode{root2}
  p1, p2 := Queue1[0], Queue2[0]
  for len(Queue1) > 0 && len(Queue2) > 0 {
    p1, p2 = Queue1[0], Queue2[0]
    Queue1, Queue2 = Queue1[1:], Queue2[1:]
    if p1.Lchild != nil {
      if p2.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, p2.Lchild)
    } else if p2.Lchild != nil {
      if p1.Lchild == nil || p1.Lchild.Data != p2.Lchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Lchild)
      Queue2 = append(Queue2, p2.Lchild)
    }
    if p1.Rchild != nil {
      if p2.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, p2.Rchild)
    } else if p2.Rchild != nil {
      if p1.Rchild == nil || p1.Rchild.Data != p2.Rchild.Data {
        return false
      }
      Queue1 = append(Queue1, p1.Rchild)
      Queue2 = append(Queue2, p2.Rchild)
    }
  }
  return true
}
func (bt *biTree) MirrorOf(bt2 *biTree) bool {
  return bt.SameAs(Mirror(bt2))
}
func (bt *biTree) IsMirror(bt2 *biTree) bool {
  root := &biTree{&btNode{1, bt.Root, bt2.Root}}
  return root.IsSymmetry()
}
func (bt *biTree) IsSymmetry() bool {
  return Equal(bt.Root.Lchild, bt.Root.Rchild.InvertNodes())
}
func (bt *biTree) IsSymmetry2() bool {
  bt2 := Mirror(bt)
  return bt.SameAs(bt2)
}


另外：从leetcode题目中整理了50多个与二叉树相关的题目，对照看看还有多少没刷过？


eab7af180bab484f9f904c141f504fc1.png


预告：下一集准备刷二叉树路径的题目.……




文章标签：
Go
关键词：
数据结构二叉树
Go语言
Go镜像
Go拷贝
Go语言拷贝
HannYang
目录
相关文章
2的n次方_
|
1天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略，从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成，具有层次关系。二叉树每个节点最多有两个子树，分为左子树和右子树。文中详细描述了二叉树的不同类型，如完全二叉树、满二叉树、平衡二叉树及搜索二叉树，并阐述了二叉树的基本性质与存储方式。此外，还介绍了二叉树的实现方法，包括节点定义、遍历方式（前序、中序、后序、层序遍历），并提供了多个示例代码，帮助理解二叉树的基本操作。
2的n次方_
29 13
【数据结构】二叉树全攻略，从实现到应用详解
aliyun6365824167
|
19天前
|
存储
【初阶数据结构篇】二叉树基础概念
有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
aliyun6365824167
32 1
睡觉待开机
|
24天前
|
存储 算法 Linux
【数据结构】树、二叉树与堆（长期维护）（1）
【数据结构】树、二叉树与堆（长期维护）（1）
睡觉待开机
14 1
睡觉待开机
|
24天前
|
算法
【数据结构】树、二叉树与堆（长期维护）（2）
【数据结构】树、二叉树与堆（长期维护）（2）
睡觉待开机
14 0
【数据结构】树、二叉树与堆（长期维护）（2）
热爱技术的小郑
|
24天前
|
算法 Java
数据结构二叉树
这篇文章讨论了数据结构中的二叉树，并提供了一个二叉树中序遍历的算法示例，包括给定二叉树的根节点返回中序遍历结果的Java代码实现。
热爱技术的小郑
23 0
数据结构二叉树
1603458909890196
|
11天前
|
运维 Shell Go
构建 Go 应用 docker 镜像的十八种姿势
构建 Go 应用 docker 镜像的十八种姿势
1603458909890196
29 0
aliyun6365824167
|
19天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
aliyun6365824167
12 0
aliyun6365824167
|
19天前
|
存储
【初阶数据结构篇】实现链式结构二叉树（二叉链）下篇
要改变root指针的指向，将本来指向根节点的root指针改为空，所以传二级指针（一级指针也可以，只不过在调用完记得把root置为空）。
aliyun6365824167
15 0
aliyun6365824167
|
19天前
|
存储 测试技术
【初阶数据结构篇】实现链式结构二叉树（二叉链）上篇
先构建根结点，再对左右子树构建，每次需要时申请一个结点空间即可，否则返回空指针。
aliyun6365824167
19 0
aliyun6365824167
|
19天前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）
注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++
aliyun6365824167
13 0

热门文章

最新文章

  • 1
    UVa 514 Rails(经典栈)
  • 2
    数据结构实践——队列数组
  • 3
    数据结构-C语言递归实现树的前中后序遍历
  • 4
    动态规划-jobdu-1547：出入栈
  • 5
    数据结构(二)_栈
  • 6
    seastar的用户态协议栈
  • 7
    数据结构与算法(三) 线性表之双向链表
  • 8
    数据结构之链表
  • 9
    OpenJudge计算概论-排队游戏【这个用到了栈的思想】
  • 10
    你知道我想要的不只是算法与数据结构，还有Android高级架构学习开发指南
  • 1
    Golang深入浅出之-Go语言中的异步编程与Future/Promise模式
    198
  • 2
    Golang深入浅出之-Go语言中的协程池设计与实现
    115
  • 3
    Golang深入浅出之-Go语言中的并发安全队列：实现与应用
    388
  • 4
    Golang深入浅出之-Go语言中的并发安全容器：sync.Map与sync.Pool
    116
  • 5
    Golang深入浅出之-Go语言中的CSP模型：深入理解并发哲学
    86
  • 6
    Golang深入浅出之-Go语言中的CSP模型：深入理解并发哲学
    86
  • 7
    Golang深入浅出之-Go语言中的并发模式：Pipeline、Worker Pool等
    55
  • 8
    Golang深入浅出之-Go语言中的反射（reflect）：原理与实战应用
    70
  • 9
    Golang深入浅出之-Go语言代码质量与规范：遵循Gofmt与Linting
    74
  • 10
    2024年的选择：为什么Go可能是理想的后端语言
    589

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • Go语言核心编程 - 面向对象、文件、单元测试、反射、TCP编程
  • Go语言完全自学手册图文教程

    • 相关电子书

    更多
  • Go语言路上踩过的坑
  • gohbase ：HBase go客户端
  • Go构建日请求千亿级微服务实践
    • 下一篇
    DDNS