AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构入门】二叉树的遍历（前序、中序、后序、层序）

2023-05-18 744
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构入门】二叉树的遍历（前序、中序、后序、层序）

二叉树遍历

什么是二叉树遍历：


二叉树遍历就是按照某种特定的规则，依次堆二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。


我们以后看到二叉树应该这样去看待：把他看成根、左子树、右子树。


二叉树的遍历有：前序、中序、后序、层序遍历的递归结构遍历：


1.前序遍历（Preorder Traversal），也叫前根遍历：

2.中序遍历（Inorder Traversal），也叫中根遍历：

3.后序遍历（Post orderTraversal）也叫后根遍历：

4.层序遍历

1.png

2.png



前序遍历

下面是前序遍历的动态图。

3.gif

以下图为例进行代码的编写：

4.png

请看代码：


void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}


这是运行结果：

5.png


中序遍历

请看中序遍历的动态图：

6.gif


还是以下图进行举例：

7.png

请看代码：


//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}


下面是运行结果：


8.png

后序遍历

下面是后序遍历的动态图：

9.gif


还是以下图进行举例：


10.png

//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}


请看运行结果：


11.png

前中后序总代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
//新建结点
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
  perror("malloc fail");
  return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
BTNode* CreatTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}
//前序遍历
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("NULL ");
  return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int main()
{
  BTNode* root = CreatTree();
  //PreOrder(root);//前序遍历
  //InOrder(root);//中序遍历
  //PostOrder(root);//后序遍历
  return 0;
}


最后，其实前序、中序、后序的过程基本上就是一样的，即前序、中序、后序的递归过程是一样的，不一样的就是访问根的时机不一样。


层序遍历

层序遍历的话可以利用队列先进先出的特点来进行实现，出上一层，带入下一层。

所以这里的层序遍历就是利用队列来实现的。

10.gif

12.png



注意队列中的结点里面的data存的是树结点的指针。


层序遍历总代码

Quene.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq,QDataType x);//插入数据
void QueuePop(Queue* pq);//删除数据
QDataType QueueFront(Queue* pq);//取队头的数据
QDataType QueueBack(Queue* pq);//取队尾的数据
int QueueSize(Queue* pq);//有多少个数据
bool QueueEmpty(Queue* pq);//判断队列是否为空

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = cur->next;
  }
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//删除
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //if (pq->head == NULL)
  //{
  //  return;
  //}//温柔的处理
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  if (pq->head == NULL)
  {
    pq->tail=NULL;
  }
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
QDataType QueueBack(Queue* pq)//取队尾的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
QDataType QueueFront(Queue* pq)//取队头的数据
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
int QueueSize(Queue* pq)//有多少个数据
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
    n++;
    cur = cur->next;
  }
  return n;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;
//新建结点
BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
BTNode* CreatTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}
//前序遍历
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int size = 0;
求树中结点个数法1
//int TreeSize(BTNode* root,int* psize)
//{
//  if (root == NULL)
//    return;
//  (*psize)++;
//  TreeSize(root->left, psize);
//  TreeSize(root->right, psize);
//}
//求树的结点个数法2
int TreeSize(BTNode* root)
{
  return root == NULL ? 0 :
    TreeSize(root->left)
    + TreeSize(root->right)
    + 1;
}
//求树的高度
int TreeHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int TreeKLevel(BTNode* root, int k)
{
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  int leftK = TreeKLevel(root->left, k - 1);
  int rightK = TreeKLevel(root->right, k - 1);
  return leftK + rightK;
}
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  BTNode* lret = BinaryTreeFind(root->left, x);
  if (lret)
    return lret;
  BTNode* rret = BinaryTreeFind(root->right, x);
  if (rret)
    return rret;
  return NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    //front指向的不是队列的结点，而是树的结点
    QueuePop(&q);
    printf("%d ", front->data);
    if (front->left)
      QueuePush(&q, front->left);
    if (front->right)
      QueuePush(&q, front->right);
  }
  QueueDestory(&q);
}
int main()
{
  BTNode* root = CreatTree();
  //PreOrder(root);//前序遍历
  //InOrder(root);//中序遍历
  //PostOrder(root);//后序遍历
  求树的结点法1
  /*int size1 = 0;
  TreeSize(root, &size1);
  printf("TreeSize:%d\n", size1);
  int size2 = 0;
  TreeSize(root, &size2);
  printf("TreeSize:%d\n", size2);*/
  求树的结点法2
  //printf("TreeSize:%d\n", TreeSize(root));
  //printf("TreeSize:%d\n", TreeSize(root));
  //printf("TreeSize:%d\n", TreeSize(root));
  求树的高度
  //printf("TreeHeight:%d\n", TreeHeight(root));
  //printf("TreeKLevel:%d\n", TreeKLevel(root, 1));
  二叉树查找值为x的结点
  //printf("BinaryTreeFind:%p\n", BinaryTreeFind(root, 5));
  //printf("BinaryTreeFind:%p\n", BinaryTreeFind(root, 0));
  //层序遍历
  LevelOrder(root);
  return 0;
}

以上就是二叉树遍历的四种方式（前序、中序、后序、层序）。说实话，内容还是有些难度的，这就更需要我们认真的进行学习并复习了。

加油，各位！！！

关键词：
数据结构二叉树
数据结构入门
数据结构遍历
数据结构二叉树的遍历
数据结构中序
Parallel
目录
相关文章
aliyun6365824167
|
1天前
|
存储
【初阶数据结构篇】二叉树基础概念
有⼀个特殊的结点，称为根结点，根结点没有前驱结点。
aliyun6365824167
9 1
睡觉待开机
|
6天前
|
存储 算法 Linux
【数据结构】树、二叉树与堆（长期维护）（1）
【数据结构】树、二叉树与堆（长期维护）（1）
睡觉待开机
10 1
睡觉待开机
|
6天前
|
算法
【数据结构】树、二叉树与堆（长期维护）（2）
【数据结构】树、二叉树与堆（长期维护）（2）
睡觉待开机
7 0
【数据结构】树、二叉树与堆（长期维护）（2）
aliyun6365824167
|
1天前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称，即左右子树是否对称.
aliyun6365824167
7 0
aliyun6365824167
|
1天前
|
存储
【初阶数据结构篇】实现链式结构二叉树（二叉链）下篇
要改变root指针的指向，将本来指向根节点的root指针改为空，所以传二级指针（一级指针也可以，只不过在调用完记得把root置为空）。
aliyun6365824167
9 0
aliyun6365824167
|
1天前
|
存储 测试技术
【初阶数据结构篇】实现链式结构二叉树（二叉链）上篇
先构建根结点，再对左右子树构建，每次需要时申请一个结点空间即可，否则返回空指针。
aliyun6365824167
14 0
aliyun6365824167
|
1天前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树（堆的实现方法）
注意传过去的参数是插入的位置，即插入前的size，在调整完后再将size++
aliyun6365824167
5 0
大柏怎么被偷了
|
6天前
【数据结构】栈和队列
【数据结构】栈和队列
大柏怎么被偷了
12 2
睡觉待开机
|
6天前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
睡觉待开机
6 0
服务端技术栈
|
4天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
8 1
栈的几个经典应用，真的绝了