【数据结构】二叉树(C语言实现)

简介: 【数据结构】二叉树(C语言实现)

一、树的概念及结构

1、树的概念

树是一种非线性数据结构,它是由n(n>=0)个有限结点组成的一个具有层次关系的集合;它被称为树因为其看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

image.png

树有一个特殊的结点,称为根结点,根节点没有前驱结点;除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树;每棵子树的根结点有且只有一个前驱,可以有0个或多个后继;因此,树是递归定义的。

2020062310470442.png

注意:树形结构中,子树之间不能有交集,否则就不是树,而是另外一种数据结构 – 图。

2020062310470442.png

2、树的相关名词

2020062310470442.png

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A节点的度为6 ;

叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点;

非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点;

双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点;

孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点;

兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点;

树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6;

节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

树的高度或深度:树中节点的最大层次; 如上图:树的高度为4;

堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点;

节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先;

子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙;

森林:由m(m>0)棵互不相交的树的集合称为森林;

3、树的表示

树结构相对线性表比较复杂,要存储表示起来比较麻烦,不仅需要保存值域,还要保存结点和结点之间的关系;实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等;其中最常用的表示法为:孩子兄弟表示法 (左孩子右兄弟表示法)。

typedef int DataType;
struct Node
{
  struct Node* firstChild1;   //存放第一个孩子结点的地址
  struct Node* pNextBrother;  //存放下一个兄弟结点的地址
  DataType data;    //结点中的数据域
};

2020062310470442.png

4、树在实际生活中的应用

树在我们实际生活中的应用之一就是用于表示文件系统的目录:

2020062310470442.png

二、二叉树的概念及结构

1、二叉树的概念

一棵二叉树是结点的一个有限集合,该集合由一个根节点加上两棵分别称为左子树和右子树的二叉树组成,该集合也可能为空。

2020062310470442.png

从上图可以看出,二叉树有以下特点:

1、二叉树不存在度大于2的结点;


2、二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树;

注意:对于任意的二叉树都是由以下几种情况复合而成的:

2020062310470442.png

ps:现实中的二叉树:

2020062310470442.png

2、特殊的二叉树

满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树;也就是说,如果一个二叉树的层数为K,且结点总数是 2^K-1,则它就是满二叉树。


完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的;对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树;要注意的是满二叉树是一种特殊的完全二叉树。

2020062310470442.png

3、二叉树的性质

任意层数的最大节点数: 若规定根节点的层数为1,则一棵非空二叉树的第 i 层上最多有 2^(i-1) 个结点;


最大节点数: 若规定根节点的层数为1,则深度为 h 的二叉树的最大结点数是 2^h-1;


叶节点数和度为2的分支节点数的关系: 对任何一棵二叉树, 如果度为0的叶结点个数为 n , 度为2的分支结点个数为 m,则有 n = m + 1,即二叉树的叶节点数始终比度为2的分支节点数多1;

解析:如下图所示

2020062310470442.png

当二叉树之有一个节点时,叶节点数为1,度为2的分支节点数为0;此时叶节点数比度为2的分支节点数多1;


当我们增加一个度为1的分支节点时,会消耗一个叶节点,但是同时又会产生一个新的叶节点;所以增加度为1的分支节点时叶节点数量不变;


当我们增加一个度为2的分支节点时,我们会同时产生一个叶节点;所以叶节点数始终比度为2的分支节点数多1;

树的深度: 若规定根节点的层数为1,具有n个结点的满二叉树的深度为:h= log (n+1); ( log以2为底)


节点数与边条数的关系: 对于任意的树都满足边的条数比节点个数少1,因为每个节点都有双亲,但是根节点没有


顺序存储中父节点和子节点的位置关系: 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于下标为 i 的结点有:如果 i == 0,则该节点为根节点,无父节点;如果 i > 0,则其父节点的下标为:(i-1) / 2;


其左孩子的下标为 2i + 1,如果 2i + 1 < n,说明该节点不是叶节点,存在子节点;如果 2i + 1 > n,说明该节点是叶节点,不存在子节点;


其右孩子的下标为 2i + 2,如果 2i + 2 < n,说明该节点不是叶节点,存在子节点;如果 2i + 2 > n,说明该节点是叶节点,不存在子节点;

二叉树性质相关选择题

1、某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )

A 不存在这样的二叉树

B 200

C 198

D 199

答案:B 根据上面的结论 – 叶节点数始终比度为2的分支节点数多1可以直接得出答案。

2、在具有 2N 个结点的完全二叉树中,叶子结点个数为( )

A N

B N+1

C N-1

D N/2

答案:A 通过完全二叉树的概念我们知道,完全二叉树中只存在三种节点:度为2的节点、度为0的节点 (叶节点) 以及度为1的节点,其中度为1的节点要么不存在,要么只存在一个;那么我们就可以得到下面的式子:n + p + m = 2N (分别代表度为0 1 2),又根据叶节点数始终比度为2的分支节点数多1,化简得:2n - 1 + p = 2N,因为2n 和 2N 都为偶数,所以度为1的节点只能是1,所以 n = N;

3、一棵完全二叉树的节点数位为531个,那么这棵树的高度为( )

A 11

B 10

C 8

D 12

答案: B 我们知道,高度为 h 的完全二叉树的节点数为:N = 2^(h-1) ~ 2^(h) - 1,把531带入其中就可以得到答案。

4、二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构;

顺序存储:顺序结构存储就是使用数组来存储,这种存储结构一般只适合表示完全二叉树,因为其他二叉树用此结构存储有空间的浪费;而现实使用中只有才会使用数组来存储;二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2020062310470442.png

链式存储:二叉树的链式存储结构是指用链来表来表示一棵二叉树,即用链来指示元素的逻辑关系;通常是链表中每个结点由三个域组成:数据域和左右指针域;左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址;链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,三叉链会在高阶数据结构如红黑树中使用到。2020062310470442.png

2020062310470442.png

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
  struct BinTreeNode* pLeft;    // 指向当前节点左孩子
  struct BinTreeNode* pRight;   // 指向当前节点右孩子
  BTDataType _data;   // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
  struct BinTreeNode* pParent;   // 指向当前节点的双亲
  struct BinTreeNode* pLeft;     // 指向当前节点左孩子
  struct BinTreeNode* pRight;    // 指向当前节点右孩子
  BTDataType data;   // 当前节点值域
};

三、链式二叉树的实现

1、结构的定义

//符号和结构的定义
typedef char BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

2、构建二叉树

由于二叉树不能进行增加和删除操作,所以一般都是给定一个字符串,该字符串中含有需要我们构建的二叉树的所有节点,我们通过读取字符串中的内容来构建二叉树。

注意:字符串中的 # 表示空树,即上一个节点没有左子树或右子树。

//通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
  if (a[*pi] == '#')
  {
    (*pi)++;
    return NULL;
  }
  //创建根节点
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  root->data = a[*pi];
  (*pi)++;
  //创建左右子树
  root->left = BinaryTreeCreate(a, pi);
  root->right = BinaryTreeCreate(a, pi);
  return root;
}

3、二叉树节点个数

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  //左子树节点个数+右子树节点个数+根节点
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

4、二叉树叶节点个数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  //没有子节点代表该节点为叶节点
  if (root->left == NULL && root->right == NULL)
    return 1;
  //左子树叶节点个数+右子树叶节点个数
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

5、二叉树第K层节点个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  //转化为求第K-1层的节点个数
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

6、在二叉树中查找值为X的节点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  //去左子树找,找到就返回
  BTNode* left = BinaryTreeFind(root->left, x);
  if (left != NULL)
    return left;
  //去右子树找,找到就返回
  BTNode* right = BinaryTreeFind(root->right, x);
  if (right != NULL)
    return right;
  //如果左右子树都没有,就返回空
  return NULL;
}

7、二叉树前序遍历

二叉树一共有四种遍历方式:前序遍历、中序遍历、后序遍历以及层序遍历;


前序遍历:先访问根节点,再访问左子树,最后访问右子树;


中序遍历:先访问左子树,再访问根节点,最后访问右子树;


后序遍历:先访问左子树,再访问右子树,最后访问根节点;


层序遍历:按照二叉树的逻辑结构,先访问第一层层的所有节点,再访问第二层的所有节点,依次向下访问。

// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  //先访问根,再访问左子树,最后访问右子树
  printf("%c ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}

8、二叉树中序遍历

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  //先访问左子树,再访问根,最后访问右子树
  BinaryTreeInOrder(root->left);
  printf("%c ", root->data);
  BinaryTreeInOrder(root->right);
}

9、二叉树后序遍历

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  //先访问左子树,再访问右子树,最后访问根
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%c ", root->data);
}

10、二叉树层序遍历

区别其他三种遍历方式,层序遍历采用的是非递归,其具体思路是:


利用一个队列来存储二叉树节点的地址,先让父节点入队列,然后让父节点出队列,但是在父节点出队列的同时会让父节点的左右字孩子入队列 (如果没有左右孩子就不入),这样就使得当这一层的节点全部出队列时,下一层的节点刚好全部入队列,最后当队列为空时,二叉树的节点就全部访问完了。


注意:1、由于我们需要队列来存储二叉树节点的地址,所以这里我们需要把我们之前写的队列 – Queue.h 和 Queue.c 添加到当前工程中;2、同时,我们需要将二叉树节点的结构体需要定义在队列结构体之前。

// 二叉树层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  if (root == NULL)
    return;
  //将节点的地址存储在队列中,取出一个节点的同时将该节点的子节点入栈
  Queue q;
  QueueInit(&q);
  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);
  }
  QueueDestory(&q);
}

11、判断二叉树是否是完全二叉树

我们知道,完全二叉树的前 h-1 层都是满二叉树,最后一层不一定是满二叉树,但是最后一层的节点必须是有序的;也就是说:当完全二叉树遇到空节点之后,后面就不会再出现节点,否则,就是非完全二叉树;


根据上面这个性质,我们可以利用层序遍历来判断二叉树是否为完全二叉树:对二叉树进行层序遍历,与普通层序遍历不同的是,当节点的孩子为空时,我们仍然入队列;当队顶的元素为空时,停止循环,检查队列中剩余的元素,如果剩余元素中存在非空节点,则不是完全二叉树,否则就是完全二叉树。

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  if (root == NULL)
    return false;
  //将节点的地址存储在队列中,取出一个节点的同时将该节点的子节点入栈
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    //取出队顶的元素
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    //当遇到data为空的节点时跳出循环
    if (front == NULL)
      break;
    //将队顶元素的左右子节点入队列
    QueuePush(&q, front->left);
    QueuePush(&q, front->right);
  }
  //遇到空以后,如果后面的节点全为空,则是完全二叉树;否则就是非完全二叉树
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestory(&q);
      return false;
    }
  }
  QueueDestory(&q);
  return true;  //前面没有返回说明是完全二叉树
}

12、销毁二叉树

和带头双向循环链表一样,为了保持接口的一致性,这里我们不使用二级指针,使用需要函数调用者在函数外部手动将根节点置空。

// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
  //通过后序遍历来销毁节点
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);  //此处置空不会影响外面,需要在外面进行置空
}

四、完整代码

由于二叉树中还调用了队列,代码较多,所以这里我直接给出码云仓库的地址,需要完整代码的同学可以在上面自取:

BinaryTree/BinaryTree · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)



相关文章
|
24天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
24天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
26天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
26天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。
|
26天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
26天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
C语言 Linux
c语言二叉树--实现
/*系统环境:centos 5.8  *  *  */ #include #include #define MAXSIZE 200 struct node {     int score;     struct node *left;     struct...
727 0
|
23天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数,`gets`用于从标准输入读取字符串直至换行符,并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外,文章还详细讲解了`str`系列字符串操作函数,包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符,每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容,提供了丰富的示例帮助理解。通过对本文的学习,读者可以全面掌握C语言中的位运算和文件处理技术。
|
26天前
|
存储 C语言
C语言程序设计核心详解 第七章 函数和预编译命令
本章介绍C语言中的函数定义与使用,以及预编译命令。主要内容包括函数的定义格式、调用方式和示例分析。C程序结构分为`main()`单框架或多子函数框架。函数不能嵌套定义但可互相调用。变量具有类型、作用范围和存储类别三种属性,其中作用范围分为局部和全局。预编译命令包括文件包含和宏定义,宏定义分为无参和带参两种形式。此外,还介绍了变量的存储类别及其特点。通过实例详细解析了函数调用过程及宏定义的应用。