<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
Go語言資料結構之二元樹視覺化詳解
2022-09-18 22:00:52
題目
以圖形展示任意二元樹，如下圖，一箇中綴表示式表示的二元樹：3.14*r²*h/3
原始碼
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 := "nt<g id="INDEX,M,N">nt<CIRCLE/>nt<TEXT/>nt<LEAF/>nt</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) + "nt" + 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">nLINKCONTENTn</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原狀
上下並列展示
//上下並列展示
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()函數中測試。
總結回顧
結點顯示的程式碼固定了文字和圓形的大小顏色，如果讀者願意自己動手的話，可以嘗試把這些要素設成引數或者增加biTreeInfo結構的屬性。
到此這篇關於Go語言資料結構之二元樹視覺化詳解的文章就介紹到這了,更多相關Go語言 二元樹視覺化內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45