秋招之路-二叉树四种遍历（递归和非递归代码实现）

秋招之路-二叉树四种遍历（递归和非递归代码实现）

[图]cute girl  2019-07-01

阅读本文大概需要 5 分钟

前言

今天和大家带来的是二叉树的常见面试题，前序，中序，后序，层次遍历，递归和非递归，这里用 C++ 代码实现。

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问依次且仅被访问一次。

前序遍历

若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。（根->左->右）。

中序遍历

若树为空，则空操作返回。否则，从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。（左->根->右）。

后序遍历

若树为空，则空操作返回。否则，从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。（左->右->根）。

层次遍历

如图

下面来介绍一下具体的代码实现。

1、二叉树的定义

struct BinaryNode{ int m_data;//结点域 BinaryNode* left;//左子树 BinaryNode* right;//右子树 BinaryNode(int data):m_data(data),left(NULL),right(NULL) {}};

2、构造一棵二叉平衡树

//小于根节点的放在左子树，否则放在右子树void insertNode(BinaryNode* root,int data){ if(data<=root->m_data) { if(!root->left) { root->left = new BinaryNode(data); } else { insertNode(root->left,data); } } else { if(!root->right) { root->right = new BinaryNode(data); } else { insertNode(root->right,data); } }}

3、递归实现二叉树树的遍历

//前序遍历：根节点-》左节点-》右节点void preOrder(BinaryNode* root){ if(root==NULL) return ; else { cout<<"root->m_data"<m_data<left); preOrder(root->right); }}//中序遍历：左节点-》根节点-》右节点void inOrder(BinaryNode* root){ if(root==NULL) return ; else { inOrder(root->left); cout<<"root->m_data"<m_data<right); }}//后序遍历：左节点-》右节点-》根节点void postOrder(BinaryNode* root){ if(root==NULL) return ; else { postOrder(root->left); postOrder(root->right); cout<<"root->m_data"<m_data<

4、非递归实现二叉树的遍历

/*前序遍历，利用栈的先进后出[1]先让根进栈，只要栈不为空，就可以做弹出操作[2]每次弹出一个结点，把它的左右结点都进栈[3]若当前右孩子结点不为空，入栈;(右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面)[4]若当前左孩子结点不为空，入栈*/void dgPreOrder(BinaryNode* root){ if(root==NULL) return; std::stacks; BinaryNode* p = root; s.push(p); while(!s.empty()) { BinaryNode* t = s-(); cout<<"root->m_data"<m_data<right) s.push(t->right); if(t->left) s.push(t->left); }}//非递归中序遍历void dgInOrder(BinaryNode* root){ if(root==NULL) return; std::stacks; BinaryNode* p = root;// 指向当前要检查的节点 while(NULL!=p || !s.empty()) { while(NULL!=p) // 一直向左走 { s.push(p); p=p->left; } if(!s.empty()) { p=s-(); s.pop(); cout<<"root->m_data"<m_data<right; } }}//双栈法，非递归后续遍历/*栈s1入栈顺序：根节点-》左节点-》右节点栈s2入栈顺序：右节点-》左节点-》根节点出栈顺序：根节点-》左节点-》右节点*/void dgPostOrder(BinaryNode* root){ if(root==NULL) return; std::stacks1,s2; BinaryNode* p;// 指向当前要检查的节点 s1.push(root); while(!s1.empty()) { p = s1-(); s1.pop(); s2.push(p); if(p->left) s1.push(p->left); if(p->right) s1.push(p->right); } while(!s2.empty()) { cout<<"root->m_data"<m_data<

5、层次遍历（广度优先搜索）二叉树

void leverOrder(BinaryNode* root){ if(root==NULL) return; BinaryNode* p = root;// 指向当前要检查的节点 std::queue Q; Q.push(p); while(!Q.empty()) { BinaryNode* t = Q.front(); Q.pop(); cout<<"root->m_data"<m_data<left) Q.push(t->left); if(t->right) Q.push(t->right); }}

完整代码：

/*File:二叉树前序中序后序遍历递归和非递归 C++实现Author: herongweiData: 2019/07/01*/#include using namespace std;struct BinaryNode{ int m_data; BinaryNode* left; BinaryNode* right; BinaryNode(int data):m_data(data),left(NULL),right(NULL) {}};//构造二叉平衡树void insertNode(BinaryNode* root,int data){ if(data<=root->m_data) { if(!root->left) { root->left = new BinaryNode(data); } else { insertNode(root->left,data); } } else { if(!root->right) { root->right = new BinaryNode(data); } else { insertNode(root->right,data); } }}//递归实现//前序遍历：根节点-》左节点-》右节点void preOrder(BinaryNode* root){ if(root==NULL) return ; else { cout<<"root->m_data"<m_data<left); preOrder(root->right); }}//中序遍历：左节点-》根节点-》右节点void inOrder(BinaryNode* root){ if(root==NULL) return ; else { inOrder(root->left); cout<<"root->m_data"<m_data<right); }}//后序遍历：左节点-》右节点-》根节点void postOrder(BinaryNode* root){ if(root==NULL) return ; else { postOrder(root->left); postOrder(root->right); cout<<"root->m_data"<m_data<s; BinaryNode* p = root; s.push(p); while(!s.empty()) { BinaryNode* t = s-(); cout<<"root->m_data"<m_data<right) s.push(t->right); if(t->left) s.push(t->left); }}//非递归中序遍历void dgInOrder(BinaryNode* root){ if(root==NULL) return; std::stacks; BinaryNode* p = root;// 指向当前要检查的节点 while(NULL!=p || !s.empty()) { while(NULL!=p) // 一直向左走 { s.push(p); p=p->left; } if(!s.empty()) { p=s-(); s.pop(); cout<<"root->m_data"<m_data<right; } }}//双栈法，非递归后续遍历/*栈s1入栈顺序：根节点-》左节点-》右节点栈s2入栈顺序：右节点-》左节点-》根节点出栈顺序：根节点-》左节点-》右节点*/void dgPostOrder(BinaryNode* root){ if(root==NULL) return; std::stacks1,s2; BinaryNode* p;// 指向当前要检查的节点 s1.push(root); while(!s1.empty()) { p = s1-(); s1.pop(); s2.push(p); if(p->left) s1.push(p->left); if(p->right) s1.push(p->right); } while(!s2.empty()) { cout<<"root->m_data"<m_data< Q; Q.push(p); while(!Q.empty()) { BinaryNode* t = Q.front(); Q.pop(); cout<<"root->m_data"<m_data<left) Q.push(t->left); if(t->right) Q.push(t->right); }}int main(){ freopen("in.txt","r",stdin); cout<<"input"<>T; while(T--) { cout<<"root"<>root_data; BinaryNode root(root_data); cout<<"num of child"<>n; cout<<"child"<>val; insertNode(&root,val); } /* 2 /\ 1 3 */ // 2 1 3 std::cout<<"preOrder is:"<

运行效果：

今天的知识点就到这里了，你学会了吗？

有问题，欢迎和我一起交流~

​

点个呗

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。