【数据结构】初等二叉树(上)

简介: 【数据结构】初等二叉树(上)

☑️前言


🚩二叉树可以说是我们学习数据结构路上的第二个高的台阶,要想跨越它,需要我们多画图,多理解,多思考它的 递归 过程。前面 树的介绍 和 堆 这两篇文章让我们对树有了一定的了解,对于二叉树的概念也有说到,因此,本章不会对二叉树的概念及介绍深入去讲,而是着重于它的实现,着重于理解递归。

🚩二叉树是后面一些高阶数据结构的基础,例如:红黑树,AVL树,B树等等。并且,我们在面试当中,也经常会被面试官要求手撕二叉树的相关OJ题,所以,二叉树这一章节就显得额外重要,可不敢遇到困难就退缩了。

🚩本章实现的二叉树是一棵普通的二叉树,与之前的数据结构有所不同,它的增删查改功能没那么有意义,那么什么时候有意义呢?我们在普通二叉树的基础上加上某一性质,使其能够通过这一性质来管理左右子树,这时候的增删查改就有意义了,例如搜索二叉树等等。


搜索二叉树:


0eac6834a38a41b6b026a84bd4780024.png


fb8d21dec011483c8e1e9f885a0a81fd.png



🚩所以本章的二叉树,是打基础。我们在学习的过程中,一定要细细品味整个递归的过程,最好就是画图理解。接下来就带大家实现一棵属于自己的初等二叉树吧!


关于二叉树的补充

在实现普通二叉树之前,我们还需知道一些东西。


  • 对于 ,是采用顺序结构来存储数据的,那是因为 的逻辑结构是一棵完全二叉树,那么本章的二叉树是否也能采用顺序结构来存储数据呢?先来看下图:



a11ac6400664402a8104feea3251b7e4.png



可以看到,可以是可以,但是一棵二叉树不一定就是完全二叉树,如果采用顺序存储结构的话,这里可能会有很多的空间浪费,因此,二叉树将采用链式的储存结构来存储数据,每一个数据对应一个树结点(结构体)。由于是二叉,所以我们只需要定义两个树结点的指针分别指向该结点的左孩子和右孩子即可。


前面说了,二叉树是递归定义的,因此后面的功能接口的实现几乎全是采用递归方法。

对于一棵二叉树,我们可以把它分成根,左子树和右子树,而它的左子树和右子树又可以分为根,左子树和右子树,依次这样下去,整个二叉树就有了递归的性质了,所以为什么二叉树是递归定义的,这是很重要的原因。


46218e3861704989a0fc7775fbd7e422.png


对于二叉树的递归,一个很重要的思想 —— 分治思想 贯穿全文,它可以形象为: 一个大学的校长想统计整个学校的人数,然后这个校长就叫来1院长和2院长去统计他们各自学院的人数,然后1院长和2院长又分别叫来各自的系主任去统计各自系的人数…最后分到每个寝室长统计各自寝室的人数,等最后一层统计完后,再依次上报,最终汇总到校长手中。这就是典型的分治思想。


得到一个树的结点


  • 这里我们的普通二叉树实现都是在一个文件里:BinaryTree.c
  • 最开始我们要包含一下所需头文件:


#include <stdio.h>
// 断言所需
#include <assert.h>
// 申请空间所需
#include <stdlib.h>
// 布尔类型所需
#include <stdbool.h>


  • 得到一个树的结点,我们首先要定义一个结点的结构体。一个结点包含存储的数据和分别指向左孩子结点和右孩子结点的两个指针,定义如下:
typedef int BTDataType;
typedef struct TreeNode
{
  // 存储数据
  BTDataType data;
  // 指向左结点的指针
  struct TreeNode* left;
  // 指向右结点的指针
  struct TreeNode* right;
}BTNode;


  • 有了结点的定义之后,如何得到一个结点呢?当然是向内存申请一个结点的空间,申请之后,我们顺便将这个结点里的成员初始化:data 给自己想要的值,两个指针分别置为NULL。最后返回指向该结点空间的指针即可。

相关函数接口代码实现:

// 得到一个结点
BTNode* BuyTreeNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  // 判断一下是否申请空间失败
  assert(newnode);
  newnode->data = x;
  // 两个指针都初始化 NULL
  newnode->left = NULL;
  newnode->right = NULL;
  // 返回指向这个结点空间的指针
  return newnode;
}


自己捣鼓的二叉树


  • 有了得到一个树结点的功能后,接下来就是按照自己的意思创建一棵树了。

这里我们采用下面这棵树作为例子:



25987e68de0843dcb158be4af66d709a.png


相关函数接口代码实现:

BTNode* BuyTree()
{
  // 依次得到一个结点
  BTNode* n1 = BuyTreeNode(1);
  BTNode* n2 = BuyTreeNode(2);
  BTNode* n3 = BuyTreeNode(3);
  BTNode* n4 = BuyTreeNode(4);
  BTNode* n5 = BuyTreeNode(5);
  BTNode* n6 = BuyTreeNode(6);
  BTNode* n7 = BuyTreeNode(7);
  // 通过每个结点内的指针进行树的连接
  n1->left = n2;
  n2->left = n3;
  n1->right = n4;
  n4->left = n5;
  n4->right = n6;
  n2->right = n7;
  // 返回所有结点的祖先结点
  return n1;
}


不同的二叉树这里的代码不同,根据自己的需求来建树。


二叉树的前序遍历

  • 前序遍历的顺序是 根 - 左 - 右 ,先打印 ,然后递归左和右, 如果当前结点为 NULL,打印NULL,然后递归返回。

图示理解:


78aa539b3b1c48caaf70279db16c1023.gif


a7a97018e9314949bc5e9082a147e2ec.gif


相关函数接口代码实现:

// 二叉树的前序遍历
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  // 根 左 右
  printf("%d ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}


二叉树的中序遍历


  • 中序遍历的顺序是 左 - 根 - 右 ,先遍历该二叉树的左子树,然后根,最后右子树, 然后该二叉树的左子树和右子树又是先遍历其左子树,然后根,最后右子树,这样就分成了若干个子问题。如果当前结点为 NULL,打印NULL,然后递归返回。


图示理解:


c049b05ba8df48c687f079d548b6849b.gif


31a9c05d679e4ca4ab2681543cfdc761.gif

相关函数接口代码实现:

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


二叉树的后序遍历


  • 前序遍历的顺序是 左 - 右 - 根 ,先遍历该而二叉树的左子树,然后右子树,最后根,然后该二叉树的左子树和右子树又是先遍历其左子树,然后右子树,最后根。这样就分成了若干个子问题。如果当前结点为 NULL,打印NULL,然后递归返回。

图示理解:


cf7b172d29534a4fbe96024b06f460e4.gif

5563882e25dd40d38c9d1e922ba60c92.gif

相关函数接口代码实现:

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


二叉树的结点个数


求二叉树的结点个数,我们可以采用一种分治思想, 求 该树的左子树的结点个数加上该树的右子树的结点个数再加上自己。然后该树的左子树和右子树又可以分成 求 该子树的左子树的结点个数加上该子树的右子树的结点个数再加上自己,这样不断将问题细化,符合递归的性质。


如果该根节点为NULL,说明不是一个结点,返回0。


图示理解:


a0d15091ef3f4bd5b7048ecb554733ed.png

3d9a46d9192345e780aa5641c5c2a246.gif

相关函数接口代码实现:


// 二叉树的结点个数
int TreeNodeSize(BTNode* root)
{
  // +1 是算上自己为一个结点
  return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}
相关文章
|
26天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
87 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
27 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
28 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
25 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
28 0
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
2月前
|
存储
【数据结构】二叉树零基础无压力上手,超详解
【数据结构】二叉树零基础无压力上手,超详解
30 0