go语言|数据结构:二叉树可视化(svg树形图改进版)

简介: go语言|数据结构:二叉树可视化(svg树形图改进版)

题目


以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3

d3e5376008194f6281305ac02b2595d8.png



源代码

package main
import (
  "fmt"
  "io"
  "os"
  "os/exec"
  "strconv"
  "strings"
)
type any = interface{}
type btNode struct {
  Data   any
  Lchild *btNode
  Rchild *btNode
}
type biTree struct {
  Root *btNode
  Info *biTreeInfo
}
type biTreeInfo struct {
  Data                []any
  DataLevel           [][]any
  L, R                []bool
  X, Y, W             []int
  Index, Nodes        int
  Width, Height       int
  MarginX, MarginY    int
  SpaceX, SpaceY      int
  SvgWidth, SvgHeight int
  SvgXml              string
}
func Build(Data ...any) *biTree {
  if len(Data) == 0 || Data[0] == nil {
    return &biTree{}
  }
  node := &btNode{Data: Data[0]}
  Queue := []*btNode{node}
  for lst := Data[1:]; len(lst) > 0 && len(Queue) > 0; {
    cur, val := Queue[0], lst[0]
    Queue, lst = Queue[1:], lst[1:]
    if val != nil {
      cur.Lchild = &btNode{Data: val}
      Queue = append(Queue, cur.Lchild)
    }
    if len(lst) > 0 {
      val, lst = lst[0], lst[1:]
      if val != nil {
        cur.Rchild = &btNode{Data: val}
        Queue = append(Queue, cur.Rchild)
      }
    }
  }
  return &biTree{Root: node}
}
func BuildFromList(List []any) *biTree {
  return Build(List...)
}
func AinArray(sub int, array []int) int {
  for idx, arr := range array {
    if sub == arr {
      return idx
    }
  }
  return -1
}
func Pow2(x int) int { //x>=0
  res := 1
  for i := 0; i < x; i++ {
    res *= 2
  }
  return res
}
func Max(L, R int) int {
  if L > R {
    return L
  } else {
    return R
  }
}
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) Coordinate(x, y, w int) []any {
  var res []any
  if bt != nil {
    L, R := bt.Lchild != nil, bt.Rchild != nil
    res = append(res, []any{bt.Data, L, R, x, y, w})
    res = append(res, bt.Lchild.Coordinate(x-w, y+1, w/2)...)
    res = append(res, bt.Rchild.Coordinate(x+w, y+1, w/2)...)
  }
  return res
}
func (bt *biTree) NodeInfo() []any {
  return bt.Root.Coordinate(0, 0, Pow2(bt.Root.MaxDepth()-2))
}
func (bt *biTree) TreeInfo() {
  height := bt.Root.MaxDepth()
  width := Pow2(height - 1)
  lsInfo := bt.NodeInfo()
  btInfo := &biTreeInfo{
    Height: height,
    Width:  width,
    Nodes:  len(lsInfo),
  }
  for _, data := range lsInfo {
    for i, info := range data.([]any) {
      switch i {
      case 0:
        btInfo.Data = append(btInfo.Data, info.(any))
      case 1:
        btInfo.L = append(btInfo.L, info.(bool))
      case 2:
        btInfo.R = append(btInfo.R, info.(bool))
      case 3:
        btInfo.X = append(btInfo.X, info.(int))
      case 4:
        btInfo.Y = append(btInfo.Y, info.(int))
      case 5:
        btInfo.W = append(btInfo.W, info.(int))
      }
    }
  }
  for j, k := 0, width*2; j < height; j++ {
    DLevel := []any{}
    for i := k / 2; i < width*2; i += k {
      index := AinArray(i-width, btInfo.X)
      if index > -1 {
        DLevel = append(DLevel, btInfo.Data[index])
      } else {
        DLevel = append(DLevel, nil)
      }
      DLevel = append(DLevel, []int{i, j})
      if k/4 == 0 {
        DLevel = append(DLevel, []int{0, 0})
        DLevel = append(DLevel, []int{0, 0})
      } else {
        DLevel = append(DLevel, []int{i - k/4, j + 1})
        DLevel = append(DLevel, []int{i + k/4, j + 1})
      }
    }
    k /= 2
    btInfo.DataLevel = append(btInfo.DataLevel, DLevel)
  }
  bt.Info = btInfo
}
func (bt *biTree) Info2SVG(Margin ...int) string {
  var res, Line, Color string
  info := bt.Info
  MarginX, MarginY := 0, 10
  SpaceX, SpaceY := 40, 100
  switch len(Margin) {
  case 0:
    break
  case 1:
    MarginX = Margin[0]
  case 2:
    MarginX, MarginY = Margin[0], Margin[1]
  case 3:
    MarginX, MarginY, SpaceX = Margin[0], Margin[1], Margin[2]
  default:
    MarginX, MarginY = Margin[0], Margin[1]
    SpaceX, SpaceY = Margin[2], Margin[3]
  }
  info.MarginX, info.MarginY = MarginX, MarginY
  info.SpaceX, info.SpaceY = SpaceX, SpaceY
  info.SvgWidth = Pow2(info.Height)*info.SpaceX + info.SpaceX
  info.SvgHeight = info.Height * info.SpaceY
  for i, Data := range info.Data {
    Node := "\n\t<g id=\"INDEX,M,N\">\n\t<CIRCLE/>\n\t<TEXT/>\n\t<LEAF/>\n\t</g>"
    DataStr := ""
    switch Data.(type) {
    case int:
      DataStr = strconv.Itoa(Data.(int))
    case float64:
      DataStr = strconv.FormatFloat(Data.(float64), 'g', -1, 64)
    case string:
      DataStr = Data.(string)
    default:
      DataStr = "Error Type"
    }
    Node = strings.Replace(Node, "INDEX", strconv.Itoa(info.Index), 1)
    Node = strings.Replace(Node, "M", strconv.Itoa(info.X[i]), 1)
    Node = strings.Replace(Node, "N", strconv.Itoa(info.Y[i]), 1)
    x0, y0 := (info.X[i]+info.Width)*SpaceX+MarginX, 50+info.Y[i]*SpaceY+MarginY
    x1, y1 := x0-info.W[i]*SpaceX, y0+SpaceY-30
    x2, y2 := x0+info.W[i]*SpaceX, y0+SpaceY-30
    Color = "orange"
    if info.L[i] && info.R[i] {
      Line = XmlLine(x0-21, y0+21, x1, y1) + "\n\t" + XmlLine(x0+21, y0+21, x2, y2)
    } else if info.L[i] && !info.R[i] {
      Line = XmlLine(x0-21, y0+21, x1, y1)
    } else if !info.L[i] && info.R[i] {
      Line = XmlLine(x0+21, y0+21, x2, y2)
    } else {
      Color = "lightgreen"
    }
    Node = strings.Replace(Node, "<CIRCLE/>", XmlCircle(x0, y0, Color), 1)
    Node = strings.Replace(Node, "<TEXT/>", XmlText(x0, y0, DataStr), 1)
    if info.L[i] || info.R[i] {
      Node = strings.Replace(Node, "<LEAF/>", Line, 1)
    }
    res += Node
  }
  info.SvgXml = res
  return res
}
func XmlCircle(X, Y int, Color string) string {
  Radius := 30
  Circle := "<circle cx=\"" + strconv.Itoa(X) + "\" cy=\"" + strconv.Itoa(Y) +
    "\" r=\"" + strconv.Itoa(Radius) + "\" stroke=\"black\" stroke-width=" +
    "\"2\" fill=\"" + Color + "\" />"
  return Circle
}
func XmlText(X, Y int, DATA string) string {
  iFontSize, tColor := 20, "red"
  Text := "<text x=\"" + strconv.Itoa(X) + "\" y=\"" + strconv.Itoa(Y) +
    "\" fill=\"" + tColor + "\" font-size=\"" + strconv.Itoa(iFontSize) +
    "\" text-anchor=\"middle\" dominant-baseline=\"middle\">" + DATA + "</text>"
  return Text
}
func XmlLine(X1, Y1, X2, Y2 int) string {
  Line := "<line x1=\"" + strconv.Itoa(X1) + "\" y1=\"" + strconv.Itoa(Y1) +
    "\" x2=\"" + strconv.Itoa(X2) + "\" y2=\"" + strconv.Itoa(Y2) +
    "\" style=\"stroke:black;stroke-width:2\" />"
  return Line
}
func (bt *biTree) ShowSVG(FileName ...string) {
  var file *os.File
  var err1 error
  Head := "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink" +
    "=\"http://www.w3.org/1999/xlink\" version=\"1.1\" width=" +
    "\"Width\" height=\"Height\">\nLINKCONTENT\n</svg>"
  Link := `<a xlink:href="https://blog.csdn.net/boysoft2002" target="_blank">
  <text x="5" y="20" fill="blue">Hann's CSDN Homepage</text></a>`
  Xml := strings.Replace(Head, "LINK", Link, 1)
  Xml = strings.Replace(Xml, "Width", strconv.Itoa(bt.Info.SvgWidth), 1)
  Xml = strings.Replace(Xml, "Height", strconv.Itoa(bt.Info.SvgHeight), 1)
  Xml = strings.Replace(Xml, "CONTENT", bt.Info.SvgXml, 1)
  svgFile := "biTree.svg"
  if len(FileName) > 0 {
    svgFile = FileName[0] + ".svg"
  }
  file, err1 = os.Create(svgFile)
  if err1 != nil {
    panic(err1)
  }
  _, err1 = io.WriteString(file, Xml)
  if err1 != nil {
    panic(err1)
  }
  file.Close()
  exec.Command("cmd", "/c", "start", svgFile).Start()
  //Linux 代码:
  //exec.Command("xdg-open", svgFile).Start()
  //Mac 代码:
  //exec.Command("open", svgFile).Start()
}
func main() {
  list := []any{"*", "*", "*", "/", 5, "*", 3.14, 1, 3, nil, nil, 6, 6}
  tree := Build(list...)
  tree.TreeInfo()
  tree.Info2SVG()
  tree.ShowSVG()
  fmt.Println(tree.Info.Data)
  fmt.Println(tree.Info.DataLevel)
}



做题思路

增加一个结构biTreeInfo,在遍历二叉树时把作图要用的信息存入此结构中,方便读取信息。

type any = interface{}
type btNode struct {
    Data   any
    Lchild *btNode
    Rchild *btNode
}
type biTree struct {
    Root *btNode
    Info *biTreeInfo
}
type biTreeInfo struct {
    Data                []any
    DataLevel           [][]any
    L, R                []bool
    X, Y, W             []int
    Index, Nodes        int
    Width, Height       int
    MarginX, MarginY    int
    SpaceX, SpaceY      int
    SvgWidth, SvgHeight int
    SvgXml              string
}
//数据域类型用 type any = interface{} 自定义类型,模拟成any数据类型。


遍历二叉树获取每个结点在svg图形中的坐标,使用先序递归遍历:

func (bt *btNode) Coordinate(x, y, w int) []any {
    var res []any
    if bt != nil {
        L, R := bt.Lchild != nil, bt.Rchild != nil
        res = append(res, []any{bt.Data, L, R, x, y, w})
        res = append(res, bt.Lchild.Coordinate(x-w, y+1, w/2)...)
        res = append(res, bt.Rchild.Coordinate(x+w, y+1, w/2)...)
    }
    return res
}


二叉树的每个结点,转svg时有圆、文字、左或右直线(叶结点没有真线)。

func XmlCircle(X, Y int, Color string) string {
    Radius := 30
    Circle := "<circle cx=\"" + strconv.Itoa(X) + "\" cy=\"" + strconv.Itoa(Y) +
        "\" r=\"" + strconv.Itoa(Radius) + "\" stroke=\"black\" stroke-width=" +
        "\"2\" fill=\"" + Color + "\" />"
    return Circle
}
func XmlText(X, Y int, DATA string) string {
    iFontSize, tColor := 20, "red"
    Text := "<text x=\"" + strconv.Itoa(X) + "\" y=\"" + strconv.Itoa(Y) +
        "\" fill=\"" + tColor + "\" font-size=\"" + strconv.Itoa(iFontSize) +
        "\" text-anchor=\"middle\" dominant-baseline=\"middle\">" + DATA + "</text>"
    return Text
}
func XmlLine(X1, Y1, X2, Y2 int) string {
    Line := "<line x1=\"" + strconv.Itoa(X1) + "\" y1=\"" + strconv.Itoa(Y1) +
        "\" x2=\"" + strconv.Itoa(X2) + "\" y2=\"" + strconv.Itoa(Y2) +
        "\" style=\"stroke:black;stroke-width:2\" />"
    return Line
}


TreeInfo()写入二叉树结点信息,其中DataLevel是层序遍历的结果,也可以用它来作图。

Info2XML()就是把上述方法所得信息,转化成SVG的xml代码;

ShowSVG()生成并显示图形,svg的xml如下:

<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" width="680" height="400">
<a xlink:href="https://blog.csdn.net/boysoft2002" target="_blank">
    <text x="5" y="20" fill="blue">Hann's CSDN Homepage</text></a>
    <g id="0,0,0">
    <circle cx="320" cy="60" r="30" stroke="black" stroke-width="2" fill="orange" />
    <text x="320" y="60" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">*</text>
    <line x1="299" y1="81" x2="160" y2="130" style="stroke:black;stroke-width:2" />
    <line x1="341" y1="81" x2="480" y2="130" style="stroke:black;stroke-width:2" />
    </g>
    <g id="0,-4,1">
    <circle cx="160" cy="160" r="30" stroke="black" stroke-width="2" fill="orange" />
    <text x="160" y="160" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">*</text>
    <line x1="139" y1="181" x2="80" y2="230" style="stroke:black;stroke-width:2" />
    <line x1="181" y1="181" x2="240" y2="230" style="stroke:black;stroke-width:2" />
    </g>
    <g id="0,-6,2">
    <circle cx="80" cy="260" r="30" stroke="black" stroke-width="2" fill="orange" />
    <text x="80" y="260" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">/</text>
    <line x1="59" y1="281" x2="40" y2="330" style="stroke:black;stroke-width:2" />
    <line x1="101" y1="281" x2="120" y2="330" style="stroke:black;stroke-width:2" />
    </g>
    <g id="0,-7,3">
    <circle cx="40" cy="360" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="40" y="360" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">1</text>
    <LEAF/>
    </g>
    <g id="0,-5,3">
    <circle cx="120" cy="360" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="120" y="360" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">3</text>
    <LEAF/>
    </g>
    <g id="0,-2,2">
    <circle cx="240" cy="260" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="240" y="260" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">5</text>
    <LEAF/>
    </g>
    <g id="0,4,1">
    <circle cx="480" cy="160" r="30" stroke="black" stroke-width="2" fill="orange" />
    <text x="480" y="160" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">*</text>
    <line x1="459" y1="181" x2="400" y2="230" style="stroke:black;stroke-width:2" />
    <line x1="501" y1="181" x2="560" y2="230" style="stroke:black;stroke-width:2" />
    </g>
    <g id="0,2,2">
    <circle cx="400" cy="260" r="30" stroke="black" stroke-width="2" fill="orange" />
    <text x="400" y="260" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">*</text>
    <line x1="379" y1="281" x2="360" y2="330" style="stroke:black;stroke-width:2" />
    <line x1="421" y1="281" x2="440" y2="330" style="stroke:black;stroke-width:2" />
    </g>
    <g id="0,1,3">
    <circle cx="360" cy="360" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="360" y="360" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">6</text>
    <LEAF/>
    </g>
    <g id="0,3,3">
    <circle cx="440" cy="360" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="440" y="360" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">6</text>
    <LEAF/>
    </g>
    <g id="0,6,2">
    <circle cx="560" cy="260" r="30" stroke="black" stroke-width="2" fill="lightgreen" />
    <text x="560" y="260" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">3.14</text>
    <LEAF/>
    </g>
</svg>



扩展

多棵二叉树同时展示,Info2SVG()可以设置起始位置



左右并列展示

  tree2 := Build("*", "*", 3.14, 6, 6)
  tree2.TreeInfo()
  tree2.Info2SVG()
  tree2.ShowSVG("tree2")
  //左右并列展示
  tree2.Info2SVG(tree.Info.SvgWidth, tree.Info.SpaceY)
  tree.Info.SvgXml += tree2.Info.SvgXml
  tree.Info.SvgWidth += tree2.Info.SvgWidth
  tree.ShowSVG("tree12")
  tree.Info2SVG() //恢复tree原状

265042bf86be421a81c23c959ff92794.png




上下并列展示

  //上下并列展示
  tree2.Info2SVG(tree.Info.SvgWidth-tree2.Info.SvgWidth, tree.Info.SvgHeight)
  tree.Info.SvgXml += tree2.Info.SvgXml
  tree.Info.SvgHeight += tree2.Info.SvgHeight
  tree.ShowSVG("tree123")
  tree.Info2SVG() //恢复tree原状

以上2段代码放在前文源代码的main()函数中测试。


60f665e58e2b461d8a067d9b6e776683.png




总结回顾


结点显示的代码固定了文字和圆形的大小颜色,如果读者愿意自己动手的话,可以尝试把这些要素设成参数或者增加biTreeInfo结构的属性。


ac17f04147fc4162b4e70de9b25eaaa3.png





目录
相关文章
|
3月前
|
运维 监控 算法
监控局域网其他电脑:Go 语言迪杰斯特拉算法的高效应用
在信息化时代,监控局域网成为网络管理与安全防护的关键需求。本文探讨了迪杰斯特拉(Dijkstra)算法在监控局域网中的应用,通过计算最短路径优化数据传输和故障检测。文中提供了使用Go语言实现的代码例程,展示了如何高效地进行网络监控,确保局域网的稳定运行和数据安全。迪杰斯特拉算法能减少传输延迟和带宽消耗,及时发现并处理网络故障,适用于复杂网络环境下的管理和维护。
|
3月前
|
编译器 Go
揭秘 Go 语言中空结构体的强大用法
Go 语言中的空结构体 `struct{}` 不包含任何字段,不占用内存空间。它在实际编程中有多种典型用法:1) 结合 map 实现集合(set)类型;2) 与 channel 搭配用于信号通知;3) 申请超大容量的 Slice 和 Array 以节省内存;4) 作为接口实现时明确表示不关注值。此外,需要注意的是,空结构体作为字段时可能会因内存对齐原因占用额外空间。建议将空结构体放在外层结构体的第一个字段以优化内存使用。
|
25天前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
46 4
|
1月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
55 10
|
1月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
129 10
|
1月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
106 9
|
2月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
76 3
 算法系列之数据结构-Huffman树
|
2月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
132 19
|
3月前
|
存储 缓存 监控
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
51 3
|
3月前
|
存储 缓存 安全
Go 语言中的 Sync.Map 详解:并发安全的 Map 实现
`sync.Map` 是 Go 语言中用于并发安全操作的 Map 实现,适用于读多写少的场景。它通过两个底层 Map(`read` 和 `dirty`)实现读写分离,提供高效的读性能。主要方法包括 `Store`、`Load`、`Delete` 等。在大量写入时性能可能下降,需谨慎选择使用场景。