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

目录
  • 题目
  • 源代码
  • 做题思路
  • 扩展
    • 左右并列展示
    • 上下并列展示
  • 总结回顾

题目

以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树: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语言 二叉树可视化内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 利用go语言判断是否是完全二叉树

    目录 一.什么是完全二叉树? 二.流程 三.代码 1.树节点 2.测试代码 3.判断树是否为完全二叉树代码 4.代码解读 5.运行结果 一.什么是完全二叉树? 先看如下这一张图: 这个一颗二叉树,如何区分该树是不是完全二叉树呢? 当一个节点存在右子节点但是不存在左子节点这颗树视为非完全二叉树 当一个节点的左子节点存在但是右子节点不存在视为完全二叉树 如果没有子节点,那也是要在左侧开始到右侧依次没有子节点才视为完全二叉树,就像上图2中 而上面第一张图这颗二叉树很明显是一颗非完全二叉树,因为在第三层

  • 利用go语言实现查找二叉树中的最大宽度

    目录 介绍 流程 代码 二叉树结构体 测试代码 查找二叉树最大宽度的代码 代码解读 介绍 这道题是这样的,有一个二叉树,让求出这颗Bt树里面最大的宽度是有几个节点,同时还要求出最大宽度的这些节点在第几层? 比如:下面这颗树,它每层最大的宽度是3,所在的层数是在第3层 流程 这个题主要是使用队列的方式来存储需要遍历的节点 同时还需要几个变量来存储最大的宽度(maxWidth).每层有几个节点(count).最大宽度所在的层(maxInrow).当前层最后一个节点(currentRowEndNode

  • go语言实现二叉树的序例化与反序列化

    目录 二叉树的反序列化 反序列化 解题思路 TreeNode结构体 反序列化方法 代码解读 二叉树的序列化 介绍 解题思路 代码 代码解读 运行结果 二叉树的反序列化 反序列化 树的反序列化故名知意就是将一个序列化成字符串或者其它形式的数据重新的生成一颗二叉树,如下这颗二叉树将它序列化成字符串后的结果[5,4,null,null,3,2,1],而现在要做的是要将这个字符串重新的生成一颗二叉树(生成下面这颗树,因为这个字符串就是通过这颗树序列化来的). 解题思路 首先,应该先拿到一个序列化后数据,

  • 详解Go语言如何实现二叉树遍历

    目录 1. 二叉树的定义 2. 前序遍历 3. 中序遍历 4. 后序遍历 1. 二叉树的定义 二叉树需满足的条件 ① 本身是有序树 ② 树中包含的各个节点的长度不能超过2,即只能是0.1或者2 2. 前序遍历 前序遍历二叉树的顺序:根——>左——>右 package main import "fmt" //定义结构体 type Student struct { Name string Age int Score float32 left *Student //左子树指针 r

  • Go 数据结构之二叉树详情

    目录 Go 语言实现二叉树 定义二叉树的结构 二叉树遍历 创建二叉树 插入值 测试 前言: 树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同. 而在其中最常用的树之一是二叉树. 二叉树是一棵树,其中每个节点最多可以有两个孩子. 一个孩子被识别为左孩子,另一个孩子被识别为右孩子. 二叉树是一种数据结构,在每个节点下面最多存在两个其他节点.即一个节点要么连接至一个.两个节点或不连接其他节点. 树形结构的深度(也被称作高度)则被定义为根节点为根节点

  • Go语言数据结构之二叉树必会知识点总结

    目录 前言 二叉树概念 二叉树的性质 创建二叉树 树的遍历 前序遍历(V-L-R) 中序遍历(L-V-R) 后序遍历(L-R-V) 前言 如果你是一个开发人员,或多或少对树型结构都有一定的认识,我个人对树型数据结构是又爱又恨.二叉树作为树的一种,是一种重要的数据结构,也是面试官经常考的东西.这篇文章主要分享下关于二叉树相关的知识点,并用go语言实现一个二叉树和对二叉树进行遍历. 二叉树概念 二叉树是具有两个节点的树形结构,通常左边的子树被称为左子树,右边的子树称为右子树,图示如下: 在代码中我们

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

    目录 题目 源代码 做题思路 扩展 左右并列展示 上下并列展示 总结回顾 题目 以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3 源代码 package main import ( "fmt" "io" "os" "os/exec" "strconv" "strings" ) type any = interface{} type btNode struc

  • C语言 链式二叉树结构详解原理

    目录 前言 二叉树节点声明 二叉树的遍历 构建二叉树 1.前序遍历 2.中序遍历 3.后序遍历 二叉树节点的个数 二叉树叶子节点的个数 二叉树第K层节点个数 二叉树的高度/深度 二叉树查找值为x的节点 整体代码 前言 二叉树不同于顺序表,一颗普通的二叉树是没有增删改查的意义.普通的二叉树用来存储数据是不方便的.但是二叉树的一些基本实现结构,例如前序遍历,中序遍历...等等都是对我们学习更深层次的二叉树打下夯实的基础. 二叉树节点声明 typedef char BTDataType; typede

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • C语言数据结构之二分法查找详解

    问题:在有序数组中查找给定元素的下标goal. 在查找一个数组元素的下标,可以用循环来解决,但是如果一个数足够大,比如说手机的价格,用循环来查找,就相当于叫一个人猜,从0开始,需要猜很久.这时候就出现了二分查找,也叫对半查找. 对半查找顾名思义就是猜一次,下次猜的内容就减少一半              这时候定义一个变量left表示最左边元素的下标,在定义一个right表示最右边元素的下标,而mid就表示中间元素的下标. 当中间值小于目标值,left重新定义. if (mid < goal)

  • C语言数据结构哈希表详解

    /* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其

  • Python数据结构之递归可视化详解

    目录 1.学习目标 2.递归的调用 3.递归可视化 3.1 turtle 库简介 3.1 递归绘图 1.学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数.递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题.虽然使用递归可以快速的解决一些难题,但由于递归的抽象性,使递归难以掌握.为了更好的理解递归函数背后的思想,本节主要通过可视化方式来了解递归函数的执行步骤. 通过本节学习,应掌握以下内容: 提高对递归的理解 利用可视化理解递归函数背后的思想 2.递归的调

  • Go语言数据结构之插入排序示例详解

    目录 插入排序 动画演示 Go 代码实现 总结 插入排序 插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法. 思想: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置.重复该过程,直到所有输入元素都被选择一次,排序结束. 插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里:抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边. 因此,对所有的牌重复这样的操作,所以每一次都是插

  • C语言数据结构之队列算法详解

    目录 一.前言 二.基本概念 三.顺序队列 四.链队列 五.循环队列 六.总结与提高 一.前言 队列在程序设计中经常出现,如:操作系统中的排队问题. 这篇文章主要介绍了队列的基本概念.性质,顺序.链.循环三种不同的方法实现队列,顺序和循环队列在算法中比较常用 二.基本概念    定义:队列是允许在一端插入,另一端删除的线性表 队头(front):允许删除的一端 队尾(rear):允许插入的一端 特点:先进先出 三.顺序队列 动态图: 算法讲解:  图解:入队,rear++,出队,front++

  • C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • 用C语言递归实现火车调度算法详解

    目录 1.代码 2.代码详解 3.用二叉树表示调用过程 4.思维导图 笔者在李云清版的<数据结构>中第二章遇到了这道经典的火车调度题,经过对一些前辈的代码进行学习,以下将这段火车代码进行分析详解,不对之处,还请各位大佬指示,不胜感激! 1.代码 题目如下: 2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站,可能得到的调度结果有哪些?如果有n列火车通过调度站,请设计一个算法,输出所有可能的调度结果. 算法运用的思想是运用栈+递归,算法的难点也在于此.先上代码: #include &l

随机推荐