最近一直在刷二叉树题目，但在要验证结果时，通常用中序遍历、层序遍历查看结果，验证起来没有画图来得直观，所有想到自己动手制作二叉树的树形图。 直接开干，先从svg入手：
什么是SVG
SVG定义
SVG是可伸缩矢量图形 (Scalable Vector Graphics)，于2003年1月14日成为 W3C 推荐标准。
SVG 用来定义用于网络的基于矢量的图形
SVG 使用 XML 格式定义图形
SVG 是万维网联盟的标准
SVG 与诸如 DOM 和 XSL 之类的 W3C 标准是一个整体
SVG优点
- SVG 可被非常多的工具读取和修改（比如记事本）
- SVG 与 JPEG 和 GIF 图像比起来，尺寸更小，且可压缩性更强。
- SVG 图像在放大或改变尺寸的情况下其图形质量不会有所损失
- SVG 图像可在任何的分辨率下被高质量地打印
- SVG 可在图像质量不下降的情况下被放大
- SVG 图像中的文本是可选的，同时也是可搜索的（很适合制作地图）
- SVG 可以与 JavaScript 技术一起运行
- SVG 是开放的标准
- SVG 文件是纯粹的 XML
预定义元素
- 矩形 <rect>
- 圆形 <circle>
- 椭圆 <ellipse>
- 直线 <line>
- 文字 <text>
- 路径 <path>
- 折线 <polyline>
- 多边形 <polygon>
制作二叉树的树形图，就使用圆形、直线、文字三种即可：
圆形 <circle>
|
1 2 3 |
<svg xmlns="http://www.w3.org/2000/svg" version="1.1"> <circle cx="150" cy="50" r="30" stroke="black" stroke-width="2" fill="red"/> </svg> |
cx和cy属性定义圆点的x和y坐标；r属性定义圆的半径
如果省略cx和cy，圆的中心会被设置为(0, 0)
直线 <line>
|
1 2 3 |
<svg xmlns="http://www.w3.org/2000/svg" version="1.1"> <line x1="50" y1="50" x2="200" y2="200" style="stroke:red;stroke-width:2"/> </svg> |
x1，y2 属性定义线条的起始端点坐标
x2，y2 属性定义线条的结束端点坐标
文字 <text>
|
1 2 3 |
<svg xmlns="http://www.w3.org/2000/svg" version="1.1"> <text x="30" y="150" fill="red">Welcome to Hann's HomePage</text> </svg> |
x，y 属性定义文字左对齐显示时的起始坐标（居中对齐则是文字中间点）
fill 属性定义文字的颜色
结点SVG格式
根结点
由<circle>和<text>组成，存放结点的数据域
|
1 2 3 4 |
<g id="0,0"> <circle cx="400" cy="50" r="30" stroke="black" stroke-width="2" fill="orange" /> <text x="400" y="50" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">1</text> </g> |
子树结点
比根结点多出<line>元素，用来表示父结点左或右指针的指向
|
1 2 3 4 5 |
<g id="1,0"> <circle cx="200" cy="170" r="30" stroke="black" stroke-width="2" fill="orange" /> <text x="200" y="170" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">2</text> <line x1="200" y1="140" x2="379" y2="71" style="stroke:black;stroke-width:2"/> </g> |
叶结点
与子树结点相同，为区别显示把<circle>填充色改为greenlight
|
1 2 3 4 5 |
<g id="1,1"> <circle cx="600" cy="170" r="30" stroke="black" stroke-width="2" fill="lightgreen" /> <text x="600" y="170" fill="red" font-size="20" text-anchor="middle" dominant-baseline="middle">3</text> <line x1="600" y1="140" x2="421" y2="71" style="stroke:black;stroke-width:2"/> </g> |
结点坐标
坐标的确定
结点坐标确定，把二叉树还原成满二叉树，结点位置标记为：
[ [0,0], [1,0], [1,1], [2,0], [2,1], [2,2], [2,3], [3,0]......]，再用循环计算出各点坐标。
连线的夹角
实际上不用考虑连线夹角，只要计算出连线始终两端点的坐标即可：
结点文本
以字符串形式保存好属性变量的特征关键词，用于遍历二叉树时替换成实际数据：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
func XmlNode(M, N, X, Y int, Data string, Color ...string) string { var cColor, tColor string R := 30 Node := `<Tab><g id="M,N"> <circle cx="X" cy="Y" r="RC" stroke="black" stroke-width="2" fill="COLOR" /> <text x="X" y="Y" fill="TextColor" font-size="20" text-anchor="middle" dominant-baseline="middle">DATA</text> <ROOT/> </g><CrLf>` if len(Color) == 0 { cColor, tColor = "orange", "red" } else if len(Color) == 1 { cColor, tColor = Color[0], "red" } else { cColor, tColor = Color[0], Color[1] } Node = strings.Replace(Node, "M", strconv.Itoa(M), 1) Node = strings.Replace(Node, "N", strconv.Itoa(N), 1) Node = strings.Replace(Node, "X", strconv.Itoa(X), 2) Node = strings.Replace(Node, "Y", strconv.Itoa(Y), 2) Node = strings.Replace(Node, "RC", strconv.Itoa(R), 1) Node = strings.Replace(Node, "DATA", Data, 1) Node = strings.Replace(Node, "COLOR", cColor, 1) Node = strings.Replace(Node, "TextColor", tColor, 1) Node = strings.Replace(Node, "<CrLf>", "\n", -1) Node = strings.Replace(Node, "<Tab>", "\t", -1) Node = strings.Replace(Node, "\n\t\t", " ", -1) return Node } |
二叉树转SVG
遍历二叉树对应的满二叉树，读出数据域并计算坐标，转成svg格式：
格式转换
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
func (bt *biTree) Xml4Tree() string { var Xml, Node string Head := "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/" + "1999/xlink\" version=\"1.1\" width=\"Width\" height=\"Height\">\nCONTENT</svg>" Line := `<line x1="X1" y1="Y1" x2="X2" y2="Y2" style="stroke:black;stroke-width:2"/>` Link := `<a xlink:href="https://blog.csdn.net/boysoft2002" target="_blank"> <text x="5" y="20" fill="blue">Hann's CSDN Homepage</text></a>` List := bt.LevelNullwith() Levels := len(List) for i := Levels - 1; i >= 0; i-- { negative := -1 TmpXml := "" for j := 0; j < Pow2(i); j++ { t := Pow2(Levels - i - 1) x, y := 50*(2*t*j+t), 120*i+50 if List[i][j] != nil { fillColor := "orange" if i == Levels-1 || i > 0 && i < Levels-1 && List[i+1][j*2] == nil && List[i+1][j*2+1] == nil { fillColor = "lightgreen" } TmpStr := "" switch List[i][j].(type) { case int: TmpStr = strconv.Itoa(List[i][j].(int)) case float64: TmpStr = strconv.FormatFloat(List[i][j].(float64), 'g', -1, 64) case string: TmpStr = List[i][j].(string) default: TmpStr = "Error Type" } Xml = XmlNode(i, j, x, y, TmpStr, fillColor) } if i > 0 { line1 := strings.Replace(Line, "X1", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y1", strconv.Itoa(y-30), 1) negative *= -1 x0, y0 := 21, 21 x += 50*negative*(2*t*j%2+t) - negative*x0 line1 = strings.Replace(line1, "X2", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y2", strconv.Itoa(y-120+y0), 1) Xml = strings.Replace(Xml, "<ROOT/>", line1, 1) } if List[i][j] != nil { TmpXml += Xml } } Node = TmpXml + Node } Xml = strings.Replace(Head, "CONTENT", Node, 1) Xml = strings.Replace(Xml, "Width", strconv.Itoa(Pow2(Levels)*50), 1) Xml = strings.Replace(Xml, "Height", strconv.Itoa(Levels*120), 1) Xml = strings.Replace(Xml, "<ROOT/>", Link, 1) return Xml } |
写入文件、调取浏览
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//...... for index, text := range texts { svgFile := "./biTree0" + strconv.Itoa(index+1) + ".svg" file, err1 = os.Create(svgFile) if err1 != nil { panic(err1) } _, err1 = io.WriteString(file, text) 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() } //...... |
全部源代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 |
package main
import ( "fmt" "io" "os" "os/exec" "strconv" "strings" )
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 (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 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 (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) LevelNullwith(Fills ...interface{}) [][]interface{} { var Nodes [][]interface{} var Fill0 interface{} if len(Fills) == 0 { Fill0 = nil } else if len(Fills) == 1 { Fill0 = Fills[0] } else { panic("Error: number of parameters is greater than 1") } root := bt.Root if root == nil { return Nodes } Count := 0 Queue := []*btNode{root} for len(Queue) > 0 { nodes := []interface{}{} Level := len(Queue) for Level > 0 { cur := Queue[0] Queue = Queue[1:] nodes = append(nodes, cur.Data) Count++ Level-- if cur.Lchild != nil { Queue = append(Queue, cur.Lchild) } if cur.Rchild != nil { Queue = append(Queue, cur.Rchild) } } Nodes = append(Nodes, nodes) } newbiTree := Copy(bt) for i := 1; i < Pow2(len(Nodes))-Count; i++ { newbiTree.AppendNode(Fill0) } return newbiTree.BForder2D() }
func XmlNode(M, N, X, Y int, Data string, Color ...string) string { var cColor, tColor string R := 30 Node := `<Tab><g id="M,N"> <circle cx="X" cy="Y" r="RC" stroke="black" stroke-width="2" fill="COLOR" /> <text x="X" y="Y" fill="TextColor" font-size="20" text-anchor="middle" dominant-baseline="middle">DATA</text> <ROOT/> </g><CrLf>` if len(Color) == 0 { cColor, tColor = "orange", "red" } else if len(Color) == 1 { cColor, tColor = Color[0], "red" } else { cColor, tColor = Color[0], Color[1] } Node = strings.Replace(Node, "M", strconv.Itoa(M), 1) Node = strings.Replace(Node, "N", strconv.Itoa(N), 1) Node = strings.Replace(Node, "X", strconv.Itoa(X), 2) Node = strings.Replace(Node, "Y", strconv.Itoa(Y), 2) Node = strings.Replace(Node, "RC", strconv.Itoa(R), 1) Node = strings.Replace(Node, "DATA", Data, 1) Node = strings.Replace(Node, "COLOR", cColor, 1) Node = strings.Replace(Node, "TextColor", tColor, 1) Node = strings.Replace(Node, "<CrLf>", "\n", -1) Node = strings.Replace(Node, "<Tab>", "\t", -1) Node = strings.Replace(Node, "\n\t\t", " ", -1) return Node }
func Pow2(x int) int { //x>=0 res := 1 for i := 0; i < x; i++ { res *= 2 } return res }
func Xml4Full(Levels int) string { var Xml, Node string Head := "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/" + "1999/xlink\" version=\"1.1\" width=\"Width\" height=\"Height\">\nCONTENT</svg>" Line := `<line x1="X1" y1="Y1" x2="X2" y2="Y2" style="stroke:black;stroke-width:2"/>` Link := `<a xlink:href="https://blog.csdn.net/boysoft2002" rel="external nofollow" rel="external nofollow" target="_blank"> <text x="5" y="20" fill="blue">Hann's CSDN Homepage</text></a>` for i := 0; i < Levels; i++ { negative := -1 for j := 0; j < Pow2(i); j++ { t := Pow2(Levels - i - 1) x, y := 50*(2*t*j+t), 120*i+50 if Levels != 1 && i == Levels-1 { Xml = XmlNode(i, j, x, y, strconv.Itoa(Pow2(i)+j), "lightgreen") } else { Xml = XmlNode(i, j, x, y, strconv.Itoa(Pow2(i)+j)) } if i > 0 { line1 := strings.Replace(Line, "X1", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y1", strconv.Itoa(y-30), 1) negative *= -1 x0, y0 := 21, 21 //过连线起始端的半径与纵轴线夹角取45度时x,y坐标修正值21,21[30/1.414] //取30度时 x0,y0:= 15,30-26；取60度时 x0,y0:= 26[15*1.732],15 x += 50*negative*(2*t*j%2+t) - negative*x0 line1 = strings.Replace(line1, "X2", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y2", strconv.Itoa(y-120+y0), 1) Xml = strings.Replace(Xml, "<ROOT/>", line1, 1) } Node += Xml } } Xml = strings.Replace(Head, "CONTENT", Node, 1) Xml = strings.Replace(Xml, "Width", strconv.Itoa(Pow2(Levels)*50), 1) Xml = strings.Replace(Xml, "Height", strconv.Itoa(Levels*120), 1) Xml = strings.Replace(Xml, "<ROOT/>", Link, 1) return Xml }
func (bt *biTree) Xml4Tree() string { var Xml, Node string Head := "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/" + "1999/xlink\" version=\"1.1\" width=\"Width\" height=\"Height\">\nCONTENT</svg>" Line := `<line x1="X1" y1="Y1" x2="X2" y2="Y2" style="stroke:black;stroke-width:2"/>` Link := `<a xlink:href="https://blog.csdn.net/boysoft2002" rel="external nofollow" rel="external nofollow" target="_blank"> <text x="5" y="20" fill="blue">Hann's CSDN Homepage</text></a>` List := bt.LevelNullwith() Levels := len(List) for i := Levels - 1; i >= 0; i-- { negative := -1 TmpXml := "" for j := 0; j < Pow2(i); j++ { t := Pow2(Levels - i - 1) x, y := 50*(2*t*j+t), 120*i+50 if List[i][j] != nil { fillColor := "orange" if i == Levels-1 || i > 0 && i < Levels-1 && List[i+1][j*2] == nil && List[i+1][j*2+1] == nil { fillColor = "lightgreen" } TmpStr := "" switch List[i][j].(type) { case int: TmpStr = strconv.Itoa(List[i][j].(int)) case float64: TmpStr = strconv.FormatFloat(List[i][j].(float64), 'g', -1, 64) case string: TmpStr = List[i][j].(string) default: TmpStr = "Error Type" } Xml = XmlNode(i, j, x, y, TmpStr, fillColor) } if i > 0 { line1 := strings.Replace(Line, "X1", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y1", strconv.Itoa(y-30), 1) negative *= -1 x0, y0 := 21, 21 x += 50*negative*(2*t*j%2+t) - negative*x0 line1 = strings.Replace(line1, "X2", strconv.Itoa(x), 1) line1 = strings.Replace(line1, "Y2", strconv.Itoa(y-120+y0), 1) Xml = strings.Replace(Xml, "<ROOT/>", line1, 1) } if List[i][j] != nil { TmpXml += Xml } } Node = TmpXml + Node } Xml = strings.Replace(Head, "CONTENT", Node, 1) Xml = strings.Replace(Xml, "Width", strconv.Itoa(Pow2(Levels)*50), 1) Xml = strings.Replace(Xml, "Height", strconv.Itoa(Levels*120), 1) Xml = strings.Replace(Xml, "<ROOT/>", Link, 1) return Xml }
func main() {
var file *os.File var err1 error
list1 := []interface{}{"-", "*", 6, "+", 3, nil, nil, 2, 8} list2 := []interface{}{1, 2, 3, 4, 5, nil, 6, 7, 8} tree1 := Build(list1) tree2 := Build(list2) tree3 := Mirror(tree2) texts := []string{tree1.Xml4Tree(), tree2.Xml4Tree(), tree3.Xml4Tree(), Xml4Full(4)}
for index, text := range texts { svgFile := "./biTree0" + strconv.Itoa(index+1) + ".svg" file, err1 = os.Create(svgFile) if err1 != nil { panic(err1) } _, err1 = io.WriteString(file, text) 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() }
fmt.Println("Welcome to my homepage: https://blog.csdn.net/boysoft2002") exec.Command("cmd", "/c", "start", "https://blog.csdn.net/boysoft2002").Start()
} |
至此，已达成自己的预想结果，算法实在有点笨拙，但总算成功了。
