《二叉树的递归和非递归遍历》由会员分享，可在线阅读，更多相关《二叉树的递归和非递归遍历（18页珍藏版）》请在金锄头文库上搜索。
1、 前序遍历：遍历顺序：根节点，左子树，右子树递归遍历：访问根节点，递归调用再访问左子树，右子树/前序遍历 void PrevOrder() _PrevOrder(_root); cout endl; void _PrevOrder(Node* root) if (root = NULL) return; cout _data _leftNode);/左子树 _PrevOrder(root-_rightNode);/右子树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16非递归遍历：压入根节点的左子树节点并访问，取栈顶元素，对其右子树节点进行压栈(右子树节点作为子树的
2、根节点说不定会有左子树节点)。/前序遍历 void PrevOrder_NonR() Node* cur = _root; stack s; while (cur | !s.empty() while (cur) cout _data _leftNode; Node* top = s.top(); cur = top-_rightNode; s.pop(); cout endl; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 中序遍历遍历顺序：左子树，根节点，右子树递归遍历：递归调用左子树并访问，根节点，再右子树/中序遍历 void InOrd
3、er() _InOrder(_root); cout _leftNode);/左子树 cout _data _rightNode);/右子树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16非递归遍历：和前序遍历一样，建立栈将根节点的左子树节点压入，但不访问。在取栈顶元素的时候对节点进行访问。/中序遍历 void InOrder_NonR() Node* cur = _root; stack s; while (cur | !s.empty() /压入根节点的左子树节点 while (cur) s.push(cur); cur = cur-_leftNode; /取
4、栈顶元素并进行访问 Node* top = s.top(); cout _data _rightNode; cout endl; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 后序遍历遍历顺序：左子树，右子树，根节点递归遍历：/后序遍历 void PostOrder() _PostOrder(_root); cout _leftNode);/左子树 _PostOrder(root-_rightNode);/右子树 cout _data ;/根节点 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16非递
5、归遍历：左子树节点遍历后不能对直接取栈顶元素进行pop操作，需要对其右子树节点进行判断，这里需要记录上次访问的节点prevNode,右子树节点为空或右子树节点为上次访问过的节点，都说明此子树已经遍历完成。/后序遍历 void PostOrder_NonR() Node* cur = _root; Node* prevNode = NULL;/记录上次访问的节点 stack s; while (cur | !s.empty() while (cur) s.push(cur); cur = cur-_leftNode; Node* top = s.top(); if (top-_rightNode
6、 = NULL | top-_rightNode = prevNode) cout _data _rightNode; cout endl; 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 层序遍历1. 利用队列先进先出的特点，将根节点压进队列，如果此根节点存在左子树节点和右子树节点，就将根节点先出队列，再将左子树节点和右子树节点进队列；2. 此次进入的左右子树节点也会作为根节点有其对应的左右子树节点，再进行根节点出队列，左右子树节点进队列操作即可，直至所有节点全被遍历。/层序遍历 void LevelOrder() queue q; if (_root) q.push(_root); while (!q.empty() Node* front = q.front(); cout _data _leftNode) q.push(front-_leftNode); if (front-_rightNode) q.push(front-_rightNode); cout endl; 更多精彩内容：http:/
