[Data Structure] During the secondary line of the binary tree, a iterator is realized to traverse the binary tree.

1. Create a node of the binary tree

#pragma once #include#includeusing namespace std;enum PointerTag{ THREND, LINK,};templatestruct BinaryTreeThdNode{ typedef BinaryTreeThdNode Node; BinaryTreeThdNode(T data) :_data(data), _left (NULL), _right(NULL),_father(NULL), _leftTag(LINK), _rightTag(LINK) () T _data; Node* _left; Node* _right; Node* _father; //Set for the traversal of subsequent threading Parent pointer, here you can ignore PointerTag _leftTag; PointerTag _rightTag;};

2. Create a binary tree

templateclass BinaryTreeThd{public: typedef BinaryTreeThdNode Node; typedef TreeIterator Iterator; BinaryTreeThd() {} BinaryTreeThd(T * arr, size_t size, T invalid) //non-recursive tree creation {stack s; size_t index = 0; Node* cur = NULL; while (index _left = new Node(arr[index++]); //Create a left node Node* tmp = cur; cur = cur->_left; cur->_father = tmp;} s.push(cur);} index++; Node* top = s.top(); s.pop (); if ((index_right = new Node(arr[index++]); //Create right node Node* tmp = cur ; cur = cur->_right; cur->_father = tmp; s.push(cur);}} }private: Node* _root;}

/*******************In-order clueing recursive implementation* *******************/ void InorderThreading() {Node* prev = NULL; _InorderThreading(_root, prev);} void _InorderThreading(Node* cur,Node*& prev ) {if (cur == NULL) return; _InorderThreading(cur->_left, prev); //recursively thread the left subtree if (cur->_left == NULL) {cur->_leftTag = THREND; cur-> _left = prev;} if (prev && (prev->_right == NULL)) {prev->_rightTag = THREND; prev->_right = cur;} prev = cur; _InorderThreading(cur->_right, prev); //recursive threading of the right child Tree }

/**************In-order clueing non-recursive Implement **********************/void InorderThreading() {Node* cur = _root; Node* prev = NULL; stack s; while ( cur || !s.empty()) {while (cur) {s.push(cur); cur = cur->_left;} Node* top = s.top(); if ((top->_left == NULL)) {top->_left = prev; top->_leftTag = THREND;} if (prev&&(prev->_right == NULL)) {prev->_rightTag = THREND; prev->_right = top;} prev = top;			if (top->_right != NULL)				cur = top->_right;			s.pop();					}	}

3.迭代器部分

templateclass TreeIterator{public: typedef TreeIterator self; typedef TreeIterator Iterator; typedef BinaryTreeThdNode Node; TreeIterator(Node* p) :ptr(p) {} TreeIterator() {} self& operator++() {if (ptr->_rightTag == THREND) {ptr = ptr->_right;} else if (ptr->_rightTag == LINK) {Node* tmp = ptr->_right; while (tmp&&tmp->_leftTag == LINK) {tmp = tmp->_left; } ptr = tmp;} return *this;} bool operator!=(Iterator it) {return !(ptr == it.ptr);} Ref operator*() {return ptr->_data; }private: Node* ptr ;};

Iterator Begin() {Node* cur = _root; while (cur->_leftTag) cur = cur->_left; return Iterator(cur);} Iterator End() {Node* cur = _root; while (cur!=NULL) {cur = cur->_right;} return Iterator(cur); }

4. Test

void TestInOrderIter(){ int array[10] = {1, 2, 3,'#','#', 4, '#','#', 5, 6 }; int array1[15] = {1, 2,'#', 3,'#','#', 4, 5,'#', 6,'# ', 7,'#','#', 8 }; BinaryTreeThd bt(array, 10,'#'); bt.InorderThreading(); BinaryTreeThd::Iterator it; for (it = bt .Begin(); it != bt.End();++it) {cout << *it << "";} cout << endl; BinaryTreeThdbt1(array1, 15,'#'); bt1.InorderThreading(); BinaryTreeThd::Iterator it1; for (it1 = bt1.Begin(); it1 != bt1.End(); ++it1) {cout << *it1 << "";} cout << endl;}