二叉树遍历

2024-07-11 01:49| 来源: 网络整理| 查看: 265

文章目录深度优先遍历1、先根遍历2、中根遍历3、后根遍历广度优先遍历（层序遍历）参考

二叉树的遍历分为两类，一类是深度优先遍历，一类是广度优先遍历。

左孩子结点一定要在右孩子结点之前访问。

深度优先遍历

二叉树的深度优先遍历方式有三种，先根（序）遍历、中根（序）遍历、后根（序）遍历。

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。下面一一讲解具体的递归和非递归实现。

1、先根遍历

递归实现

//先根递归遍历 void preOrderRecursion(BinaryTreeNode* root) { if(root==NULL) return; coutm_pLeft); preOrderRecursion(root->m_pRight); }

非递归实现

根据先序遍历的顺序，首先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问完左子树时，再访问它的右子树。因此其处理过程如下：

给定二叉树的根节点 R：

首先将根节点 R 入栈；

判断栈是否为空，若不为空，取栈顶元素 cur 访问并出栈。然后先将 cur 的右子节点入栈，再将 cur 的左子节点入栈；

重复（b）直到栈为空，则遍历结束。

// 先序非递归遍历，需要使用栈 void preOrderStack(BinaryTreeNode* root) { if(root==NULL) return; stack stack; stack.push(root); BinaryTreeNode* cur=NULL; while(!stack.empty()) { cur=stack.top(); coutm_pLeft!=NULL) { stack.push(cur->m_pLeft); } } }

下面给出个中根遍历相同框架的非递归实现：

void preOrderStack(BinaryTreeNode* root) { if(root==NULL) return; stack stack; BinaryTreeNode* cur=root; while(!stack.empty() || cur!=NULL) { while(cur) { coutm_pLeft); coutm_pRight==NULL) || (pre!=NULL&&(pre==cur->m_pLeft || pre==cur->m_pRight))) { coutm_pLeft!=NULL) s.push(cur->m_pLeft); } } } 广度优先遍历（层序遍历）

广度优先遍历，也就是层序遍历，按照层次从上到下，每层从左到右地访问，可以使用队列来实现。

void breadthFirstOrder(BinaryTreeNode* root) { if(root==NULL) return; queue queue; queue.push(root); // 首先根节点入栈 while(!queue.empty()) { BinaryTreeNode* cur=queue.front(); queue.pop(); coutm_pRight!=NULL) queue.push(cur->m_pRight); } } 参考

https://cloud.tencent.com/developer/article/1632481。

https://cloud.tencent.com/developer/article/1376745。

【本文地址】

二叉树遍历

二叉树遍历

今日新闻

推荐新闻