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

简介: 二叉树的链式结构 - 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;
}

目录
相关文章
|
2月前
|
网络协议 编译器 Linux
【C语言】结构体内存对齐:热门面试话题
【C语言】结构体内存对齐:热门面试话题
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
26天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
87 8
|
2月前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
66 7
|
2月前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
34 2
|
2月前
|
C语言
链式顺序表实现(C语言描述)
本文介绍了如何在C语言中实现链式顺序表,包括数据结构的定义、节点的创建、数据的插入和删除以及链表的打印和销毁。
41 2
|
2月前
|
编译器 C语言 Python
C语言结构
C语言结构
17 0
|
2月前
|
C语言
c语言回顾-函数递归(下)
c语言回顾-函数递归(下)
40 0
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现,帮助读者理解和掌握二叉树的基本操作与应用。