1.画出如下图片

2.放出源码
package main
import (
"fmt"
"io"
"os"
"os/exec"
"strconv"
"strings"
)
/* 参考:https://blog.nanpuyue.com/2019/054.html */
func main() {
if len(os.Args) != 2 {
fmt.Printf("usage: %s \"1,0,2,4,0,4,5,6,7,1,null,6,5,4,nil,3\"\n", os.Args[0])
return
}
const maxInt = 1<<31 - 1
var arr []int
for _, v := range strings.Split(os.Args[1], ",") {
str := strings.TrimSpace(v)
if str == "nil" || str == "null" {
arr = append(arr, maxInt) // 表示nil节点
} else if tmp, err := strconv.Atoi(str); err == nil {
arr = append(arr, tmp)
} else {
fmt.Println(err)
return
}
}
lArr := len(arr)
if lArr <= 0 {
return
}
var (
i, num = 0, 2
head = &TreeNode{Val: arr[0], Num: 1}
queue = []*TreeNode{head}
)
// 根据输入还原二叉树
for len(queue) != 0 {
node := queue[0]
queue = queue[1:]
if i++; i < lArr && arr[i] != maxInt {
node.Left = &TreeNode{Val: arr[i], Num: num}
queue = append(queue, node.Left)
num++
}
if i++; i < lArr && arr[i] != maxInt {
node.Right = &TreeNode{Val: arr[i], Num: num}
queue = append(queue, node.Right)
num++
}
}
printTree(head)
}
type TreeNode struct {
Val int // 节点值
Num int // 节点序号,因为节点值可能重复
IsWrite bool // true表示已经将该节点序号和label写入文件
Left *TreeNode
Right *TreeNode
}
func printTree(root *TreeNode) error {
if root == nil {
return nil
}
const dotFile = "tree.dot"
fw, err := os.Create(dotFile)
if err != nil {
return err
}
fw.WriteString(`digraph G {
graph [nodesep=0.1]
node [shape=circle]
edge [arrowhead=vee]
`)
if root.Left != nil || root.Right != nil {
root.IsWrite = true
fmt.Fprintf(fw, " %d [group=%d,label=\"%d\"]\n", root.Num, root.Num, root.Val)
}
printNode(fw, root)
fw.WriteString("}")
fw.Close()
return exec.Command("dot", dotFile, "-Tsvg", "-o"+dotFile+".svg").Run()
}
func printNode(fw io.Writer, root *TreeNode) {
if !root.IsWrite {
fmt.Fprintf(fw, " %d [label=\"%d\"]\n", root.Num, root.Val)
}
target, distance := 0, 0
if root.Left != nil {
leftMax := root
leftDistance := 1
for leftMax.Right != nil {
leftMax = leftMax.Right
leftDistance++
}
// 找到root节点的root.left往下最右边的节点
target = leftMax.Num
distance = leftDistance
if root.Left.Left != nil || root.Left.Right != nil {
root.Left.IsWrite = true // 生成该节点值
fmt.Fprintf(fw, " %d [group=%d,label=\"%d\"]\n", root.Left.Num, root.Left.Num, root.Left.Val)
}
// 生成root指向root.left的关系
fmt.Fprintf(fw, " %d -> %d\n", root.Num, root.Left.Num)
printNode(fw, root.Left)
}
if root.Left != nil || root.Right != nil {
// 弄一个中间节点,隐藏起来,主要是让布局更美观
fmt.Fprintf(fw, " _%d [group=%d,label=\"\",width=0,style=invis]\n", root.Num, root.Num)
fmt.Fprintf(fw, " %d -> _%d [style=invis]\n", root.Num, root.Num)
}
if root.Right != nil {
rightMin := root.Right
rightDistance := 1
for rightMin.Left != nil {
rightMin = rightMin.Left
rightDistance++
}
// 找到root节点的root.Right往下最左边的节点
if rightDistance <= distance {
target = rightMin.Num
distance = rightDistance
}
if root.Right.Left != nil || root.Right.Right != nil {
root.Right.IsWrite = true // 生成该节点值
fmt.Fprintf(fw, " %d [group=%d,label=\"%d\"]\n", root.Right.Num, root.Right.Num, root.Right.Val)
}
// 生成root指向root.Right的关系
fmt.Fprintf(fw, " %d -> %d\n", root.Num, root.Right.Num)
printNode(fw, root.Right)
}
// 一个节点对应的占位节点应该与该节点的左子树的最大节点和右子树的最小节点中距离较近的那一个处于同一层
if distance > 1 && target != 0 {
fmt.Fprintf(fw, " {rank=same;_%d;%d}\n", root.Num, target)
}
}
3. 总结
- 原理的话可以看【别人的解释】
- 首先需要安装【graphviz】
- 然后编写还原二叉树的代码,生成【graphviz】的脚本,然后用dot命令产生svg矢量图
- 在markdow编辑器中使用SVG可以用如下操作
<div width="100%" style="overflow-x: auto;">
<svg width="140" height="170">
<title>SVG Sample</title>
<desc>This is a sample to use SVG in markdown on the website cnblogs.</desc>
<circle cx="70" cy="95" r="50" style="stroke: black; fill: none;"/>
</svg>
</div>
最后由
Janbar 修改于
2020-05-01 15:21