《二叉树的递归和非递归遍历》由会员分享,可在线阅读,更多相关《二叉树的递归和非递归遍历(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:/