带你深入理解二叉树的遍历-阿里云开发者社区

带你深入理解二叉树的遍历

2024-01-30 38

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 带你深入理解二叉树的遍历

二叉树的遍历

1. 二叉树的前序、中序、后序遍历

前、中、后序遍历又叫深度优先遍历

注：严格来说，深度优先遍历是先访问当前节点再继续递归访问，因此，只有前序遍历是严格意义上的深度优先遍历

首先需要知道下面几点：

任何一颗二叉树，都由根节点、左子树、右子树构成。

如图：

分治算法：分而治之。大问题分成类似的子问题，子问题再分成子问题……直到子问题不能再分割。对树也可以做类似的处理，对一棵树不断地分割，直到子树为空时，分割停止。
关于二叉树的许多问题我们都要利用分治思想，将一棵完整的树分解成根和左右两棵子树，然后再对这两棵子树进行相同的递归处理，最后得到结果。
如果对递归的过程想的不太清楚，建议画递归展开图来辅助理解。

1.1 前序（先根）遍历

遍历顺序：根- > 左子树 -> 右子树（即先访问根，再访问左子树，最后在访问右子树）
如上图中：A -> B -> C -> NULL -> NULL -> D -> NULL -> NULL -> E -> NULL -> NULL

typedef char BTDataType;
typedef struct BinaryTreeNode
{
   struct BinaryTreeNode *left; //指向左子树
   struct BinaryTreeNode *right;  //指向右子树
    BTDataType data;
}BTNode;
void PrevOrder(BTNode * root) //前序遍历
{
   if (!root)
       return;
   printf("%d ",root->data);  //根
   PrevOrder(root->left);   //左子树
   PrevOrder(root->right);    //右子树
   return;
}

递归顺序图：

递归展开图:

1.2 中序（中根）遍历

遍历顺序：左子树 -> 根 -> 右子树（即先访问左子树，再访问根，最后在访问右子树）
如上图中：NULL -> C -> NULL -> B -> NULL -> D -> NULL -> A -> NULL -> E -> NULL

void InOrder(BTNode* root)
{
   if (!root)
    return;
   InOrder(root->left); //左子树
   printf("%c ", root->data);   //根
   InOrder(root->right);  //右子树
   return;
}

递归顺序图：

1.3 后序（后根）遍历

遍历顺序：左子树 -> 右子树 -> 根（即先访问左子树，再访问左=右子树，最后在访问根）
如上图中：NULL -> NULL -> C -> NULL -> NULL -> D -> B -> NULL -> NULL -> E -> A

void PostOrder(BTNode* root)
{
   if (!root)
   {
    printf("NULL ");
    return;
   }
   PostOrder(root->left); //左子树
   PostOrder(root->right);    //右子树
   printf("%c ", root->data);   //根
}

递归顺序图：

2. 二叉树的层序遍历

层序遍历又叫广度优先遍历。
设二叉树的根节点所在层数为1，层序遍历就是从根节点出发，首先访问第一层的节点，然后从左到右访问第二层上的节点，接着访问第三层的节点，以此类推，自上而下，自左往右逐层访问树的结点的过程就是层序遍历。
层序遍历借助队列的先进先出思想来实现。
核心思想：上一层带下一层
如图就是对上面那棵树的层序遍历示意图：
实现代码

typedef BTNode* QDataType;    //队列元素类型
typedef struct QueueNode
{
   struct QueueNode* next;
   QDataType data;
}QueueNode;
typedef struct Queue  //定义存放指向队头，队尾指针的结构体
{
   QueueNode* head; //指向队头
   QueueNode* tail; //指向队尾
}Queue;
//层序遍历
void LevelOrder(BTNode* root)   
{
   Queue *q = (Queue *)malloc(sizeof(Queue)); //创建队列
   QueueInit(q);  //初始化队列
   //如果根节点为空，直接退出函数
   if (!root)
    return;
   QueuePush(q, root);    //先将根节点入队入队
   while (!QueueEmpty(q))   //当队列不为空
   {
    BTNode* front = QueueFront(q);    //接收队头元素
    QueuePop(q);    //出队头元素
    printf("%c ", front->data); //访问该节点
    if (front->left)    //如果左子树不为空
      QueuePush(q, front->left);      //左子树入队
    if (front->right)   //如果右子树不为空
      QueuePush(q, front->right);   //右子树入队
   }
   printf("\n");
   QueueDestroy(q);   //销毁队列  
}