当前位置: 萬仟网 > IT编程>脚本编程>Go语言 > Go语言数据结构之二叉树可视化详解

Go语言数据结构之二叉树可视化详解

2022年09月18日 Go语言 我要评论
题目以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3源代码package main import ( "fmt" "io" "os"

题目

以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树: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 := "\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原状

上下并列展示

    //上下并列展示
    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语言 二叉树可视化内容请搜索萬仟网以前的文章或继续浏览下面的相关文章希望大家以后多多支持萬仟网!

(1)
打赏 微信扫一扫 微信扫一扫

相关文章:

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。

发表评论

验证码:
Copyright © 2017-2022  萬仟网 保留所有权利. 琼ICP备2022007597号