数据结构入门(C语言版)二叉树链式结构的实现

简介: 从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。

60cc048de8fb4b98b746449c16ceea25.png


二叉树的概念及结构创建


1、概念


简单回顾一下二叉树的概念:

★ 空树

★非空:根节点,根节点的左子树、根节点的右子树组成的。


ef30581884964bdcb6b967fdb4b61ee8.jpg


95b14432078d400c97564d9016e12c36.jpg


从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。


2、结构创建


下面我们先看二叉树的结构体定义以及创建


typedef char BTDataType;
typedef struct BinaryTreeNode
{
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
  BTDataType data;
}BTNode;


首先结构体的定义是元素本身,以及左右子树的指针。


2、创建结点函数


BTNode* BuyNode(BTDataType x)
{
  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
  if (node == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  node->data = x;
  node->left = node->right = NULL;
  return node;
}


我们指定每调用一次此函数,便新建一个结点空间,并将左右指针指向空即可。


3、建树函数


BTNode* CreatBinaryTree()
{
  BTNode* nodeA = BuyNode('A');
  BTNode* nodeB = BuyNode('B');
  BTNode* nodeC = BuyNode('C');
  BTNode* nodeD = BuyNode('D');
  BTNode* nodeE = BuyNode('E');
  BTNode* nodeF = BuyNode('F');
  nodeA->left = nodeB;
  nodeA->right = nodeC;
  nodeB->left = nodeD;
  nodeC->left = nodeE;
  nodeC->right = nodeF;
  return nodeA;
}


这个函数是树建立的关键步骤,将每个结点创建完成后,再将每个结点的左右指针重定义,继而完成建树,上述代码执行后表示的就是下图:


aabeb1ea895c47dcac2269cd616473f9.jpg


二叉树的遍历


学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。


190e76fac2a844c0a5cf6b86ef7505b7.jpg


主要分为以下几种:


1、前序遍历


前序遍历(Preorder Traversal | 先序遍历)——访问根结点的操作发生在遍历其左右子树之前,顺序为:根 ->左子树->右子树

比如上面这个二叉树前序遍历输出为:

A B D NULL NULL NULL C E NULL NULL F NULL NULL

实现代码如下:


void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
  printf("%c ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}


这个函数的实现是利用前序的性质,首先取根节点,之后每个结点先返回左结点,再返回右结点的顺序,进行递归调用,到最后的叶子结点之后再逐个返回打印输出,即为前序遍历。


2、中序遍历


中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中。

顺序为:左子树 ->根->右子树

比如这个二叉树中序遍历输出为:

NULL D NULL B NULL A NULL E NULL C NULL F NULL

实现代码如下:


void InOrder(BTNode* root)
{
  if (root == NULL){
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%C ", root->data);
  InOrder(root->right);
}


中序遍历就是将前序稍微做调整,先打印左子树,再打印根,之后才是右子树,同样用的是递归分治。


3、后序遍历


后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

顺序为:左子树 ->右子树->根

比如这个二叉树中序遍历输出为:

NULL NULL D NULL B NULL NULL E NULL NULL F C A

实现代码如下:


void PostOrder(BTNode* root)
{
  if (root == NULL){
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%C ", root->data);
}


此函数与上面两个同理而得。


4、层序遍历


除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。


e9f2c37d0a0b4bfb86fa78bf52109a1f.jpg


比如这个二叉树,层序遍历结果为123456。

代码实现如下:


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);
  }
  printf("\n");
  QueueDestroy(&q);
}


因为是链式结构,这里的层序遍历采用队列来实现,不了解队列的小伙伴可以看看我之前的文章:栈和队列之队列的介绍及实现

首先我们建立一个队列,初始化后先入根,再出根打印,继续打印其左右结点,继而循环打印,直到为空终止,最后释放队列空间,完成层序遍历打印。


二叉树的销毁


代码如下:


void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
}


销毁与前中后序的实现一样,使用递归自下而上销毁。


结语


有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出

感谢大家的来访,UU们的观看是我坚持下去的动力

在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!


d0066077527b4b9cbb32c4b7a39cf2e3.png

相关文章
|
3月前
|
存储 C语言
c语言——二叉树
二叉树的概念在这里就不进行过多的赘述,那么主要说一下我认为重要的部分,第一点就是二叉树里面部分概念的理解:就比如说,你对于如何构建二叉树,掌握的十分深刻,但刷题的时候对于一些题目所给的概念不清楚,导致看不明白题目,这课不好,二叉树的概念如下图所示,其实都很简单,主要是当给他的名字时,你明不明白。还有对于满二叉树与完全二叉树。
66 0
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
182 10
 算法系列之数据结构-二叉树
|
7月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
8月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
8月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
180 12
|
8月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
162 10
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
258 3
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
217 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
47 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。