数据结构-二叉树的前、中、后序遍历

简介: 数据结构-二叉树的前、中、后序遍历

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\n");
    return NULL;
  }
  node->left = NULL;
  node->right = NULL;
  node->data = x;
  return node;
}
BTNode* CreatBinaryTree()
{
  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;
}

下图就是我们上述代码创建的二叉树,从今天开始,我们看到二叉树要将其分为三个部分:根、左子树、右子树

图中每个子树也能再分为根和左子树、右子树,直到不能再分为止。

二叉树的遍历分为:前序、中序、后序、层序。今天先来学习前中后序,层序后面再学。

1.1 前序

前序要求的访问次序:根、左子树、右子树

按照前序的访问规则,对上述代码的节点的访问次序依次是: 1 2 3 null null null 4 5 null null 6 null null

先访问根节点1,然后访问它的左子树,左子树中先访问根节点2,然后访问2的左子树3,3的左右子树是null null,然后继续访问2的右子树为null,接着访问1的右子树,右子树中先访问根节点4,然后访问4的左子树5,再访问5的左右子树null null,接着访问4的右子树6,6的左右子树是null null,所以最终的访问次序是:1 2 3 null null null 4 5 null null 6 null null

前序的代码实现:

//前序
void PrevOrder(BTNode* root)
{
  if (root==NULL)
  {
    printf("null ");
    return;
  }
  printf("%d ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  PrevOrder(root);
  printf("\n");
  return 0;
}

打印结果:

递归过程如下:

递归调用的过程实际就是函数栈帧的创建与销毁的过程,每次调用完左子树,它的栈帧就销毁了,调用右子树时会共用左子树的栈帧。

1.2 中序

中序要求的访问次序:左子树、根、右子树

按照中序的访问规则,对上述代码中的节点的访问次序依次是:null 3 null 2 null 1 null 5 null 4 null 6 null

因为每个子树都可以被拆成左子树、根和右子树,而且在访问时左子树的优先级高,左子树可以一直分到3,所以从3的左子树开始访问:null 3 null,然后把null 3 null作为2的左子树,再访问2和2的右子树:null 3 null 2 null,接着把 null 3 null 2 null 作为1的左子树,访问1和1的右子树......,最终访问的次序应该是:null 3 null 2 null 1 null 5 null 4 null 6 null

中序代码实现:

//中序
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("null ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  //前序
  PrevOrder(root);
  printf("\n");
  //中序
  InOrder(root);
  printf("\n");
  return 0;
}

运行结果:

1.3 后序

后序要求的访问次序:左子树、右子树、根

按照后序的访问规则,对上述代码中的节点的访问次序依次是:null null 3 null 2 null null 5 null null 6 4 1。 与分析前序和中序一样,这里不再详解。

后序代码实现:

//后序
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("null ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  //前序
  PrevOrder(root);
  printf("\n");
  //中序
  InOrder(root);
  printf("\n");
  //后序
  PostOrder(root);
  printf("\n");
  return 0;
}

运行结果:

以上就是二叉树的前、中、后序遍历了,这几种方式其实就是对根的访问的先后问题,如果上述内容还不是很明白,最好画一下递归调用图,这样就很清楚了。

1.4 遍历的复杂度

时间复杂度:O(N),因为二叉树一共有N个节点,递归一共调用N次,所以时间复杂度是O(N)。

空间复杂度:O(h),h的范围是:[ logN, N ]

为什么空间复杂度是这样的呢?

我们前面的章节中讲过,时间是一去不复返的,所以时间要累加计算,而空间是可以共用的,所以空间不能累加计算。我们在调用函数时,左子树调用完,它的栈帧会销毁,而调用右子树时,它会共用左子树的栈帧,而假设二叉树有N个节点,当它是满二叉树时,由于左右子树共用一个空间,只需创建空间logN次,而如果二叉树像下图中的情况,它就要创建空间N次,所以空间复杂度是:O(logN~N)

2.二叉树节点个数及高度的计算

2.1 二叉树节点个数

法一:

要计算二叉树节点个数,我们只需要将二叉树遍历一遍(前、中、后序都可以),每次调用时使size++即可,注意size要定义为全局变量,防止每次调用的时候size被置为0

代码如下:

//二叉树节点个数
int size = 0;
int BTreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  size++;
  BTreeSize(root->left);
  BTreeSize(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  BTreeSize(root);
  printf("BTreeSize:%d\n", size);
  return 0;
}

法二:

把计算节点个数分为,左子树节点个数+右子树节点个数+根节点个数,而每个子树还能分为左子树、右子树和根,所以我们使用递归的思想,如果根节点不为空,就分别计算它的左右子树节点个数+它自身,如果为空,就返回0。

代码如下:

//二叉树节点个数
int BTreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  return  BTreeSize(root->left) + BTreeSize(root->right)+1;
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("BTreeSize:%d\n", BTreeSize(root));
  return 0;
}

运行结果:

2.2 二叉树叶子节点的个数

要计算叶子节点,也可以使用上述分开计算的方法,分别计算左子树和右子树的叶子节点个数,然后相加,递归的条件是:如果左子树和右子树的节点都是NULL,那说明是叶子节点,返回1,否则,说明是分支节点,继续往下递归

代码如下:

//二叉树叶子节点
int BLeafNum(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  if (root->left == NULL && root->right == NULL)
  {
    return 1 ;
  }
  return BLeafNum(root->left) + BLeafNum(root->right);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("BLeafNum:%d\n", BLeafNum(root));
  return 0;
}

运行结果:

2.3 二叉树高度

求二叉树高度,也可以分别求左子树和右子树的高度,然后比较大小,返回大的值,并将该值加一就是二叉树的高度加一是因为左右子树距离根节点还有一层

求左右子树的高度可以再分解为上面的步骤,所以使用递归解决问题。

代码如下:

//二叉树高度
int BTreeHeight(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int LeftNum = BTreeHeight(root->left);
  int RightNum = BTreeHeight(root->right);
  return LeftNum > RightNum ? LeftNum + 1 : RightNum + 1;
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf(" BTreeHeight:%d\n", BTreeHeight(root));
  return 0;
}

运行结果:

2.4 二叉树第k层节点个数

该问题可以转换成:分别求左子树的第k-1层和右子树的第k-1层,然后返回它们的和

结束条件是:k==1 且k不为空

比如我们要求1的第三层,就是求2和4的第二层,也就是求3 5 6的第一层

代码如下:

//二叉树第k层节点的个数
int BTreekNum(BTNode* root,int k)
{
  if (root == NULL)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  return BTreekNum(root->left, k - 1) + BTreekNum(root->right, k - 1);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("BTreekNum:%d\n", BTreekNum(root,3));
  printf("BTreekNum:%d\n", BTreekNum(root, 2));
  return 0;
}

运行结果:

递归过程如下:

通过以上计算,相信我们对二叉树的遍历有了更深的理解,同时也加深了对递归的理解,其实当我们熟练运用递归之后,递归问题都可以分两步解决:1. 找出子问题  2. 递归条件

 

以上就是今天学习的所有内容了,未完待续。。。

目录
相关文章
|
14天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略,从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成,具有层次关系。二叉树每个节点最多有两个子树,分为左子树和右子树。文中详细描述了二叉树的不同类型,如完全二叉树、满二叉树、平衡二叉树及搜索二叉树,并阐述了二叉树的基本性质与存储方式。此外,还介绍了二叉树的实现方法,包括节点定义、遍历方式(前序、中序、后序、层序遍历),并提供了多个示例代码,帮助理解二叉树的基本操作。
38 13
【数据结构】二叉树全攻略,从实现到应用详解
|
11天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
11天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
11天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
1月前
|
存储
【初阶数据结构篇】二叉树基础概念
有⼀个特殊的结点,称为根结点,根结点没有前驱结点。
|
1月前
|
算法
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
【数据结构】树、二叉树与堆(长期维护)(2)
|
1月前
|
算法
【初阶数据结构篇】二叉树算法题
二叉树是否对称,即左右子树是否对称.
|
1月前
|
存储
【初阶数据结构篇】实现链式结构二叉树(二叉链)下篇
要改变root指针的指向,将本来指向根节点的root指针改为空,所以传二级指针(一级指针也可以,只不过在调用完记得把root置为空)。
|
1月前
|
存储 测试技术
【初阶数据结构篇】实现链式结构二叉树(二叉链)上篇
先构建根结点,再对左右子树构建,每次需要时申请一个结点空间即可,否则返回空指针。
|
1月前
|
存储 算法 测试技术
【初阶数据结构篇】实现顺序结构二叉树(堆的实现方法)
注意传过去的参数是插入的位置,即插入前的size,在调整完后再将size++