[Data Structure] Traverse of the binary tree

/* * 1. Recursive and non-recursive implementation of preorder traversal* 2. Intermediate traversal Recursive and non-recursive implementations of * 3. Recursive and non-recursive implementations of post-order traversal* 4. Reconstruct the tree structure based on the two traversal results*/#include #include #include using namespace std;struct BTreeNode{ int m_nValue; //number field BTreeNode* m_pLeft; < span class="hljs-comment">//left child BTreeNode* m_pRight; //right child};//Rebuild the binary treeBTreeNode* ConstructionCore(int *startPre, int *endPre, < span class="hljs-keyword">int *startIn, int *endIn){ //int rootValue = startPre[0]; BTreeNode* root =  new BTreeNode(); root->m_nValue = startPre[0]; root->m_pLeft = root->m_pRight = NULL; if(startPre == endPre) {if(startIn == endIn && *startPre == *startIn) {return root;} else {cout<<"Input Error!"<exit(-1<);}} int *rootIn = startIn; while(rootIn <= endIn && *rootIn! = root->m_nValue) ++rootIn; if(rootIn == endIn && *rootIn != root->m_nValue) {cout<<"Inout Error!"<exit(-1);} int leftlen = rootIn- startIn; int *leftPreEnd = startPre + leftlen; if(leftlen> 0) {root->m_pLeft = ConstructionCore(startPre+1, leftPreEnd, startIn, rootIn-1 );} if(leftlen m_pRight = ConstructionCore(leftPreEnd+1< /span>, endPre, rootIn+1, endIn);} return root;}BTreeNode* Construct(< span class="hljs-keyword">int *preorder, int *inorder, int len){ if(preorder == NULL || inorder == NULL || len <= < span class="hljs-number">0) return NULL; return ConstructionCore(preorder , preorder+len-1, inorder, inorder+len-1);}//Three traversal methods of binary tree//Recursive realization of preorder traversalvoid< /span> PreBTree(BTreeNode *pHead){ if(pHead) {cout<< pHead->m_nValue << " "; PreBTree(pHead->m_pLeft); PreBTree(pHead->m_pRight); }// cout< }//Preorder traversal non-recursive implementationvoid NRPreBTree(BTreeNode *pHead ){ stack sk; while(pHead != NULL || !sk.empty()) { if(pHead != NULL) {cout << pHead->m_nValue << " "; sk.push(pHead); pHead = pHead->m_pLeft;} else {pHead = sk.top() ; //Pop up parent node sk.pop(); pHead = pHead->m_pRight;}} cout <//Recursive realization of in-order traversalvoid InBTree(BTreeNode *pHead){ < span class="hljs-keyword">if(pHead != NULL) {InBTree(pHead->m_pLeft); cout << pHead->m_nValue << " "; InBTree(pHead->m_pRight); }}//Non-recursive implementation of in-order traversalvoid NRInBTree(BTreeNode *pHead){ stack sk; while(pHead! = NULL || !sk.empty()) {if(pHead != NULL) {//cout << pHead ->m_nValue << ""; sk.push(pHead); pHead = pHead->m_pLeft;} else {pHead = sk.top() ; //Pop up parent node sk.pop(); cout << pHead->m_nValue << < span class="hljs-string">" "; pHead = pHead->m_pRight;} }}//Recursive realization of post-order traversalvoid PostBTree(BTreeNode *pHead){ if(pHead != NU LL) {PostBTree(pHead->m_pLeft); PostBTree(pHead->m_pRight); cout << pHead->m_nValue << " "; }}//Non-recursive implementation of post-order traversalvoid NRPostBTree (BTreeNode *pHead){ stack sk; BTreeNode* q; int flag = 0; do {while(pHead) {sk.push(pHead); pHead = pHead->m_pLeft;} q = NULL; flag = 1; while(!sk.empty() && flag) {pHead = sk.top(); if( pHead->m_pRight == q) {sk.pop(); cout<< pHead->m_nValue <<" "; q = pHead;} ​​else< /span> {pHead = pHead->m_pRight; flag = 0;}}} while(!sk .empty());}int main(){ int pre[8] = {1,2,4,7,3,5,6,8};  int in[8] = {4,7,2,1,< span class="hljs-number">5,3,8,6}; BTreeNode *tr = Construct(pre, in, 8); cout<<"Preorder traversal recursion"<cout span><"Preorder traversal non-recursive"<cout span><<"In-order traversal recursion"<cout<< endl<<"In-order traversal non-recursive"<cout<< endl<<"Post-order traversal recursion"<cout<"Post-order traversal non-recursive"<cout<return 0;}