二叉搜索树的迭代器_二叉搜索树 实现iterator

我们经常使用着我们并不熟悉的函数/类,我们只知道它们所提供的接口以及怎样使用。这就像我们开车在马路上，你可能并不知道汽车是如何运行，或许你会说这并不需要知道。但至少知道一些回在车抛锚的时候你能做一些事，而不是抽根烟无所事事等维修队过来（如果路上很挤，你就倒霉了）。
我们也有必要知道问题来源在程序出问题的时侯。

你可能会说你没用过树的迭代器，因为数据库里没有提供树。但是你如果理解map,set的话，它们的底层实现
就是红黑树。它们所使用的迭代器便是红黑树的迭代器。

//rep_type便是红黑树类型。
typedef typename rep_type::iterator iterator;
1
2

实现二叉树的迭代器主要是为了方便我们遍历，以及进行元素修改。使容器可以更好的配合泛型算法。为此二叉树的迭代器至少应该支持递增，递减，！=, -> 等操作符。

我们有2种办法来实现二叉树的迭代器，第一种就是在节点里遍历，第二种是线索化二叉树，

第一种思路：

为了使输出的元素有序，我们默认的都是中序遍历，那么这个树的最左元素就是begin了.

！=。->运算符都很好实现，主要是递增递减我们需要把它的情况都列举出来。

以下情况都不考虑节点为根节点时的情况。
首先是递增（++）
1，当前节点无右子节点时
如果当前节点是父节点的左子节点时，那么父节点便是它的下一个节点。
如果为父节点的右子节点，那么便往上查找，直到不为父节点的右子节点，这时父节点便为下一个节点。

2，当前节点有右节点时。找出右子树的最左节点即可。

递减（— —）
1，当前节点无左节点时
当前节点为父节点的右节点时，父节点即为下一个节点。
当前节点为父节点的左节点时，向上查找，直到节点不为父节点的左子节点，这时父节点既是。

2，当前节点有左节点时，找到左子树的最右节点。

我们这里以stl中红黑树的迭代器为例。stl红黑树设置了一个特殊节点。

//以下列举的都是stl源码，这里只列举有关系的代码
  self& operator++() { increment(); return *this; }
  self operator++(int) {
    self tmp = *this;
    increment();//调用
    return tmp;
  }
  void increment()
  {
  //递增的请况
    if (node->right != 0) {
      node = node->right;
      while (node->left != 0)
        node = node->left;
    }
    else {
      base_ptr y = node->parent;
      while (node == y->right) {
        node = y;
        y = y->parent;
      }
     //若在最右节点++或最左节点--时，就会找到向上找到header。这样就防止了越界情况
      if (node->right != y)
        node = y;
    }
  }

//递减
  void decrement()
  {
    if (node->color == __rb_tree_red &&
        node->parent->parent == node)
      node = node->right;
    else if (node->left != 0) {
      base_ptr y = node->left;
      while (y->right != 0)
        y = y->right;
      node = y;
    }
    else {
      base_ptr y = node->parent;
      while (node == y->left) {
        node = y;
        y = y->parent;
      }
      node = y;
    }
  }

  self& operator--() { decrement(); return *this; }
  self operator--(int) {
    self tmp = *this;
    decrement();
    return tmp;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

其他的符号操作较为简单，这里不在赘述。