Binární strom (Go)

11.1.2019 00:37 | Přečteno: 2041× | Linux | poslední úprava: 11.1.2019 00:32

Zobrazení výšky:

a
 \
  b
   \
    c
     \
      d
       \
        e
         \
          f
           \
            g

a b c d e f g

      d
     / \
    c   e
   /     \
  b       f
 /         \
a           g

d c e b f a g

    d
   / \
  b   f
 / \ / \
a  c e  g

d b f a g c e


Program načte slova se souboru a vypíše je srovnané, včetně jejich četnosti.

package main

import (
    "bufio"
    "fmt"
    "os"
    str "strings"
)

type tree struct {
    word        string
    count       int
    left, right *tree
}

func main() {
    if len(os.Args) < 2 {
        fmt.Println("Missing file argument!")
        os.Exit(1)
    }
    f, err := os.Open(os.Args[1])
    if err != nil {
        fmt.Fprintf(os.Stderr, "err v%\n", err) 
        os.Exit(1)
    }
    line := bufio.NewScanner(f)    
    
    var root *tree
    for line.Scan() {
        words := str.Fields(line.Text())
        for _, w := range words {
            root = add(root, w) 
        }
    }    
    print(root)    
}

func add(t *tree, w string) *tree {
    if t == nil {        
        return &tree{word: w, count: 1}
    }
    if w == t.word {
        t.count++
    } else if w < t.word {        
        t.left = add(t.left, w)    
    } else {        
        t.right = add(t.right, w) 
    }
    return t
}

func print(t *tree) {
    if t != nil {
        print(t.left)
        fmt.Printf("%-20s%d\n", t.word, t.count)
        print(t.right)
    }
}

Funkce Fields rozdělí řádek podle bílých znaků a vrátí jednotlivá slova jako slice řetězců. Funkce print vypisuje slova v abecedním pořadí - prochází stromem in-order.

Takže kdyby soubor obsahoval tento text

A pointer is a variable that
contains the address of a variable.

výpis by vypadal takto:

A                   1
a                   2
address             1
contains            1
is                  1
of                  1
pointer             1
that                1
the                 1
variable            1
variable.           1

       

Komentáře