[Data Structure] Iterator realizes the order of the binary tree

Iterator

templatestruct __TreeIterator{ typedef BinTreeNode Node; typedef __TreeIterator Self; __TreeIterator() {} __TreeIterator(Node* node) :_node(node) {} Ref operator*() {assert( _node); return _node->_date;} Self& operator++() {assert(_node); if(_node->RightTag==Link) {Node* right=_node->rightchild; while (right&&right->LeftTag==Link) {right=right->leftchild;} _node=right;} else {_node=_node->rightchild;} return *this;} Self& operator++(int) {Self tmp(*this); ++(*this); return tmp;} Self& operator--() {assert(_node); if(_node->LeftTag=Link) {Node* left=_node->leftchild; while (left&&left->RightTag==Link) {left=left-> rightchild;} _node=left;} else {_node=_node->leftchild;} return *this;} bool operator!=(const Self s) const {return _node!=s._node;} Node* _no de;

T means type, Ref means reference, Ptr means pointer

The realization of the binary tree

The need to implement begin and end

< pre code_snippet_id="1930184" snippet_file_name="blog_20161015_2_5713547" name="code" class="cpp">template class BinTree{ typedef BinTreeNode Node;public: typedef __TreeIterator Iterator ; typedef __TreeIterator ConstIterator; Iterator Begin() {Node* cur=_root; while (cur&&cur->LeftTag==Link) {cur=cur->leftchild;} return Iterator(cur) ;} ConstIterator Begin()const; Iterator End() {return Iterator(0);} ConstIterator End()const; BinTree() :_root(NULL) {} BinTree(T* a,size_t size,const T& invalid): _root(NULL) {size_t index=0; _CreateTree( _root,a,size,index,invalid);} void InOrderThead() {Node* pre=NULL; _InOrderThead(_root,pre); }protected: void _CreateTree(Node* & root,T a[],size_t size,size_t& index ,const T& invalid) {assert(a); if(index< size&& a[index]!=invalid) {root=new Node(a[index]); _CreateTree (root->leftchild,a,size,++index,i nvalid); _CreateTree(root->rightchild,a,size,++index,invalid);}} void _InOrderThead(Node* root,Node* &pre) {if(root==NULL) return; _InOrderThead(root->leftchild ,pre); if(root->leftchild==NULL) {root->LeftTag=Thread; root->leftchild=pre;} if(pre&&pre->rightchild==NULL) {pre->RightTag=Thread; pre- >rightchild=root;} pre=root; _InOrderThead(root->rightchild,pre); }private: Node* _root;};
Test case

void test(){ int a1[10]={1,2,3,'#','#' ,4,'#','#',5,6}; BinTree t1(a1,10,'#'); t1.InOrderThead(); //t1.InOrder_NonR(); BinTree: :Iterator it=t1.Begin(); cout<