根据层次遍历序列画出二叉树

1.画出如下图片

tree_1.png

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. 总结

  1. 原理的话可以看【别人的解释
  2. 首先需要安装【graphviz
  3. 然后编写还原二叉树的代码,生成【graphviz】的脚本,然后用dot命令产生svg矢量图
  4. 在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>

captcha