AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

万字超全详解：二叉树的基本操作（C语言版本）（上）

2023-07-27 994
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 万字超全详解：二叉树的基本操作（C语言版本）（上）

image.png

前言

本文主要内容：

          1.对于二叉树的基本操作，创建 、遍历 、前序、中序、后序输出等

          2.关于二叉树的自己的体会

提示：以下是本篇文章正文内容，下面案例可供参考

一、二叉树是什么？

二叉树是数据结构中的一种，可以通过顺序表或者链表的形式实现，接下来让我们一起来看看如何通过顺序表或者链表的形式来实现二叉树

二叉树图：

   

二、二叉树的创建（以顺序表的形式）

1.先创建数组（为了顺序表做准备）

代码如下（示例）：

#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];
TElemType Nil = '#';   我们规定当元素数值为 ‘#’ 的时候表示该节点为NULL

2.输入数值

代码如下（示例）：

void input(TElemType* x) {
    scanf("%c", &x);
}      简单明了的传参  TElemType也就是char类型的变量  x

3.输出数值

void visit(TElemType x) {
  printf("%c", x);
}

4.创建空二叉树并在二叉树中输入数值

void InitBiTree(SqBiTree T) {
  //构造空二叉树
  for (int i = 0; i < MAX_SIZE; i++) {
    T[i] = Nil;//初始值为空  #表示为空
  }
}
void CreateBiTree(SqBiTree T) {
  int i = 1;//按照层次次序输入二叉树中结点的值
  scanf("%s", T + 1);
  while (T[i]!='\0')
  {
    i++;
  }
  T[i] = '#';
}

5.判断是否为空二叉树

int BiTreeEmpty(SqBiTree T) {
  //初始条件：二叉树T存在。操作结果为：若T为空二叉树，则返回true 否则false
  if (T[1] == Nil) {
    return 1;//空
  }
  else {
    return 0;
  }
}

6.返回二叉树的深度

//返回二叉树的深度
int BiTreeDepth(SqBiTree T) {
  int i = MAX_SIZE - 1;
  while (T[i] == '#') {
    i--;
  }
  //现在得到的i是存储元素的最后一位
  int j = i;
  int dep = 0;
  while (j >= 1) {
    dep++;
    j = j / 2;//根据的是树的深度为 【log2n】+1
  }
  return dep;
 }

7.先序遍历输出二叉树

这里的先序遍历是通过二叉树的一个性质来输出的，二叉树的性质之一：把完全二叉树的节点按照顺序写好对应坐标之后，i 节点的左右孩子的坐标位置分别为 2 * i  和  2 * i + 1；

void PreTraverse(SqBiTree T, int e) {
  if (T[e] != '#') {
    visit(T[e]);
    PreTraverse(T, 2 * e);
    PreTraverse(T, 2 * e + 1);//遍历输出结点 左子树 右子树
  }
}    这个函数就涉及到二叉树的一个性质 通过2*e和2*e+1来进行遍历
void  PreOrderTraverse(SqBiTree T) {
  //先序遍历
  if (!BiTreeEmpty(T)) {
    //非空就调用PreTraverse
    PreTraverse(T, 1);//从第一个元素就开始
  }
  printf("\n");
}

8.中序遍历输出二叉树

void InTraverse(SqBiTree T, int e) {
  //中序遍历使用
  if (T[e] != '#') {
    InTraverse(T, 2 * e);
    visit(T[e]);
    InTraverse(T, 2 * e + 1);//中序遍历，先左后中再右
  }
}
void InOrderTreaverse(SqBiTree T) {
  if (!BiTreeEmpty(T)) {
    InTraverse(T, 1);
  }
  printf("\n");
}

9.后序遍历输出二叉树

//后序遍历
void PostTreaverse(SqBiTree T, int e) {
  if (T[e] != '#') {
    PostTreaverse(T, e * 2);
    PostTreaverse(T, e * 2 + 1);
    visit(T[e]);
  }
}
void PostOrderTraverse(SqBiTree T) {
  if (!BiTreeEmpty(T)){
    PostTreaverse(T, 1);
  }
  printf("\n");
}

10.层序遍历输出二叉树

//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T) {
  int dep = BiTreeDepth(T);
  int tree_max = pow(dep, 2) - 1;//得到当前深度下完全二叉树应该有多少结点
  for (int i = 1; i < tree_max; i++) {
    if (T[i] == '#') {
      continue;
    }//不用输出‘#’  而且获得的深度来看，不需要for很多没有价值的 下标  牛逼
    visit(T[i]);
  }
}

11.总结：（全部代码实现）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//使用顺序结构完成二叉树的基本操作
//编写前序、中序、后序以及层次顺序遍历二叉树的算法，并计算二叉树的深度、所有的结点数
#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];
TElemType Nil = '#';
void input(TElemType* x) {
  scanf("%c", &x);
}
void visit(TElemType x) {
  printf("%c", x);
}
void InitBiTree(SqBiTree T) {
  //构造空二叉树
  for (int i = 0; i < MAX_SIZE; i++) {
    T[i] = Nil;//初始值为空  #表示为空
  }
}
void CreateBiTree(SqBiTree T) {
  int i = 1;//按照层次次序输入二叉树中结点的值
  scanf("%s", T + 1);
  while (T[i]!='\0')
  {
    i++;
  }
  T[i] = '#';
}
int BiTreeEmpty(SqBiTree T) {
  //初始条件：二叉树T存在。操作结果为：若T为空二叉树，则返回true 否则false
  if (T[1] == Nil) {
    return 1;//空
  }
  else {
    return 0;
  }
}
//返回二叉树的深度
int BiTreeDepth(SqBiTree T) {
  int i = MAX_SIZE - 1;
  while (T[i] == '#') {
    i--;
  }
  //现在得到的i是存储元素的最后一位
  int j = i;
  int dep = 0;
  while (j >= 1) {
    dep++;
    j = j / 2;//根据的是树的深度为 【log2n】+1
  }
  return dep;
 }
void PreTraverse(SqBiTree T, int e) {
  if (T[e] != '#') {
    visit(T[e]);
    PreTraverse(T, 2 * e);
    PreTraverse(T, 2 * e + 1);//遍历输出结点 左子树 右子树
  }
}
void  PreOrderTraverse(SqBiTree T) {
  //先序遍历
  if (!BiTreeEmpty(T)) {
    //非空就调用PreTraverse
    PreTraverse(T, 1);//从第一个元素就开始
  }
  printf("\n");
}
void InTraverse(SqBiTree T, int e) {
  //中序遍历使用
  if (T[e] != '#') {
    InTraverse(T, 2 * e);
    visit(T[e]);
    InTraverse(T, 2 * e + 1);//中序遍历，先左后中再右
  }
}
void InOrderTreaverse(SqBiTree T) {
  if (!BiTreeEmpty(T)) {
    InTraverse(T, 1);
  }
  printf("\n");
}
//后序遍历
void PostTreaverse(SqBiTree T, int e) {
  if (T[e] != '#') {
    PostTreaverse(T, e * 2);
    PostTreaverse(T, e * 2 + 1);
    visit(T[e]);
  }
}
void PostOrderTraverse(SqBiTree T) {
  if (!BiTreeEmpty(T)){
    PostTreaverse(T, 1);
  }
  printf("\n");
}
//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T) {
  int dep = BiTreeDepth(T);
  int tree_max = pow(dep, 2) - 1;//得到当前深度下完全二叉树应该有多少结点
  for (int i = 1; i < tree_max; i++) {
    if (T[i] == '#') {
      continue;
    }//不用输出‘#’  而且获得的深度来看，不需要for很多没有价值的 下标  牛逼
    visit(T[i]);
  }
}
int main()
{
  TElemType e;
  SqBiTree Bt;
  InitBiTree(Bt);
  CreateBiTree(Bt);
  printf("先序遍历结果为：");
  PreOrderTraverse(Bt);
  printf("中序遍历结果为：");
  InOrderTreaverse(Bt);
  printf("后序遍历结果为：");
  PostOrderTraverse(Bt);
  LevelOrderTraverse(Bt);
  return 0;
}


文章标签：
C语言
关键词：
C语言二叉树
二叉树C语言
C语言版本
C语言基本操作
二叉树基本操作C语言版本
容颜寄语-26413
目录
相关文章
hahaha无
|
7月前
|
存储 C语言
c语言——二叉树
二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，第一点就是二叉树里面部分概念的理解：就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。还有对于满二叉树与完全二叉树。
hahaha无
221 0
ephemerals__
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
1270 8
小徐在进步
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
393 6
小徐在进步
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
379 3
小徐在进步
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
小徐在进步
423 2
小徐在进步
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
481 2
梦笔生花伟
|
机器学习/深度学习 存储 C语言
C语言的二叉树
1.树概念及结构 1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 补充定义: 有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。 1.2 树的相关概念 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6 叶节点或终端
梦笔生花伟
93 0
osswangxining
|
4月前
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数，通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配，并建议检查返回值以确保读取成功，提升程序健壮性。
osswangxining
1109 0
RossyYan
|
存储 算法 C语言
【C语言程序设计——函数】素数判定（头歌实践教学平台习题）【合集】
本内容介绍了编写一个判断素数的子函数的任务，涵盖循环控制与跳转语句、算术运算符（%）、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码，测试说明提供了输入输出示例，最后给出通关代码和测试结果。 任务核心：编写判断素数的子函数并在主函数中调用，涉及循环结构和条件判断。
RossyYan
760 23
蓝易云
|
6月前
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用，可以有效管理字符串和内存操作，它们是C语言编程中不可或缺的工具。
蓝易云
356 15