[Data Structure] Non-recurable traversal binary tree

Because the recursion is achieved through the stack, although the recursive code sometimes looks simpler, then the recursion is too deep and it will be created p>

Stack overflow. So we can achieve non-recursive traversal of the binary tree through the stack. Let’s look at the analysis below:

[Pre-order traversal]

Look at the implementation code below:

void PreOrderTraverseNonR() {stack s; Node* cur = _root; if (cur == NULL) return; while (cur || !s.empty( )) {while (cur) {cout << cur->_data << ""; s.push(cur); cur = cur->_left;} Node* top = s.top(); s.pop() ;			cur = top->_right;		}		cout << endl;	}

[In-order traversal]

The implementation code is given below:

void InOrderTraverseNonR() {stack s; Node* cur = _root; if (cur == NULL) return; while (cur ||! s.empty()) {while (cur) {s.push(cur); cur = cur->_left;} Node* top = s.top(); cout << top->_data<<" "; s .pop();			cur = top->_right;		}		cout << endl;	}



 
[Post-order traversal]
 
 
Look at the code below:

void PostOrderTraverseNonR() {if (NULL == _root) return; Node* prev = NULL; Node* cur = _root; stack s; while (cur || !s.empty( )) {while (cur) {s.push(cur); cur = cur->_left;} Node* top = s.top(); if (top->_right == NULL || top->_right == prev) {cout << top->_data << ""; prev = top; s.pop();} else {cur = top->_right;}} cout << endl; }