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

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

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

二叉树遍历

什么是二叉树遍历：


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


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


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


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
目录
相关文章
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
111 8
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
26 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
28 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
2月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
30 1
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
26 0
阿客不是客
|
2月前
|
存储 机器学习/深度学习 算法
探索数据结构：入门及复杂度的解锁
探索数据结构：入门及复杂度的解锁
阿客不是客
23 0
java冯坚持
|
2月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
30 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
140 9
那年春天
|
26天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
24 1
龙大吉
|
13天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
32 5