缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

二叉查找树

  1. 二叉查找树（又叫作二叉搜索树或二叉排序树）是一种数据结构，
  2. 数据存储于二叉查找树的各个结点中。
  4. 二叉查找树有两个性质:
  5. 第一个是每个结点的值均大于其左子树上任意一个结点的值,
  6. 第二个是每个结点的值均小于其右子树上任意一个结点的值。
  8. 根据这两个性质可以得到以下结论。
  9. 首先，二叉查找树的最小结点要从顶端开始，往其左下的末端寻找。
  10. 反过来，二叉查找树的最大结点要从顶端开始，往其右下的末端寻找。
  12. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

目标

  • 实现一棵二叉查找树, 并测试其基本功能

设计

  • IComparator: 定义值比较函数. 值比较函数可以返回小于, 等于, 大于三种情况
  • IBinarySearchTree: 定义二叉查找树的接口, 增删改查都要.
  • IIterator: 定义二叉查找树的遍历接口.
  • tComparator: 值比较函数的包装器, 实现IComparator接口. 具体比较函数由外部传入.
  • tBinarySearchTree: 二叉查找树的示例, 实现IBinarySearchTree接口.
  • tBinaryNode: 二叉查找树节点
  • tBSTreeIterator: 二叉查找树的遍历迭代器, 内部使用广度优先搜索+候选队列.

单元测试

bstree_test.go, 测试二叉查找树的增删改查, 以及大小序输出.

  1. package data_structure
  3. import (
  4.     "fmt"
  5.     bstree "learning/gooop/data_structure/binary_search_tree"
  6.     "math/rand"
  7.     "strings"
  8.     "testing"
  9.     "time"
  10. )
  12. func Test_BinarySearchTree(t *testing.T) {
  13.     fnAssertTrue := func(b bool, msg string) {
  14.         if !b {
  15.             panic(msg)
  16.         }
  17.     }
  19.     fnCompare := func(a interface{}, b interface{}) bstree.CompareResult {
  20.         i1 := a.(int)
  21.         i2 := b.(int)
  23.         if i1 < i2 {
  24.             return bstree.LESS
  25.         } else if i1 == i2 {
  26.             return bstree.EQUAL
  27.         } else {
  28.             return bstree.GREATER
  29.         }
  30.     }
  31.     comparator := bstree.NewComparator(fnCompare)
  33.     // test empty tree
  34.     tree := bstree.NewBinarySearchTree(comparator)
  35.     t.Log(tree)
  36.     fnAssertTrue(tree.String() == "r=nil,s=0,v=0", "expecting r=nil,s=0,v=0")
  37.     fnAssertTrue(tree.Size() == 0, "expecting size == 0")
  38.     fnAssertTrue(tree.IsEmpty(), "expecting empty")
  40.     // test one item
  41.     tree.Push(5)
  42.     t.Log(tree)
  43.     fnAssertTrue(tree.String() == "r=5,s=1,v=1 5(n,n)", "expecting r=5,s=1,v=1 5(n,n)")
  44.     fnAssertTrue(tree.Size() == 1, "expecting size == 1")
  45.     fnAssertTrue(tree.IsNotEmpty(), "expecting not empty")
  47.     // test min
  48.     ok, v := tree.Min()
  49.     fnAssertTrue(ok, "expecting min() ok")
  50.     fnAssertTrue(v == 5, "expecting 5")
  52.     // test max
  53.     ok, v = tree.Max()
  54.     fnAssertTrue(ok, "expecting max() ok")
  55.     fnAssertTrue(v == 5, "expecting 5")
  56.     fnAssertTrue(tree.String() == "r=5,s=1,v=1 5(n,n)", "expecting r=5,s=1,v=1 5(n,n)")
  58.     // test pop one
  59.     ok, v = tree.PopMin()
  60.     t.Log(tree)
  61.     fnAssertTrue(tree.String() == "r=nil,s=0,v=2", "expecting r=nil,s=0,v=2")
  62.     fnAssertTrue(ok, "expecting PopMin() ok")
  63.     fnAssertTrue(v == 5, "expecting 5")
  64.     fnAssertTrue(tree.Size() == 0, "expecting size == 0")
  65.     fnAssertTrue(tree.IsEmpty(), "expecting empty")
  67.     // test batch push
  68.     samples := []int{ 5,4,8, 2, 7, 9, 1,3,6 }
  69.     for i := 0;i < len(samples);i++ {
  70.         tree.Push(samples[i])
  71.     }
  72.     t.Log(tree)
  73.     fnAssertTrue(tree.Size() == len(samples), "expecting Size() == len(samples)")
  74.     fnAssertTrue(tree.String() == "r=5,s=9,v=11 5(4,8),4(2,n),8(7,9),2(1,3),7(6,n),9(n,n),1(n,n),3(n,n),6(n,n)", "expecting r=5,s=9,v=11 5(4,8),4(2,n),8(7,9),2(1,3),7(6,n),9(n,n),1(n,n),3(n,n),6(n,n)")
  76.     for _,it := range samples {
  77.         fnAssertTrue(tree.Has(it), "expecting Has() == true")
  78.     }
  80.     // test iterator
  81.     iter := tree.Iterator()
  82.     fnAssertTrue(iter.More(), "expectiong More()")
  83.     iterItems := make([]string, 0)
  84.     for range samples {
  85.         ok,v = iter.Next()
  86.         t.Logf("ok=%v, v=%v", true, v)
  87.         fnAssertTrue(ok, "expectiong Next()")
  88.         iterItems = append(iterItems, fmt.Sprintf("%v", v))
  89.     }
  90.     fnAssertTrue(strings.Join(iterItems, ",") == "5,4,8,2,7,9,1,3,6", "expecting 5,4,8,2,7,9,1,3,6")
  91.     fnAssertTrue(iter.More() == false, "expectiong !iter.More()")
  92.     ok,v = iter.Next()
  93.     fnAssertTrue(!ok, "expecting !iter.Next()")
  95.     // test min
  96.     ok,v = tree.Min()
  97.     fnAssertTrue(ok, "expecting ok")
  98.     fnAssertTrue(v == 1, "expection Min() == 1")
  100.     // test max
  101.     ok,v = tree.Max()
  102.     fnAssertTrue(ok, "expecting ok")
  103.     fnAssertTrue(v == 9, "expection Max() == 9")
  105.     // test batch pop min
  106.     for i := 1;i <= 9;i ++ {
  107.         ok,v = tree.PopMin()
  108.         t.Logf("i=%v v=%v tree=%s", i, v, tree.String())
  109.         fnAssertTrue(ok, "expecting ok")
  110.         fnAssertTrue(v == i, fmt.Sprintf("expecting %v", i))
  111.     }
  113.     // test batch pop max
  114.     for i := 0;i < len(samples);i++ {
  115.         tree.Push(samples[i])
  116.     }
  117.     t.Log(tree)
  118.     for i := 1;i <= 9;i ++ {
  119.         ok,v = tree.PopMax()
  120.         t.Logf("i=%v v=%v tree=%s", i, v, tree.String())
  121.         fnAssertTrue(ok, "expecting ok")
  122.         fnAssertTrue(v == 10 - i, fmt.Sprintf("expecting %v", 10 - i))
  123.     }
  125.     // test batch push
  126.     samples = []int{ 2,1,3 }
  127.     for i := 0;i < len(samples);i++ {
  128.         tree.Push(samples[i])
  129.     }
  130.     t.Log(tree)
  131.     fnAssertTrue(tree.String() == "r=2,s=3,v=41 2(1,3),1(n,n),3(n,n)", "expecting 2(1,3),1(n,n),3(n,n)")
  133.     // test clear
  134.     tree.Clear()
  135.     t.Log(tree)
  136.     fnAssertTrue(tree.String() == "r=nil,s=0,v=42", "expecting empty")
  138.     // test batch remove
  139.     rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
  140.     rndItems := make(map[int]bool, 0)
  141.     for i := 0;i < 10000;i++ {
  142.         x := rnd.Intn(50000)
  143.         tree.Push(x)
  144.         rndItems[x] = true
  145.     }
  146.     for k,_ := range rndItems {
  147.         //t.Logf("removing %v", k)
  148.         fnAssertTrue(tree.Remove(k), "expecting Remove() = true")
  149.         //t.Log(tree)
  150.     }
  151.     t.Log(tree)
  152.     fnAssertTrue(tree.IsEmpty(), "expecting empty")
  153. }

测试输出

  1. $ go test -v bstree_test.go 
  2. === RUN   Test_BinarySearchTree
  3.     bstree_test.go:35: r=nil,s=0,v=0
  4.     bstree_test.go:42: r=5,s=1,v=1 5(n,n)
  5.     bstree_test.go:60: r=nil,s=0,v=2
  6.     bstree_test.go:72: r=5,s=9,v=11 5(4,8),4(2,n),8(7,9),2(1,3),7(6,n),9(n,n),1(n,n),3(n,n),6(n,n)
  7.     bstree_test.go:86: ok=true, v=5
  8.     bstree_test.go:86: ok=true, v=4
  9.     bstree_test.go:86: ok=true, v=8
  10.     bstree_test.go:86: ok=true, v=2
  11.     bstree_test.go:86: ok=true, v=7
  12.     bstree_test.go:86: ok=true, v=9
  13.     bstree_test.go:86: ok=true, v=1
  14.     bstree_test.go:86: ok=true, v=3
  15.     bstree_test.go:86: ok=true, v=6
  16.     bstree_test.go:108: i=1 v=1 tree=r=5,s=8,v=12 5(4,8),4(2,n),8(7,9),2(n,3),7(6,n),9(n,n),3(n,n),6(n,n)
  17.     bstree_test.go:108: i=2 v=2 tree=r=5,s=7,v=13 5(4,8),4(3,n),8(7,9),3(n,n),7(6,n),9(n,n),6(n,n)
  18.     bstree_test.go:108: i=3 v=3 tree=r=5,s=6,v=14 5(4,8),4(n,n),8(7,9),7(6,n),9(n,n),6(n,n)
  19.     bstree_test.go:108: i=4 v=4 tree=r=5,s=5,v=15 5(n,8),8(7,9),7(6,n),9(n,n),6(n,n)
  20.     bstree_test.go:108: i=5 v=5 tree=r=8,s=4,v=16 8(7,9),7(6,n),9(n,n),6(n,n)
  21.     bstree_test.go:108: i=6 v=6 tree=r=8,s=3,v=17 8(7,9),7(n,n),9(n,n)
  22.     bstree_test.go:108: i=7 v=7 tree=r=8,s=2,v=18 8(n,9),9(n,n)
  23.     bstree_test.go:108: i=8 v=8 tree=r=9,s=1,v=19 9(n,n)
  24.     bstree_test.go:108: i=9 v=9 tree=r=nil,s=0,v=20
  25.     bstree_test.go:117: r=5,s=9,v=29 5(4,8),4(2,n),8(7,9),2(1,3),7(6,n),9(n,n),1(n,n),3(n,n),6(n,n)
  26.     bstree_test.go:120: i=1 v=9 tree=r=5,s=8,v=30 5(4,8),4(2,n),8(7,n),2(1,3),7(6,n),1(n,n),3(n,n),6(n,n)
  27.     bstree_test.go:120: i=2 v=8 tree=r=5,s=7,v=31 5(4,7),4(2,n),7(6,n),2(1,3),6(n,n),1(n,n),3(n,n)
  28.     bstree_test.go:120: i=3 v=7 tree=r=5,s=6,v=32 5(4,6),4(2,n),6(n,n),2(1,3),1(n,n),3(n,n)
  29.     bstree_test.go:120: i=4 v=6 tree=r=5,s=5,v=33 5(4,n),4(2,n),2(1,3),1(n,n),3(n,n)
  30.     bstree_test.go:120: i=5 v=5 tree=r=4,s=4,v=34 4(2,n),2(1,3),1(n,n),3(n,n)
  31.     bstree_test.go:120: i=6 v=4 tree=r=2,s=3,v=35 2(1,3),1(n,n),3(n,n)
  32.     bstree_test.go:120: i=7 v=3 tree=r=2,s=2,v=36 2(1,n),1(n,n)
  33.     bstree_test.go:120: i=8 v=2 tree=r=1,s=1,v=37 1(n,n)
  34.     bstree_test.go:120: i=9 v=1 tree=r=nil,s=0,v=38
  35.     bstree_test.go:130: r=2,s=3,v=41 2(1,3),1(n,n),3(n,n)
  36.     bstree_test.go:135: r=nil,s=0,v=42
  37.     bstree_test.go:151: r=nil,s=0,v=18146
  38. --- PASS: Test_BinarySearchTree (0.01s)
  39. PASS
  40. ok      command-line-arguments  0.012s

IComparator.go

定义值比较函数. 值比较函数可以返回小于, 等于, 大于三种情况

  1. package binary_search_tree
  3. type IComparator interface {
  4.     Compare(a interface{}, b interface{}) CompareResult
  5. }
  7. type CompareResult int
  8. const LESS CompareResult = -1
  9. const EQUAL CompareResult = 0
  10. const GREATER CompareResult = 1

IBinarySearchTree.go

定义二叉查找树的接口, 增删改查都要.

  1. package binary_search_tree
  3. type IBinarySearchTree interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Push(value interface{})
  9.     Min() (bool, interface{})
  10.     Max() (bool, interface{})
  11.     Has(value interface{}) bool
  12.     PopMin() (bool, interface{})
  13.     PopMax() (bool, interface{})
  14.     Remove(value interface{}) bool
  15.     Clear()
  17.     Iterator() IIterator
  18.     String() string
  19. }

IIterator.go

定义二叉查找树的遍历接口.

  1. package binary_search_tree
  3. type IIterator interface {
  4.     More() bool
  5.     Next() (bool,interface{})
  6. }

tComparator.go

值比较函数的包装器, 实现IComparator接口. 具体比较函数由外部传入.

  1. package binary_search_tree
  3. import "errors"
  5. type FnCompare func(a interface{}, b interface{}) CompareResult
  7. type tComparator struct {
  8.     fnCompare FnCompare
  9. }
  11. func NewComparator(fn FnCompare) IComparator {
  12.     if fn == nil {
  13.         panic(gNullArgumentError)
  14.     }
  16.     return &tComparator{
  17.         fnCompare: fn,
  18.     }
  19. }
  21. func (me *tComparator) Compare(a interface{}, b interface{}) CompareResult {
  22.     if a == nil || b == nil {
  23.         panic(gNullArgumentError)
  24.     }
  25.     return me.fnCompare(a, b)
  26. }
  28. var gNullArgumentError = errors.New("null argument error")

tBinarySearchTree.go

二叉查找树的示例, 实现IBinarySearchTree接口. 

  1. package binary_search_tree
  3. import (
  4.     "fmt"
  5.     "strings"
  6. )
  8. type tBinarySearchTree struct {
  9.     comparator IComparator
  10.     root       *tBinaryNode
  11.     size       int
  12.     version    uint64
  13. }
  15. func NewBinarySearchTree(comparator IComparator) IBinarySearchTree {
  16.     return &tBinarySearchTree{
  17.         comparator: comparator,
  18.         root:       nil,
  19.         size:       0,
  20.         version:    0,
  21.     }
  22. }
  24. func (me *tBinarySearchTree) Size() int {
  25.     return me.size
  26. }
  28. func (me *tBinarySearchTree) IsEmpty() bool {
  29.     return me.size <= 0
  30. }
  32. func (me *tBinarySearchTree) IsNotEmpty() bool {
  33.     return !me.IsEmpty()
  34. }
  36. func (me *tBinarySearchTree) Push(value interface{}) {
  37.     if me.IsEmpty() {
  38.         me.root = me.append(value)
  39.         return
  40.     }
  42.     for node := me.root; node != nil; {
  43.         r := me.comparator.Compare(value, node.value)
  45.         switch r {
  46.         case EQUAL:
  47.             return
  49.         case LESS:
  50.             if node.left == nil {
  51.                 node.LChild(me.append(value))
  52.                 return
  53.             } else {
  54.                 node = node.left
  55.             }
  56.             break
  58.         case GREATER:
  59.             if node.right == nil {
  60.                 node.RChild(me.append(value))
  61.                 return
  62.             } else {
  63.                 node = node.right
  64.             }
  65.             break
  66.         }
  67.     }
  68. }
  70. func (me *tBinarySearchTree) append(value interface{}) *tBinaryNode {
  71.     me.size++
  72.     me.version++
  73.     return newBinaryNode(value)
  74. }
  76. func (me *tBinarySearchTree) Min() (bool, interface{}) {
  77.     ok, node := me.getMinNode(me.root)
  78.     if !ok {
  79.         return false, nil
  80.     }
  81.     return true, node.value
  82. }
  84. func (me *tBinarySearchTree) Max() (bool, interface{}) {
  85.     ok, node := me.getMaxNode(me.root)
  86.     if !ok {
  87.         return false, nil
  88.     }
  89.     return true, node.value
  90. }
  93. func (me *tBinarySearchTree) Has(value interface{}) bool {
  94.     ok, _ := me.find(value)
  95.     return ok
  96. }
  98. func (me *tBinarySearchTree) find(value interface{}) (ok bool, node *tBinaryNode) {
  99.     if me.IsEmpty() {
  100.         return false, nil
  101.     }
  103.     for node = me.root; node != nil; {
  104.         r := me.comparator.Compare(value, node.value)
  106.         switch r {
  107.         case EQUAL:
  108.             return true, node
  110.         case LESS:
  111.             if node.left == nil {
  112.                 return false, nil
  113.             } else {
  114.                 node = node.left
  115.             }
  116.             break
  118.         case GREATER:
  119.             if node.right == nil {
  120.                 return false, nil
  121.             } else {
  122.                 node = node.right
  123.             }
  124.             break
  125.         }
  126.     }
  128.     return false, nil
  129. }
  132. func (me *tBinarySearchTree) getMinNode(from *tBinaryNode) (ok bool, left *tBinaryNode) {
  133.     if from == nil {
  134.         return false, nil
  135.     }
  137.     left = from.left
  138.     if left == nil {
  139.         return true, from
  140.     }
  142.     for {
  143.         if left.left == nil {
  144.             return true, left
  145.         }
  147.         left = left.left
  148.     }
  149. }
  151. func (me *tBinarySearchTree) getMaxNode(from *tBinaryNode) (ok bool, right *tBinaryNode) {
  152.     if from == nil {
  153.         return false, nil
  154.     }
  156.     right = from.right
  157.     if right == nil {
  158.         return true, from
  159.     }
  161.     for {
  162.         if right.right == nil {
  163.             return true, right
  164.         }
  166.         right = right.right
  167.     }
  168. }
  170. func (me *tBinarySearchTree) PopMin() (bool, interface{}) {
  171.     ok, node := me.getMinNode(me.root)
  172.     if !ok {
  173.         return false, nil
  174.     }
  175.     value := node.value
  177.     me.removeNode(node)
  179.     me.size--
  180.     me.version++
  182.     return true, value
  183. }
  186. func (me *tBinarySearchTree) removeNode(node *tBinaryNode) {
  187.     //var pv interface{} = "nil"
  188.     //if node.parent != nil {
  189.     //    pv = node.parent.value
  190.     //}
  191.     //fmt.Printf("removeNode %v.%v\n", pv, node.value)
  193.     left := node.left
  194.     right := node.right
  196.     if node.parent == nil {
  197.         switch node.childrenCount() {
  198.         case 0:
  199.             me.root = nil
  200.             break
  202.         case 1:
  203.             if left != nil {
  204.                 me.root = left
  205.                 left.SetParent(nil)
  206.             } else if right != nil {
  207.                 me.root = right
  208.                 right.SetParent(nil)
  209.             }
  211.         default:
  212.             _, n := me.getMaxNode(left)
  213.             if n == left {
  214.                 me.root = n
  215.                 n.SetParent(nil)
  216.                 n.RChild(right)
  218.             } else {
  219.                 me.root.value = n.value
  220.                 me.removeNode(n)
  221.             }
  222.         }
  224.     } else {
  225.         parent := node.parent
  227.         switch node.childrenCount() {
  228.         case 0:
  229.             if parent.left == node {
  230.                 parent.left = nil
  231.             } else {
  232.                 parent.right = nil
  233.             }
  234.             break
  236.         case 1:
  237.             if left != nil {
  238.                 if parent.left == node {
  239.                     parent.LChild(left)
  240.                 } else {
  241.                     parent.RChild(left)
  242.                 }
  243.             } else if right != nil {
  244.                 if parent.left == node {
  245.                     parent.LChild(right)
  246.                 } else {
  247.                     parent.RChild(right)
  248.                 }
  249.             }
  251.         default:
  252.             _, n := me.getMaxNode(left)
  253.             if n == left {
  254.                 if parent.left == node {
  255.                     parent.LChild(n)
  256.                 } else {
  257.                     parent.RChild(n)
  258.                 }
  259.                 n.RChild(right)
  261.             } else {
  262.                 node.value = n.value
  263.                 me.removeNode(n)
  264.             }
  265.         }
  266.     }
  267. }
  269. func (me *tBinarySearchTree) PopMax() (bool, interface{}) {
  270.     ok, node := me.getMaxNode(me.root)
  271.     if !ok {
  272.         return false, nil
  273.     }
  275.     me.removeNode(node)
  277.     me.size--
  278.     me.version++
  280.     return true, node.value
  281. }
  283. func (me *tBinarySearchTree) Remove(value interface{}) bool {
  284.     ok, node := me.find(value)
  285.     if !ok {
  286.         return false
  287.     }
  289.     me.removeNode(node)
  291.     me.size--
  292.     me.version++
  294.     return true
  295. }
  297. func (me *tBinarySearchTree) Clear() {
  298.     if me.IsEmpty() {
  299.         return
  300.     }
  302.     me.root = nil
  303.     me.size = 0
  304.     me.version++
  305. }
  307. func (me *tBinarySearchTree) Iterator() IIterator {
  308.     return newBSTreeIterator(me)
  309. }
  311. func (me *tBinarySearchTree) String() string {
  312.     queue := newVisitQeuue()
  313.     queue.push(me.root)
  315.     items := make([]string, 0)
  316.     for ;queue.more(); {
  317.         ok, node := queue.poll()
  318.         if ok {
  319.             queue.push(node.left)
  320.             queue.push(node.right)
  322.             var lv interface{} = "n"
  323.             if node.left != nil {
  324.                 lv = node.left.value
  325.             }
  326.             var rv interface{} = "n"
  327.             if node.right != nil {
  328.                 rv = node.right.value
  329.             }
  330.             items = append(items, fmt.Sprintf("%v(%v,%v)", node.value, lv,rv))
  332.         } else {
  333.             break
  334.         }
  335.     }
  337.     r := "nil"
  338.     if me.root != nil {
  339.         r = fmt.Sprintf("%v", me.root.value)
  340.     }
  342.     if len(items) > 0 {
  343.         return fmt.Sprintf("r=%v,s=%v,v=%v %s", r, me.size, me.version, strings.Join(items, ","))
  344.     } else {
  345.         return fmt.Sprintf("r=%v,s=%v,v=%v", r, me.size, me.version)
  346.     }
  347. }

tBinaryNode.go

二叉查找树节点

  1. package binary_search_tree
  3. type tBinaryNode struct {
  4.     value interface{}
  5.     parent *tBinaryNode
  6.     left *tBinaryNode
  7.     right *tBinaryNode
  8. }
  10. func newBinaryNode(value interface{}) *tBinaryNode {
  11.     return &tBinaryNode{
  12.         value: value,
  13.         left: nil,
  14.         right: nil,
  15.     }
  16. }
  18. func (me *tBinaryNode) childrenCount() int {
  19.     left := me.left
  20.     right := me.right
  22.     if left == nil && right == nil {
  23.         return 0
  24.     }
  26.     if left == nil || right == nil {
  27.         return 1
  28.     }
  30.     return 2
  31. }
  33. func (me *tBinaryNode) LChild(node *tBinaryNode) {
  34.     me.left = node
  35.     if node != nil {
  36.         node.SetParent(me)
  37.     }
  38. }
  40. func (me *tBinaryNode) SetParent(parent *tBinaryNode) {
  41.     if me.parent == parent {
  42.         return
  43.     }
  45.     if me.parent != nil {
  46.         if me.parent.left == me {
  47.             me.parent.left = nil
  48.         } else if me.parent.right == me {
  49.             me.parent.right = nil
  50.         }
  51.     }
  53.     me.parent = parent
  54. }
  56. func (me *tBinaryNode) RChild(node *tBinaryNode) {
  57.     me.right = node
  58.     if node != nil {
  59.         node.SetParent(me)
  60.     }
  61. }

tBSTreeIterator.go

二叉查找树的遍历迭代器, 内部使用广度优先搜索+候选队列.

  1. package binary_search_tree
  3. type tBSTreeIterator struct {
  4.     tree *tBinarySearchTree
  5.     queue *tVisitQueue
  6.     version uint64
  7. }
  10. type tVisitQueue struct {
  11.     head *tQueuedNode
  12.     tail *tQueuedNode
  13. }
  15. type tQueuedNode struct {
  16.     node *tBinaryNode
  17.     next *tQueuedNode
  18. }
  20. func newQueuedNode(node *tBinaryNode) *tQueuedNode {
  21.     return &tQueuedNode{
  22.         node: node,
  23.         next: nil,
  24.     }
  25. }
  27. func newVisitQeuue() *tVisitQueue {
  28.     return &tVisitQueue{
  29.         nil,
  30.         nil,
  31.     }
  32. }
  34. func (me *tVisitQueue) push(node *tBinaryNode) {
  35.     if node == nil {
  36.         return
  37.     }
  39.     qn := newQueuedNode(node)
  40.     if me.head == nil {
  41.         me.head = qn
  42.         me.tail = qn
  43.     } else {
  44.         me.tail.next = qn
  45.         me.tail = qn
  46.     }
  47. }
  49. func (me *tVisitQueue) poll() (bool, *tBinaryNode) {
  50.     if me.head == nil {
  51.         return false, nil
  53.     } else {
  54.         it := me.head
  55.         if it == me.tail {
  56.             me.tail = nil
  57.         }
  58.         me.head = me.head.next
  59.         return true, it.node
  60.     }
  61. }
  63. func (me *tVisitQueue) more() bool {
  64.     return me.head != nil
  65. }
  67. func newBSTreeIterator(tree *tBinarySearchTree) IIterator {
  68.     it := &tBSTreeIterator{
  69.         tree: tree,
  70.         queue: newVisitQeuue(),
  71.         version: tree.version,
  72.     }
  73.     it.queue.push(tree.root)
  74.     return it
  75. }
  77. func (me *tBSTreeIterator) More() bool {
  78.     if me.version != me.tree.version {
  79.         return false
  80.     } else {
  81.         return me.queue.more()
  82.     }
  83. }
  85. func (me *tBSTreeIterator) Next() (bool, interface{}) {
  86.     if !me.More() {
  87.         return false, nil
  88.     }
  90.     ok, node := me.queue.poll()
  91.     if !ok {
  92.         return false, nil
  93.     }
  95.     me.queue.push(node.left)
  96.     me.queue.push(node.right)
  97.     return true, node.value
  98. }

(end)