• go语言｜数据结构：二叉树可视化（svg树形图改进版）

    题目

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

    源代码

    1. package main
    2.  
    3. import (
    4. 	"fmt"
    5. 	"io"
    6. 	"os"
    7. 	"os/exec"
    8. 	"strconv"
    9. 	"strings"
    10. )
    11.  
    12. type any = interface{}
    13.  
    14. type btNode struct {
    15. 	Data   any
    16. 	Lchild *btNode
    17. 	Rchild *btNode
    18. }
    19.  
    20. type biTree struct {
    21. 	Root *btNode
    22. 	Info *biTreeInfo
    23. }
    24.  
    25. type biTreeInfo struct {
    26. 	Data                []any
    27. 	DataLevel           [][]any
    28. 	L, R                []bool
    29. 	X, Y, W             []int
    30. 	Index, Nodes        int
    31. 	Width, Height       int
    32. 	MarginX, MarginY    int
    33. 	SpaceX, SpaceY      int
    34. 	SvgWidth, SvgHeight int
    35. 	SvgXml              string
    36. }
    37.  
    38. func Build(Data ...any) *biTree {
    39. 	if len(Data) == 0 || Data[0] == nil {
    40. 		return &biTree{}
    41. 	}
    42. 	node := &btNode{Data: Data[0]}
    43. 	Queue := []*btNode{node}
    44. 	for lst := Data[1:]; len(lst) > 0 && len(Queue) > 0; {
    45. 		cur, val := Queue[0], lst[0]
    46. 		Queue, lst = Queue[1:], lst[1:]
    47. 		if val != nil {
    48. 			cur.Lchild = &btNode{Data: val}
    49. 			Queue = append(Queue, cur.Lchild)
    50. 		}
    51. 		if len(lst) > 0 {
    52. 			val, lst = lst[0], lst[1:]
    53. 			if val != nil {
    54. 				cur.Rchild = &btNode{Data: val}
    55. 				Queue = append(Queue, cur.Rchild)
    56. 			}
    57. 		}
    58. 	}
    59. 	return &biTree{Root: node}
    60. }
    61.  
    62. func BuildFromList(List []any) *biTree {
    63. 	return Build(List...)
    64. }
    65.  
    66. func AinArray(sub int, array []int) int {
    67. 	for idx, arr := range array {
    68. 		if sub == arr {
    69. 			return idx
    70. 		}
    71. 	}
    72. 	return -1
    73. }
    74.  
    75. func Pow2(x int) int { //x>=0
    76. 	res := 1
    77. 	for i := 0; i < x; i++ {
    78. 		res *= 2
    79. 	}
    80. 	return res
    81. }
    82.  
    83. func Max(L, R int) int {
    84. 	if L > R {
    85. 		return L
    86. 	} else {
    87. 		return R
    88. 	}
    89. }
    90.  
    91. func (bt *btNode) MaxDepth() int {
    92. 	if bt == nil {
    93. 		return 0
    94. 	}
    95. 	Lmax := bt.Lchild.MaxDepth()
    96. 	Rmax := bt.Rchild.MaxDepth()
    97. 	return 1 + Max(Lmax, Rmax)
    98. }
    99.  
    100. func (bt *btNode) Coordinate(x, y, w int) []any {
    101. 	var res []any
    102. 	if bt != nil {
    103. 		L, R := bt.Lchild != nil, bt.Rchild != nil
    104. 		res = append(res, []any{bt.Data, L, R, x, y, w})
    105. 		res = append(res, bt.Lchild.Coordinate(x-w, y+1, w/2)...)
    106. 		res = append(res, bt.Rchild.Coordinate(x+w, y+1, w/2)...)
    107. 	}
    108. 	return res
    109. }
    110.  
    111. func (bt *biTree) NodeInfo() []any {
    112. 	return bt.Root.Coordinate(0, 0, Pow2(bt.Root.MaxDepth()-2))
    113. }
    114.  
    115. func (bt *biTree) TreeInfo() {
    116. 	height := bt.Root.MaxDepth()
    117. 	width := Pow2(height - 1)
    118. 	lsInfo := bt.NodeInfo()
    119. 	btInfo := &biTreeInfo{
    120. 		Height: height,
    121. 		Width:  width,
    122. 		Nodes:  len(lsInfo),
    123. 	}
    124. 	for _, data := range lsInfo {
    125. 		for i, info := range data.([]any) {
    126. 			switch i {
    127. 			case 0:
    128. 				btInfo.Data = append(btInfo.Data, info.(any))
    129. 			case 1:
    130. 				btInfo.L = append(btInfo.L, info.(bool))
    131. 			case 2:
    132. 				btInfo.R = append(btInfo.R, info.(bool))
    133. 			case 3:
    134. 				btInfo.X = append(btInfo.X, info.(int))
    135. 			case 4:
    136. 				btInfo.Y = append(btInfo.Y, info.(int))
    137. 			case 5:
    138. 				btInfo.W = append(btInfo.W, info.(int))
    139. 			}
    140. 		}
    141. 	}
    142. 	for j, k := 0, width*2; j < height; j++ {
    143. 		DLevel := []any{}
    144. 		for i := k / 2; i < width*2; i += k {
    145. 			index := AinArray(i-width, btInfo.X)
    146. 			if index > -1 {
    147. 				DLevel = append(DLevel, btInfo.Data[index])
    148. 			} else {
    149. 				DLevel = append(DLevel, nil)
    150. 			}
    151. 			DLevel = append(DLevel, []int{i, j})
    152. 			if k/4 == 0 {
    153. 				DLevel = append(DLevel, []int{0, 0})
    154. 				DLevel = append(DLevel, []int{0, 0})
    155. 			} else {
    156. 				DLevel = append(DLevel, []int{i - k/4, j + 1})
    157. 				DLevel = append(DLevel, []int{i + k/4, j + 1})
    158. 			}
    159. 		}
    160. 		k /= 2
    161. 		btInfo.DataLevel = append(btInfo.DataLevel, DLevel)
    162. 	}
    163. 	bt.Info = btInfo
    164. }
    165.  
    166. func (bt *biTree) Info2SVG(Margin ...int) string {
    167. 	var res, Line, Color string
    168. 	info := bt.Info
    169. 	MarginX, MarginY := 0, 10
    170. 	SpaceX, SpaceY := 40, 100
    171. 	switch len(Margin) {
    172. 	case 0:
    173. 		break
    174. 	case 1:
    175. 		MarginX = Margin[0]
    176. 	case 2:
    177. 		MarginX, MarginY = Margin[0], Margin[1]
    178. 	case 3:
    179. 		MarginX, MarginY, SpaceX = Margin[0], Margin[1], Margin[2]
    180. 	default:
    181. 		MarginX, MarginY = Margin[0], Margin[1]
    182. 		SpaceX, SpaceY = Margin[2], Margin[3]
    183. 	}
    184. 	info.MarginX, info.MarginY = MarginX, MarginY
    185. 	info.SpaceX, info.SpaceY = SpaceX, SpaceY
    186. 	info.SvgWidth = Pow2(info.Height)*info.SpaceX + info.SpaceX
    187. 	info.SvgHeight = info.Height * info.SpaceY
    188. 	for i, Data := range info.Data {
    189. 		Node := "\n\t\n\t\n\t\n\t\n\t"
    190. 		DataStr := ""
    191. 		switch Data.(type) {
    192. 		case int:
    193. 			DataStr = strconv.Itoa(Data.(int))
    194. 		case float64:
    195. 			DataStr = strconv.FormatFloat(Data.(float64), 'g', -1, 64)
    196. 		case string:
    197. 			DataStr = Data.(string)
    198. 		default:
    199. 			DataStr = "Error Type"
    200. 		}
    201. 		Node = strings.Replace(Node, "INDEX", strconv.Itoa(info.Index), 1)
    202. 		Node = strings.Replace(Node, "M", strconv.Itoa(info.X[i]), 1)
    203. 		Node = strings.Replace(Node, "N", strconv.Itoa(info.Y[i]), 1)
    204. 		x0, y0 := (info.X[i]+info.Width)*SpaceX+MarginX, 50+info.Y[i]*SpaceY+MarginY
    205. 		x1, y1 := x0-info.W[i]*SpaceX, y0+SpaceY-30
    206. 		x2, y2 := x0+info.W[i]*SpaceX, y0+SpaceY-30
    207. 		Color = "orange"
    208. 		if info.L[i] && info.R[i] {
    209. 			Line = XmlLine(x0-21, y0+21, x1, y1) + "\n\t" + XmlLine(x0+21, y0+21, x2, y2)
    210. 		} else if info.L[i] && !info.R[i] {
    211. 			Line = XmlLine(x0-21, y0+21, x1, y1)
    212. 		} else if !info.L[i] && info.R[i] {
    213. 			Line = XmlLine(x0+21, y0+21, x2, y2)
    214. 		} else {
    215. 			Color = "lightgreen"
    216. 		}
    217. 		Node = strings.Replace(Node, "", XmlCircle(x0, y0, Color), 1)
    218. 		Node = strings.Replace(Node, "", XmlText(x0, y0, DataStr), 1)
    219. 		if info.L[i] || info.R[i] {
    220. 			Node = strings.Replace(Node, "", Line, 1)
    221. 		}
    222. 		res += Node
    223. 	}
    224. 	info.SvgXml = res
    225. 	return res
    226. }
    227.  
    228. func XmlCircle(X, Y int, Color string) string {
    229. 	Radius := 30
    230. 	Circle := " + strconv.Itoa(X) + "\" cy=\"" + strconv.Itoa(Y) +
    231. 		"\" r=\"" + strconv.Itoa(Radius) + "\" stroke=\"black\" stroke-width=" +
    232. 		"\"2\" fill=\"" + Color + "\" />"
    233. 	return Circle
    234. }
    235.  
    236. func XmlText(X, Y int, DATA string) string {
    237. 	iFontSize, tColor := 20, "red"
    238. 	Text := " + strconv.Itoa(X) + "\" y=\"" + strconv.Itoa(Y) +
    239. 		"\" fill=\"" + tColor + "\" font-size=\"" + strconv.Itoa(iFontSize) +
    240. 		"\" text-anchor=\"middle\" dominant-baseline=\"middle\">" + DATA + ""
    241. 	return Text
    242. }
    243.  
    244. func XmlLine(X1, Y1, X2, Y2 int) string {
    245. 	Line := " + strconv.Itoa(X1) + "\" y1=\"" + strconv.Itoa(Y1) +
    246. 		"\" x2=\"" + strconv.Itoa(X2) + "\" y2=\"" + strconv.Itoa(Y2) +
    247. 		"\" style=\"stroke:black;stroke-width:2\" />"
    248. 	return Line
    249. }
    250.  
    251. func (bt *biTree) ShowSVG(FileName ...string) {
    252. 	var file *os.File
    253. 	var err1 error
    254. 	Head := " +
    255. 		"=\"http://www.w3.org/1999/xlink\" version=\"1.1\" width=" +
    256. 		"\"Width\" height=\"Height\">\nLINKCONTENT\n"
    257. 	Link := `
    258. 	Hann's CSDN Homepage`
    259. 	Xml := strings.Replace(Head, "LINK", Link, 1)
    260. 	Xml = strings.Replace(Xml, "Width", strconv.Itoa(bt.Info.SvgWidth), 1)
    261. 	Xml = strings.Replace(Xml, "Height", strconv.Itoa(bt.Info.SvgHeight), 1)
    262. 	Xml = strings.Replace(Xml, "CONTENT", bt.Info.SvgXml, 1)
    263. 	svgFile := "biTree.svg"
    264. 	if len(FileName) > 0 {
    265. 		svgFile = FileName[0] + ".svg"
    266. 	}
    267. 	file, err1 = os.Create(svgFile)
    268. 	if err1 != nil {
    269. 		panic(err1)
    270. 	}
    271. 	_, err1 = io.WriteString(file, Xml)
    272. 	if err1 != nil {
    273. 		panic(err1)
    274. 	}
    275. 	file.Close()
    276. 	exec.Command("cmd", "/c", "start", svgFile).Start()
    277. 	//Linux 代码：
    278. 	//exec.Command("xdg-open", svgFile).Start()
    279. 	//Mac 代码：
    280. 	//exec.Command("open", svgFile).Start()
    281. }
    282.  
    283. func main() {
    284.  
    285. 	list := []any{"*", "*", "*", "/", 5, "*", 3.14, 1, 3, nil, nil, 6, 6}
    286. 	tree := Build(list...)
    287. 	tree.TreeInfo()
    288. 	tree.Info2SVG()
    289. 	tree.ShowSVG()
    290.  
    291. 	fmt.Println(tree.Info.Data)
    292. 	fmt.Println(tree.Info.DataLevel)
    293.  
    294. }

    做题思路

    增加一个结构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 := "         "\" 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 := "         "\" fill=\"" + tColor + "\" font-size=\"" + strconv.Itoa(iFontSize) +
            "\" text-anchor=\"middle\" dominant-baseline=\"middle\">" + DATA + "    "
        return Text
    }

    func XmlLine(X1, Y1, X2, Y2 int) string {
        Line := "         "\" x2=\"" + strconv.Itoa(X2) + "\" y2=\"" + strconv.Itoa(Y2) +
            "\" style=\"stroke:black;stroke-width:2\" />"
        return Line
    }

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

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

    ShowSVG()生成并显示图形，svg的xml如下：



        Hann's CSDN Homepage
        
        
        *
        
        
        
        
        
        *
        
        
        
        
        
        /
        
        
        
        
        
        1
        
        
        
        
        3
        
        
        
        
        5
        
        
        
        
        *
        
        
        
        
        
        *
        
        
        
        
        
        6
        
        
        
        
        6
        
        
        
        
        3.14
        
        

    扩展

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

    左右并列展示

    1. 	tree2 := Build("*", "*", 3.14, 6, 6)
    2. 	tree2.TreeInfo()
    3. 	tree2.Info2SVG()
    4. 	tree2.ShowSVG("tree2")
    5.  
    6. 	//左右并列展示
    7. 	tree2.Info2SVG(tree.Info.SvgWidth, tree.Info.SpaceY)
    8. 	tree.Info.SvgXml += tree2.Info.SvgXml
    9. 	tree.Info.SvgWidth += tree2.Info.SvgWidth
    10. 	tree.ShowSVG("tree12")
    11. 	tree.Info2SVG() //恢复tree原状

    上下并列展示

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

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

     

    总结回顾

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

  • 相关阅读:
    【c++】stringstream基础：实现数据类型转换和字符串分割
    RabbitMQ
    vue使用.filter方法检索数组中指定时间段内的数据
    4.7 wait notify - 4.11 多把锁
    携创教育：2022年10月广东自考成绩查询时间？成绩查询流程？
    Python_Numpy库的ndarray对象的属性有哪些?如何获取它们的值?
    昔日红极一时，如今重出江湖，这种按键位要怎么设计
    App 软件开发《判断5》试卷及答案
    关于nginx一个域名，配置多个端口https的方法
    5分钟学会canvas的使用
  • 原文地址：https://blog.csdn.net/boysoft2002/article/details/126908846