首页 > 代码库 > 二叉树遍历,深度有限遍历,广度优先遍历,前序中序后续优先遍历,层次遍历
二叉树遍历,深度有限遍历,广度优先遍历,前序中序后续优先遍历,层次遍历
首先明白两个概念:
1. 深度遍历包括前中后序遍历三种;
2. 广度优先遍历就是层次遍历。
PS:
前中后序遍历,如果使用递归遍历,都很简单易理解;
如果使用非递归方式,首先想到的就应该是使用栈结构来控制整个过程,因为递归也是利用栈来实现的;
前中后序遍历的非递归方式中,后序遍历的非递归方式相比较而言,略复杂。
直接上代码:
#include "stdlib.h" #include <iostream> #include <stack> #include <queue> using namespace std; struct BinaryTreeNode { int value; BinaryTreeNode* leftChild; BinaryTreeNode* rightChild; }; /* 前序遍历递归方式 步骤: 1.先处理当前节点 2.递归处理完左支 3.递归处理右支 */ void PreOrderRecursive(BinaryTreeNode* parent) { if(NULL == parent) return; cout<<parent->value<<" "; PreOrderRecursive(parent->leftChild); PreOrderRecursive(parent->rightChild); } /* 前序遍历非递归方式 说明: nodeStack栈用来记录未遍历的节点,而且节点的左右孩子也未遍历。所以遍历结束条件是栈空 ((想什么时候可以出栈(被遍历),因为是先序遍历,所以只要在栈顶,输出即可,再处理左右孩子)) 1.栈不空,则把栈顶元素出栈,并把其右左孩子依次压栈。这个顺序保证了,先父亲、后左孩子、最后右孩子的前序遍历 */ void PreOrderStack(BinaryTreeNode* root) { if (NULL == root) return; stack<BinaryTreeNode*> nodeStack; BinaryTreeNode* pNode = NULL; nodeStack.push(root); while(!nodeStack.empty()) { pNode = nodeStack.top(); nodeStack.pop(); cout<<pNode->value<<" "; if(NULL != pNode->rightChild) nodeStack.push(pNode->rightChild); if(NULL != pNode->leftChild) nodeStack.push(pNode->leftChild); } } /* 中序遍历递归方式 步骤: 1.先递归处理完左支 2.再处理当前节点 3.最后递归处理右支 */ void InOrderRecursive(BinaryTreeNode* parent) { if(NULL == parent) return; InOrderRecursive(parent->leftChild); cout<<parent->value<<" "; InOrderRecursive(parent->rightChild); } /* 中序遍历非递归方式 说明: nodeStack栈用来记录未遍历的节点,而且节点的左右孩子也未遍历。遍历结束条件是栈空且当前节点无效。 ((想什么时候可以出栈,肯定是左支已经处理完了,栈顶的才可以出栈,而且出栈之后马上处理右孩子节点)) 1.中序遍历输出当前节点前,应把左支所有节点遍历完毕。所以第一步就是循环查找最左下节点,并依次压栈,直到找到最左下节点(没有左孩子) 2.中序是(左中右),既然没有左孩子,则可以直接出当前节点(在栈顶) 3.然后从第一步循环处理当前节点的右孩子 */ void InOrderStack(BinaryTreeNode* root) { if (NULL == root) return; stack<BinaryTreeNode*> nodeStack; BinaryTreeNode* pNode = root; while(NULL != pNode || !nodeStack.empty()) { while(NULL != pNode) { nodeStack.push(pNode); pNode = pNode->leftChild; } /* if (nodeStack.empty()) return; 不需要此检测 1. 外层while条件如果是pNode不空,会进内层while,则nodeStack肯定不空; 2. 外层while条件如果是nodeStack不空,更不需要此检测了。 */ pNode = nodeStack.top(); cout<<pNode->value<<" "; nodeStack.pop(); pNode = pNode->rightChild; } } /* 后序遍历递归方式 步骤: 1.先递归处理完左支 2.再递归处理完右支 3.最后处理当前节点 */ void PostOrderRecursive(BinaryTreeNode* parent) { if(NULL == parent) return; PostOrderRecursive(parent->leftChild); PostOrderRecursive(parent->rightChild); cout<<parent->value<<" "; } /* 后序遍历非递归方式 步骤: nodeStack栈用来记录未遍历的节点,而且节点的左孩子或右孩子也未遍历。遍历结束条件是栈空。 ((想什么时候可以出栈,1.没有左右孩子的可以出;2.有左右孩子,且左右孩子已经被遍历输出了,也可以出栈)) 用preNode记录最近遍历输出的节点 1.检查是不是满足输出条件,如果满足,则输出; 2.不满足,则说明有左或右孩子,且没被遍历,所以先把孩子压栈做处理,处理完之后再说当前节点的事情 */ void PostOrderStack(BinaryTreeNode* root) { if (NULL == root) return; stack<BinaryTreeNode*> nodeStack; BinaryTreeNode* pNode = NULL; BinaryTreeNode* preNode = NULL; nodeStack.push(root); while(!nodeStack.empty()) { pNode = nodeStack.top(); if ((NULL == pNode->leftChild && NULL == pNode->rightChild) || (preNode!=NULL && (preNode == pNode->leftChild || preNode == pNode->rightChild))) { cout<<pNode->value<<" "; nodeStack.pop(); preNode = pNode; } else { if (NULL != pNode->rightChild) nodeStack.push(pNode->rightChild); if (NULL != pNode->leftChild) nodeStack.push(pNode->leftChild); } } } /* 宽度优先遍历,层次遍历 步骤: 队列用来记录未遍历的节点,而且节点的左孩子或右孩子也未遍历。如果队列空,则说明遍历结束。 ((想一想层次遍历就是,同层孙子辈的最后依次输出,同层叔父辈的依次输出,同层爷爷辈的一次输出;而且是辈份越长,越先输出;同层即同辈份的必须挨着,队列可以满足)) 1.输出队头的节点; 2.把队头节点的儿子们赶紧地送到队尾去排队(因为叔父辈的在队列里挨着,所以保证了叔父辈的儿子们这一辈在队列里也是挨着的) */ void BreadthFirst(BinaryTreeNode* root) { if (NULL == root) return; queue<BinaryTreeNode*> nodeQueue; BinaryTreeNode* pNode = NULL; nodeQueue.push(root); while(!nodeQueue.empty()) { pNode = nodeQueue.front(); cout<<pNode->value<<" "; nodeQueue.pop(); if (NULL != pNode->leftChild) nodeQueue.push(pNode->leftChild); if (NULL != pNode->rightChild) nodeQueue.push(pNode->rightChild); } } // 测试 int main() { // 空树 BinaryTreeNode* nullTree = NULL;; // 单节点树 BinaryTreeNode singleNode; singleNode.value = http://www.mamicode.com/1;>
欢迎各种指正、交流!二叉树遍历,深度有限遍历,广度优先遍历,前序中序后续优先遍历,层次遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。