The node structure of the binary tree is now redefined as follows:
|
leftchild
|
lefttag
|
_date
|
righttag
|
rightchild
|
where: when lefttag=0, leftchild points to the left child;
lefttag=1 when leftchild points to the front drive;
When righttag=0, rightchild points to the right child;
righttag=1 when rightchild points to the successor
The middle-order clue binary tree diagram is as follows
Create a binary tree
< div class="para" style="font-size:14px; word-wrap:break-word; color:rgb(51,51,51); margin-bottom:15px; text-indent:2em; line-height: 24px; zoom:1; font-family:arial,宋体,sans-serif">
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,invalid); _CreateTree(root->rightchild,a,size,++index,invalid);} }
In-order threading
< div class="para" style="font-size:14px; word-wrap:break-word; color:rgb(51,51,51); margin-bottom:15px; text-indent:2em; line-height: 24px; zoom:1; font-family:arial,宋体,sans-serif">
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); }
Pre-order clueization
void _PrevOrderThead(Node* root,Node* &pre) {if(root==NULL) return; if(root->leftchild==NULL) {root- >LeftTag=Thread; root->leftchild=pre;} if(pre&&pre->rightchild==NULL) {pre->RightTag=Thread; pre->rightchild=root;} pre=root; if(root->LeftTag= =Link) _PrevOrderThead(root->leftchild,pre); if(root->RightTag==Link) _PrevOrderThead(root->rightchild,pre); }
Post-order threading
< div class="para" style="font-size:14px; word-wrap:break-word; color:rgb(51,51,51); margin-bo ttom:15px; text-indent:2em; line-height:24px; zoom:1; font-family:arial,宋体,sans-serif">
void _PostOrderThead(Node* root,Node* &pre) {if(root==NULL) return; _PostOrderThead(root->leftchild,pre); _PostOrderThead(root->rightchild,pre); if(root ->leftchild==NULL) {root->LeftTag=Thread; root->leftchild=pre;} if(pre&&pre->rightchild==NULL) {pre->RightTag=Thread; pre->rightchild=root;} pre =root; }
Detailed code implementation
#include#include#include< queue>#include using namespace std;enum PointTag{ Link,//pointer Thread//clue};template struct BinTreeNode{ T _date; BinTreeNode* leftchild;//Left child BinTreeNode * rightchild;//right child PointTag LeftTag;//left child cueing flag PointTag RightTag;//right child cueing flag BinTreeNode(const T& x) :_date(x) ,leftchild(NULL) ,rightchild( NULL) ,LeftTag(Link) ,RightTag(Link) {}};template class BinTree{ typedef BinTreeNode Node;public: 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 PrevOrderThead() {Node* pre=NULL; _PrevOrderThead(_root,pre);} void PrevOrder_NonR() {Node* root=_root; if(root==NULL) return; while(root) {while(root->LeftTag==Link) {cout<_date<<" "; root= root->leftchild;} cout<_date<<" "; root=root->rightchild;} cout<LeftTag==Link) {root=root->leftchild;} cout<_date<<" "; while (root->RightTag==Thread) {root=root->rightchild; cout<_date<<" ";} root=root->rightchild;} cout<leftchild,a,size,++index,invalid); _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);} void _PrevOrderThead(Node* root,Node* &pre) {if(root==NULL) return; if(root->leftchild==NULL) {root->LeftTag=Thread; root->leftchild= pre;} if(pre&&pre->rightchild==NULL) {pre->RightTag=Thread; pre->rightchild=root;} pre=root; if(root->LeftTag==Link) _PrevOrderThead(root->leftchild, pre); if(root->Ri ghtTag==Link) _PrevOrderThead(root->rightchild,pre);} void _PostOrderThead(Node* root,Node* &pre) {if(root==NULL) return; _PostOrderThead(root->leftchild,pre); _PostOrderThead(root ->rightchild,pre); if(root->leftchild==NULL) {root->LeftTag=Thread; root->leftchild=pre;} if(pre&&pre->rightchild==NULL) {pre->RightTag=Thread ; pre->rightchild=root;} pre=root; }private: Node* _root;};
