行为型 迭代器模式

为什么需要迭代器模式模式

迭代器在很多语言都会提供，主要作用就是用来里边集合（容器）对象，可以是数组、链表各种树。

采用迭代器可以封装遍历方法，如果是图、树这些数据结构，最好采用迭代器模式来进行封装，避免客户端自行去实现造成错误。

每个迭代器独享一份下标信息，多个迭代器同时访问容器不会造成影响。

实现

大家可以顺利考虑一下王争（我推荐的极客时间）说的快照实现。

写这个需要注意Next的关系，很容易写错。我这里起始点不是在0那里，而是在root那里，需要第一次调用后才到0那个位置。

go.mod

module iterator

go 1.13

iterator.go

package iterator

type TreeNode struct {
	Left  *TreeNode
	Right *TreeNode
	Value int
}

func NewNode(value int) *TreeNode {
	return &TreeNode{
		Value: value,
	}
}

func (node *TreeNode) Iterator() Iterator {
	return &MorrisInOrderIterator{
		node: node,
	}
}

type Iterator interface {
	HasNext() bool
	Next() int
	Cur() int
}

// InInOrderIterator is implemented in a morris way which will actually modify the tree structure.
type MorrisInOrderIterator struct {
	node *TreeNode
}

func (it *MorrisInOrderIterator) HasNext() bool {
	return it.node != nil
}

func (it *MorrisInOrderIterator) Cur() int {
	return it.node.Value
}

func (it *MorrisInOrderIterator) Next() int {
	var res int
	cur := it.node
	for cur != nil {
		left := cur.Left
		if left == nil {
			res = cur.Value
			cur = cur.Right
			break
		} else {
			for left.Right != nil && left.Right != cur {
				left = left.Right
			}
			if left.Right == cur {
				res = cur.Value
				cur = cur.Right
				left.Right = nil
				break
			} else {
				left.Right = cur
				cur = cur.Left
			}
		}
	}

	it.node = cur

	return res
}

iterator_test.go

package iterator_test

import (
	"fmt"
	"iterator"
	"testing"
)

func TestIterator(t *testing.T) {
	root := iterator.NewNode(3)
	node1 := iterator.NewNode(1)
	node2 := iterator.NewNode(0)
	node3 := iterator.NewNode(2)
	node4 := iterator.NewNode(4)
	root.Left = node1
	node1.Left = node2
	node1.Right = node3
	root.Right = node4

	it := root.Iterator()
	for i := 0; i < 5; i++ {
		if !it.HasNext() {
			t.Fatal("Error ended HasNext()", it.Cur())
		}
		cur := it.Next()
		fmt.Println("Debug:", cur)
		if cur != i {
			t.Fatal(fmt.Sprintf("Expecting %d but got %d", i, cur))
		}
	}
}

执行： go test iterator -v