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

二叉树的链式结构 - C语言（含有大量递归）下

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

🍔 构建二叉树


   🚩构建二叉树的时候要先来引用一道牛客网的题目 二叉树遍历_牛客题霸_牛客网 (nowcoder.com)这个是它的链接可以试着去做一下


✅ 题目要求：


       编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。


🥝 示例：


输入：abc##de#g##f###                  


输出：c b e g d f a


🍟示例的实际图应该是下图这样的一颗树


082ad718504c775ca9d7ea5d72225f1a_fb5c9888ba8940ab953c61e3d8e10a34.png


🥰解题思路：  这个题目要我们构造一个链式二叉树，在先序遍历的过程中构建每一个节点。


 😍代码：


#include <stdio.h>
#include <malloc.h>
typedef struct BTNode
{
    char _data;
    struct BTNode* _left;
    struct BTNode* _right;
}BTNode;
//中序遍历
void Inorder(BTNode* root)
{
    if(root)
    {
        Inorder(root->_left);
        printf("%c ", root->_data);
        Inorder(root->_right);
    }
}
BTNode* CreatBTree(char* str, int* pi)
{
    if(str[*pi]!= '#')
    {
        //当前节点非空，则创建当前节点
        BTNode*root=(BTNode*)malloc(sizeof(BTNode));
        root->_data = str[*pi];
        //字符位置向后移动一个位置
        ++(*pi);
        //创建左子树
        root->_left=CreatBTree(str,pi);
        //字符位置向后移动一个位置
        ++(*pi);
        //创建右子树
        root->_right=CreatBTree(str,pi);
        return root;
    }
    else
        return NULL;  //如果是空节点，则返回NULL
}
int main()
{
    char str[101];
    int i = 0;
    //读入字符串
    scanf("%s", str);
    //创建二叉树
    BTNode* root = CreatBTree(str, &i);
    //中序打印二叉树
    Inorder(root);
    printf("\n");
    return 0;
}


🍔二叉树销毁


😍代码：  


// 二叉树销毁—递归实现
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)  
  {
  return;
  }
  BinaryTreeDestory(root->right);  
  BinaryTreeDestory(root->left);
  free(root);
}

       ✅运用后序遍历（因为如果先释放根节点的话就不能直接找到左右子树了）来实现递归二叉树销毁，结束标志是遇见空节点返回上一级。


🍔二叉树节点个数


😍代码：


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

       ✅运用递归（前序）简化了问题，即：二叉树节点个数 = 左子树节点数 + 右子树节点数 + 1


       ✅递归结束条件是遇到空节点返回 0。


🍔二叉树叶子节点个数


😍代码：


// 二叉树叶子节点个数
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);
}

🍎叶子节点的概念：度为0的节点称为叶节点


       🍟运用递归（前序）简化了问题，即：二叉树叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数


      🍟递归结束条件是遇到空节点返回 0， 该节点的左子树节点为空 并且 右子树节点为空，则该节点为叶子节点，返回1。


🍔二叉树第k层节点个数


😍代码： 


// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0); //k的值不能为负数
  if (k == 1 && root)  //第k层的判断条件
  {
  return 1;
  }
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

🍎层的概念：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；


       🍟不满足第k层的判断条件的不计数,（继续递归下去），当满足第K层的条件的就返回1（返回上一级的函数中）


🍔二叉树查找值为x的节点


😍代码：


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
  return NULL;
  }
  if (root->data == x)
  {
  return root;
  }
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret1)
  return ret1;
  if (ret2)
  return ret2;
  return NULL;
}


       ✅运用递归（前序）简化了问题，即：二叉树中等于X的节点个数 = 左子树等于X的节点个数 + 右子树等于X的节点个数


       ✅等于空，或者等于这个要找的值为这里的结束条件，返回的是值等于X的节点指针。这里用了两个临时变量来储存左右两边的个数，这样做可以在返回的时候直接返回，不用再一次的计算。🥰


🍔判断二叉树是否是完全二叉树


69234c5c71fe51659f21dcdc41ceb29d_48985be1b37c44a88cdddae860d42d3c.png


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


       ✅运用前面层序遍历的思想用队列进行层序遍历，与它不一样的地方在于这次空值也要入队列，只要队列的队头为空指针就停止操作，看后面是否都为空，由于完全二叉树的自身特性决定了它的后面如果都为空则是完全二叉树，否则不是。


😍代码：


// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
  QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front == NULL)   // 遇到空就跳出
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}


😍二叉树的链式结构所有代码汇总😍


✅BinaryTree.c


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");
  return NULL;
  }
  node->data = x;
  node->left = NULL;
  node->right = NULL;
  return node;
}
//二叉树创建
BTNode* CreatBTree(char* str, int* pi)
{
    if(str[*pi]!= '#')
    {
        //当前节点非空，则创建当前节点
        BTNode*root=(BTNode*)malloc(sizeof(BTNode));
        root->_data = str[*pi];
        //字符位置向后移动一个位置
        ++(*pi);
        //创建左子树
        root->_left=CreatBTree(str,pi);
        //字符位置向后移动一个位置
        ++(*pi);
        //创建右子树
        root->_right=CreatBTree(str,pi);
        return root;
    }
    else
        return NULL;  //如果是空节点，则返回NULL
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
  return;
  }
  BinaryTreeDestory(root->right);
  BinaryTreeDestory(root->left);
  free(root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  return(BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1);
}
// 二叉树叶子节点个数
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);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (k == 1 && root)
  {
  return 1;
  }
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
  return NULL;
  }
  if (root->data == x)
  {
  return root;
  }
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret1)
  return ret1;
  if (ret2)
  return ret2;
  return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("N ");
  return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) 
{
  if (root == NULL)
  {
  printf("N ");
  return;
  }
  BinaryTreeInOrder(root->left);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
  printf("N ");
  return;
  }
  BinaryTreePostOrder(root->left);
  BinaryTreePostOrder(root->right);
  printf("%d ", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
  QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  printf("%d ", front->data);
  if (front->left)
    QueuePush(&q, front->left);
  if (front->right)
    QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
  QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front == NULL)   // 遇到空就跳出
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 检查后面的节点有没有非空
  // 有非空，不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}


✅Queue.c


void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail\n");
  return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
  assert(pq->phead == NULL);
  pq->phead = pq->ptail = newnode;
  }
  else
  {
  pq->ptail->next = newnode;
  pq->ptail = newnode;
  }
  pq->size++;
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->phead->next == NULL)
  {
  QNode* head = pq->phead;
  free(head);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
  }
  else
  {
  QNode* head = pq->phead;
  pq->phead = pq->phead->next;
  free(head);
  pq->size--;
  }
}
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return(pq->phead->data);
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}
文章标签：
C语言
存储
关键词：
C语言二叉树
C语言结构
C语言递归
C语言链式
二叉树C语言
Yawesh_best
目录
相关文章
c的前世今生
|
4天前
|
存储 编译器 程序员
C语言程序的基本结构
C语言程序的基本结构包括：1）预处理指令，如 `#include` 和 `#define`；2）主函数 `main()`，程序从这里开始执行；3）函数声明与定义，执行特定任务的代码块；4）变量声明与初始化，用于存储数据；5）语句和表达式，构成程序基本执行单位；6）注释，解释代码功能。示例代码展示了这些组成部分的应用。
c的前世今生
22 10
小徐在进步
|
2天前
|
C语言
C语言程序设计核心详解 第四章&&第五章 选择结构程序设计&&循环结构程序设计
本章节介绍了C语言中的选择结构，包括关系表达式、逻辑表达式及其运算符的优先级，并通过示例详细解释了 `if` 语句的不同形式和 `switch` 语句的使用方法。此外，还概述了循环结构，包括 `while`、`do-while` 和 `for` 循环，并解释了 `break` 和 `continue` 控制语句的功能。最后，提供了两道例题以加深理解。
小徐在进步
20 7
小徐在进步
|
2天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
21 6
小徐在进步
|
2天前
|
C语言
C语言程序设计核心详解 第三章:顺序结构，printf(),scanf()详解
本章介绍顺序结构的基本框架及C语言的标准输入输出。程序从`main()`开始依次执行，框架包括输入、计算和输出三部分。重点讲解了`printf()`与`scanf()`函数：`printf()`用于格式化输出，支持多种占位符；`scanf()`用于格式化输入，需注意普通字符与占位符的区别。此外还介绍了`putchar()`和`getchar()`函数，分别用于输出和接收单个字符。
小徐在进步
16 5
小徐在进步
|
2天前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
10 3
小徐在进步
|
2天前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
小徐在进步
10 2
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
11 2
芯动大师
|
15天前
|
机器学习/深度学习 存储 C语言
C语言的二叉树
1.树概念及结构 1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 补充定义: 有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。 1.2 树的相关概念 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6 叶节点或终端
芯动大师
10 0
程序员大阳
|
C语言
C语言数据结构(16)--二叉树的层序遍历代码实现
本文目录 1. 背景 2. 思路 3. 代码实现
程序员大阳
156 0
C语言数据结构(16)--二叉树的层序遍历代码实现
小徐在进步
|
2天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符，每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容，提供了丰富的示例帮助理解。通过对本文的学习，读者可以全面掌握C语言中的位运算和文件处理技术。
小徐在进步
13 5