C++如何实现二叉树的递归遍历？_vlambda技术博客

vlambda
2021-02-07

C++如何实现二叉树的递归遍历？

二叉树的递归遍历操作根据根节点的遍历顺序分为前序遍历，中序遍历，后序遍历。

前序遍历：
在遍历以当前节点为根节点的树的左右节点前（此时左右节点都还未遍历），输出当前节点的值。
如下图所示二叉树，前序遍历结果应为：

A B D E C F G

前序遍历（图示）：

中序遍历：
在遍历以当前节点为根节点的树的右节点前（此时左节点已经遍历），输出当前节点的值。
如下图所示二叉树中，中序遍历结果应为：

D B E A F C G

中序遍历（图示）：

C++如何实现二叉树的递归遍历？

后序遍历：
在遍历以当前节点为根节点的树的左右节点后（此时左右节点都已经遍历），输出当前节点的值。
如下图所示二叉树中，后序遍历结果应为：

D E B F G C A

后序遍历（图示）：

C++如何实现二叉树的递归遍历？

层序遍历：
除以上三种遍历方法以外，二叉树还有一种层序遍历方法，即从上到下，从左到右依次遍历所有节点。层序遍历的实现需要借助队列，有些不太一样。
如上所示二叉树，层序遍历结果应为：

A B C D E F G

具体实现如下代码。

代码实现：

#include <iostream>#include <queue>
using namespace std;
struct TNode { char _val; TNode* _left; TNode* _right; TNode(char val):_val(val), _left(NULL), _right(NULL) {}};
class Tree { public: Tree(); ~Tree();  public: void PreOrder(); //先序遍历 void InOrder(); //中序遍历 void PostOrder(); //后序遍历  void LevelOrder();//层序遍历   private: //为了避免类的调用者访问类的私有成员 root_  //将具体操作封装为类私有函数供公共接口调用  TNode* Creat(); //创建树  void Release(TNode* root); //释放树  void preOrder(TNode* root); void inOrder(TNode* root);  void postOrder(TNode* root);  void levelOrder(TNode* root);  private: TNode* root_;};
TNode* Tree::Creat() { TNode* temp; char val;  cin >> val;  //若输入的节点的值为 # ，则表示以当前节点为根节点创建一棵空树  if (val == '#') temp = NULL; else { temp = new TNode(val); temp->_left = Creat(); temp->_right = Creat(); }  return temp;}
void Tree::Release(TNode* root) { if (root == NULL) return ; else { Release(root->_left); Release(root->_right); delete root; }}
void Tree::preOrder(TNode* root) { //若以当前节点为根节点的树为空，则退出当前节点的遍历  if (root == NULL) return ; else { cout << root->_val << ' ';//输出节点内的值。注意输出位置（前）  preOrder(root->_left); preOrder(root->_right); }}
void Tree::inOrder(TNode* root) { if (root == NULL) return ; else { inOrder(root->_left); cout << root->_val << ' ';//输出节点内的值（中）  inOrder(root->_right); }}
void Tree::postOrder(TNode* root) { if (root == NULL) return ; else { postOrder(root->_left); postOrder(root->_right); cout << root->_val << ' ';//输出节点内的值（后）  }}
void Tree::levelOrder(TNode* root) { //层序遍历。利用队列实现 queue<TNode*> q;  if (root == NULL) return ; else { //若树不为空，将树的根节点入队 q.push(root); }
 while (!q.empty()) { TNode* temp = q.front(); q.pop(); cout << temp->_val << ' '; //从队列中弹出当前节点并输出值后，将以当前节点为根节点的树的左右子树入队 //若当前节点为空（深度已经大于叶子节点），则不入队  if (temp->_left != NULL) q.push(temp->_left); if (temp->_right != NULL) q.push(temp->_right); }}
Tree::Tree() { root_ = Creat();}
Tree::~Tree() { Release(root_);}
void Tree::PreOrder() { cout << "前序遍历：";  preOrder(root_); cout << endl;} 
void Tree::InOrder() { cout << "中序遍历："; inOrder(root_); cout << endl;}
void Tree::PostOrder() { cout << "后序遍历："; postOrder(root_); cout << endl;}
void Tree::LevelOrder() { cout << "层序遍历："; levelOrder(root_); cout << endl; } 
int main() { //测试数据：A B D # # E # # C F # # G # # Tree t;  t.PreOrder(); t.InOrder(); t.PostOrder(); t.LevelOrder();  return 0;}

运行结果：

长按下面二维码关注哦~

壁纸基地