[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; }

WordPress database error: [Table 'yf99682.wp_s6mz6tyggq_comments' doesn't exist]
SELECT SQL_CALC_FOUND_ROWS wp_s6mz6tyggq_comments.comment_ID FROM wp_s6mz6tyggq_comments WHERE ( comment_approved = '1' ) AND comment_post_ID = 5069 ORDER BY wp_s6mz6tyggq_comments.comment_date_gmt ASC, wp_s6mz6tyggq_comments.comment_ID ASC

Leave a Comment

Your email address will not be published.