go:实现前缀树

• 2019 年 11 月 22 日
• 筆記

url路由的副产品。

package utils    /*  PrefixTree 前缀树  使用姿势：  tree := utils.BuildTree([]string{      "/yuedu/account",      "/yuedu",      "/yuedu/master",  })    fmt.Println(tree.Match("/yuedu"))  fmt.Println(tree.Match("/yuedu/details"))  fmt.Println(tree.Match("/yuedu/account"))  fmt.Println(tree.Match("/yuedu/account/user"))  fmt.Println(tree.Match("/yuedu/master/"))  result:  /yuedu true  /yuedu false  /yuedu/account true  /yuedu/account false  /yuedu/master false  */  type PrefixTree struct {      root *treeNode  }    // BuildTree 生成这棵前缀树  func BuildTree(keys []string) *PrefixTree {      tree := new(PrefixTree)      root := makeNode()      for _, key := range keys {          buildNode(key, root)      }      tree.root = root      return tree  }    // Match 尝试匹配一个Path，返回最终匹配的结果和是否完全匹配  func (t PrefixTree) Match(path string) (string, bool) {      tpnode := t.root      result := ""      for _, pathpart := range path {          _, ok := tpnode.subNode[pathpart]          if !ok {              return result, false          }          tpnode = tpnode.subNode[pathpart]          if tpnode.value != "" {              result = tpnode.value          }      }      return result, tpnode.value != ""  }    type treeNode struct {      subNode map[rune]*treeNode      value   string  }    func makeNode() *treeNode {      node := new(treeNode)      node.subNode = make(map[rune]*treeNode)      return node  }    func buildNode(key string, root *treeNode) {      tpnode := root      for _, keypart := range key {          _, ok := tpnode.subNode[keypart]          if ok {              tpnode = tpnode.subNode[keypart]          } else {              tpnode.subNode[keypart] = makeNode()              tpnode = tpnode.subNode[keypart]          }      }      tpnode.value = key  }