二叉树的遍历——先序遍历、中序遍历、后序遍历

淡淡的烟草味﹌ 2022-12-01 15:44 369阅读 0赞

遍历二叉树

（本文的二叉树均使用指针方式构建）

先序遍历

操作定义：

若二叉树为空，则空操作； 否则：

  1. 访问根节点；
  2. 先序遍历左子树；
  3. 先序遍历右子树；

代码：

  1. void preOrderTraveral(treeNode* node){
  3.     if (node == NULL){
  5.         return;
  6.     }
  8.     cout << node->data;
  9.     preOrderTraveral(node->lchild);
  10.     preOrderTraveral(node->rchild);
  11. }

中序遍历

操作定义：

若二叉树为空，则空操作； 否则：

  1. 中序遍历左子树；
  2. 访问根节点；
  3. 中序遍历右子树；

代码：

  1. void inOrderTraveral(treeNode* node){
  3.     if (node == NULL){
  5.         return;
  6.     }
  8.     inOrderTraveral(node->lchild);
  9.     cout << node->data;
  10.     inOrderTraveral(node->rchild);
  11. }

后序遍历

操作定义：

若二叉树为空，则空操作； 否则：

  1. 后序遍历左子树；
  2. 后序遍历右子树；
  3. 访问根节点；

代码：

  1. void postOrderTraveral(treeNode* node){
  3.     if (node == NULL){
  5.         return;
  6.     }
  8.     postOrderTraveral(node->lchild);
  9.     postOrderTraveral(node->rchild);
  10.     cout << node->data;
  11. }

举例：

对于如图所示二叉树：
在这里插入图片描述
其先序遍历、中序遍历、后序遍历分别为：
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，369人围观）

还没有评论，来说两句吧...

相关阅读