二叉树遍历(深度优先+广度优先) |
您所在的位置：网站首页 › 深度优先搜索的数据结构是什么样的 › 二叉树遍历(深度优先+广度优先) |
|
文章目录
1.深度优先遍历1.1 先序遍历1.2 中序遍历1.3 后序遍历
2.广度优先遍历3.验证结果参考文献
二叉树的遍历分为两类，一类是深度优先遍历，一类是广度优先遍历。
1.深度优先遍历
二叉树的深度优先遍历有三种方式，先序（先根次序）、中序（中根次序）和后序（后根次序）遍历。 因为树的定义本身是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。若采用非递归的方法遍历二叉树，需要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。下面一一讲解具体的递归和非递归实现。 1.1 先序遍历先根次序遍历按照“根结点 > 左孩子 > 右孩子”的顺序进行访问。 递归实现 // 先根递归遍历。 void preOrderRecursion(BinaryTreeNode* root) { if(root==NULL) return; coutm_pLeft); } } } 1.2 中序遍历中序遍历按照“左孩子 > 根结点 > 右孩子”的顺序进行访问。 递归实现 // 中序递归遍历。 void midOrderRecursion(BinaryTreeNode* root){ if(root==NULL) return; midOrderRecursion(root->m_pLeft); coutm_pLeft); postOrderRecursion(root->m_pRight); cout m_pRight))) { coutm_pLeft!=NULL) s.push(cur->m_pLeft); } } } 2.广度优先遍历广度优先周游的方式是按层次从上到下，从左到右的逐层访问，不难想到，可以利用一个队列来实现。基本思想如下： （1）首先把二叉树的根节点送入队列； （2）队首的节点出队列并访问之，然后把它的右子节点和左子节点分别入队列； （3）重复上面两步操作，直至队空。 // 广度优先遍历二叉树，使用队列实现 void breadthFirstOrder(BinaryTreeNode* root) { if(root==NULL) return; queue queue; queue.push(root); while(!queue.empty()) { BinaryTreeNode* cur=queue.front(); coutm_pRight!=NULL) queue.push(cur->m_pRight); } } 3.验证结果以上面介绍的各种遍历，验证代码如下： #include #include #include using namespace std; // 二叉树节点结构体 struct BinaryTreeNode { int m_key; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; /**************************************** func:根据前序序列和中序序列构建二叉树 para:preOrder:前序序列;midOrder:中序序列;len:节点数 ****************************************/ BinaryTreeNode* construct(int* preOrder,int* midOrder,int len) { if(preOrder==NULL||midOrder==NULL||lenm_key=rootKey; root->m_pLeft=root->m_pRight=NULL; //只有一个节点 if(len==1 && *preOrder == *midOrder) return root; //在中序遍历中找到根节点的值 int* rootMidOrder=midOrder; int leftLen=0; //左子树节点数 while(*rootMidOrder!=rootKey&&rootMidOrder0) { root->m_pLeft=construct(preOrder+1,midOrder,leftLen); } //构建右子树 if(len-leftLen-1>0) { root->m_pRight=construct(preOrder+leftLen+1,rootMidOrder+1,len-leftLen-1); } return root; } int main() { // 先序序列 int preOrder[8]={1,2,4,7,3,5,6,8}; // 中序序列 int midOrder[8]={4,7,2,1,5,3,8,6}; // 建树 BinaryTreeNode* root=construct(preOrder, midOrder, 8); cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |