【数据结构】C语言实现链式二叉树(附完整运行代码)

简介: 【数据结构】C语言实现链式二叉树(附完整运行代码)

一.了解项目功能

在本次项目中我们的目标是实现一个链式二叉树:

链式二叉树使用动态内存分配空间,可以用来存储任意数量的同类型数据.

二叉树结点(BTNode)需要包含三个要素:左孩子指针域left,数据域data,右孩子指针域right.

二叉树结点(BTNode)逻辑结构图示如下:

链式二叉树程序提供的功能有:

  1. 二叉树的先序建树.
  2. 二叉树的新节点创建.
  3. 二叉树的判空
  4. 二叉树的先序遍历
  5. 二叉树的中序遍历
  6. 二叉树的后序遍历
  7. 二叉树的层序遍历
  8. 二叉树的叶子结点数
  9. 二叉树的左孩子节点数
  10. 二叉树的右孩子节点数
  11. 二叉树的结点数
  12. 二叉树的高度
  13. 查询二叉树某层的结点个数
  14. 查询某节点是否在二叉树中
  15. 查询此树是否是完全二叉树
  16. 翻转二叉树
  17. 销毁二叉树

二.项目功能演示

要编写一个链式二叉树项目,首先要明确我们想要达到的效果是什么样,下面我将用vs2022编译器来为大家演示一下链式二叉树程序运行时的样子:

C语言实现l二叉树程序功能演示


三.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍,我们已经对链式二叉树的功能有了大致的了解,虽然看似需要实现的功能很多,貌似一时间不知该如何下手,但我们可以分步分模块来分析这个项目的流程,最后再将各部分进行整合,所以大家不用担心,跟着我一步一步分析吧!


!!!注意,该部分的代码只是为了详细介绍某一部分的项目实现逻辑,故可能会删减一些与该部分不相关的代码以便大家理解,需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

为直观分析链式二叉树中的递归思路,在后续的功能实现部分,我会频繁使用下面这棵树画函数递归展开图,大家可以先熟悉一下这棵二叉树,我们马上就开始实现具体的功能:


1.实现链式二叉树程序菜单

菜单部分的逻辑比较简单,就是利用C语言printf函数打印出这个菜单界面即可。但要注意菜单的标序要和后续switch...case语句的分支相应,以免导致后续执行语句错乱的问题.基础问题就不过多赘述了,代码如下:

该部分功能实现代码如下:

//菜单二叉树
void BTMenu()
{
  printf("****************************************\n");
  printf("******请选择要进行的操作          ******\n");
  printf("******1.先序建树                  ******\n");
  printf("******2.查询树是否为空            ******\n");
  printf("******3.树的先序遍历              ******\n");
  printf("******4.树的中序遍历              ******\n");
  printf("******5.树的后序遍历              ******\n");
  printf("******6.树的层序遍历              ******\n");
  printf("******7.树的叶子节点数            ******\n");
  printf("******8.树的左孩子节点个数        ******\n");
  printf("******9.树的右孩子节点个数        ******\n");
  printf("******10.树的节点个数             ******\n");
  printf("******11.树的高度                 ******\n");
  printf("******12.查询树某层的节点个数     ******\n");
  printf("******13.查询结点是否在树中       ******\n");
  printf("******14.查询树是否是完全二叉树   ******\n");
  printf("******15.翻转此树                 ******\n");
  printf("******0.退出二叉树程序            ******\n");
  printf("****************************************\n");
  printf("请选择:>");
}

2.实现链式二叉树程序功能可循环使用

由于我们要实现链式二叉树的功能可以反复使用的逻辑,且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.

该部分功能实现代码如下:

int main()
{
  BTNode* root = NULL;
 
  int swi = 0;
  do         
  {
    BTMenu();
    scanf("%d", &swi);
    switch (swi)
    {
    case 0:
      TreeDestory(root); // 释放树内存
      printf("您已退出程序:>\n");
      break;
 
    case 1:
      printf("请输入树:>(以'#'表示空孩子)\n");
      char a[100];
      scanf("%s", a);
      int i = 0;
      root = CreatTree(a, &i);
      printf("已成功建树:>\n");
 
      break;
 
    case 2:
      if (BTEmpty(root) == true) //判断树空
        printf("当前树为空\n");
      else
        printf("当前树不为空\n");
 
      break;
 
    case 3:
      printf("先序遍历此树: ");    
      PreOrder(root);
      printf("\n");
 
      break;
 
    case 4:
      printf("中序遍历此树: ");
      InOrder(root);
      printf("\n");
 
      break;
 
    case 5:
      printf("后序遍历此树: ");
      PostOrder(root);
      printf("\n");
 
      break;
 
    case 6:
      printf("层序遍历此树: ");
      LevelOrder(root);
      printf("\n");
 
      break;
 
    case 7:
      printf("此树的叶子节点数有: %d\n", BinaryTreeLeafSize(root));
 
      break;
 
    case 8:
      printf("此树的左孩子节点数有: %d\n", BinaryTreeLLeafSize(root));
 
      break;
 
    case 9:
      printf("此树的右孩子节点数有: %d\n", BinaryTreeRLeafSize(root));
 
      break;
 
    case 10:
      printf("此树的节点数有:%d\n", TreeSize(root));
 
      break;
 
    case 11:
      printf("此树的高度为:%d\n", TreeHeight(root));
 
      break;
 
    case 12:
      printf("请输入你要查询的层数:>");
      int k = 0;
      scanf("%d", &k);
 
      printf("此树第%d层的节点数有:%d\n",k,TreeKLevel(root,k));
 
      break;
 
    case 13:
      printf("请输入你要查询的结点:>");
      setbuf(stdin, NULL);//之前键盘缓冲区有污染,该函数作用是清空键盘缓冲区
      BTDataType x = 0;
      scanf("%c", &x);
      //二叉树查找值为x的结点
      if (BinaryTreeFind(root, x) != NULL)
      {
        printf("结点%c在树中:>\n",x);
      }
      else
      {
        printf("结点%c不在树中:<\n",x);
      }
      
      break;
 
    case 14:
      if (TreeComplete(root))
      {
        printf("该树是完全二叉树:>\n");
      }
      else
      {
        printf("该树不是完全二叉树:<\n");
      }
 
      break;
      
    case 15:
      root = InvertTree(root);
      printf("翻转成功:>\n");
      printf("前序遍历结果为:");
      PreOrder(root);
      printf("\n");
 
      break;
 
    default:
      printf("输入错误,请重新输入\n");
 
      break;
    }
  } while (swi);
  return 0;
}

3.实现链式二叉树的新结点创建

创建链式二叉树结点的结构体应该包括:存储数据的数据域data,以及存储左孩子结点地址的指针域left,存储右孩子结点地址的指针域right.

图示如下:

因此我们创建BTNode结构体类型时应由一个数据成员类型及两个指向该结构体的结构体的指针组成.

了解了链式二叉树的结点构造后,创建新结点就和之前单链表中对新结点的处理方法相同了,

具体思路如下:

  1. 使用malloc动态开辟结点空间
  2. 对结点结构体内容进行初始化
  3. 处理完毕,返回该新结点

该部分代码实现如下:

//获取二叉树结点
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;
}

4.实现链式二叉树的先序建树

先序建树部分,我们采用的思路是:

  1. 先在主函数接收先序排列的建树字符串
  2. 再将其传入建树函数递归建树

我们按照最开始画的那颗树先前序遍历树:

我们给函数输入我们前序遍历的树得到的字符串,此时就可以画出前序建树时的函数递归展开图:

该部分实现代码如下:

//前序建树
BTNode* CreatTree(char* a, int* pi)
{
  
  if (a[(*pi)] == '#')  //不是#不++!
  {
    (*pi)++;
    return NULL;
  }
 
  BTNode* root = BuyNode(a[(*pi)]);
 
  (*pi)++;
  root->left = CreatTree(a, pi);
  root->right = CreatTree(a, pi);
 
  return root;
}
 
//主函数部分调用建树逻辑
case 1:
      printf("请输入树:>(以'#'表示空孩子)\n");
    char a[100];
    scanf("%s", a);
    int i = 0;
    root = CreatTree(a, &i);
    printf("已成功建树:>\n");
 
    break;

5.实现链式二叉树的判空

链式二叉树的判空逻辑较为简单,只需要返回树根节点的状态即可.

该部分实现代码如下:

//判断树空
bool BTEmpty(BTNode* root)
{
    return (!root);
}

6.实现链式二叉树的先序遍历

先序遍历的思路是:

  1. 先访问根节点
  2. 再递归访问左子树
  3. 再递归访问右子树

我们画一下先序遍历的函数递归展开图:

该部分代码实现如下:

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

7.实现链式二叉树的中序遍历

中序遍历的思路是:

  1. 先递归访问左子树
  2. 再访问根节点
  3. 最后递归访问右子树

该部分递归展开图于先序遍历类似,故不作展示,代码实现如下:

//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
 
  InOrder(root->left);
  printf("%c ", root->data);
  InOrder(root->right);
}

8.实现链式二叉树的后序遍历

后序遍历的思路是:

  1. 先递归访问左子树
  2. 再递归访问右子树
  3. 最后访问根节点

该部分递归展开图于先序遍历类似,故不作展示,代码实现如下:

//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
 
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%c ", root->data);
}

9.实现链式二叉树的层序遍历

实现层序遍历的思路为(借助队列实现):

  1. 将根节点入队
  2. 如果队首结点不为空,将队首结点不为空的孩子入队
  3. 访问队首元素并将其出队

注:因为在之前的文章中我们已经实现过链队列程序了,所以在树部分我们不涉及讲解链队列的实现,而是直接使用.

层序遍历算法演示如下:

该部分实现代码如下(链队列的实现在文末的两个Queue文件中):

//层序遍历(借助队列)
void LevelOrder(BTNode* root)
{
  Que q;
  QueueInit(&q);
 
  if (root)
    QueuePush(&q, root);
 
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%c ", front->data);
    if (front->left != NULL)
    {
      QueuePush(&q, front->left);
    }
    if (front->right != NULL)
    {
      QueuePush(&q, front->right);
    }
  }
 
  QueueDestroy(&q);
}

10.实现链式二叉树的叶子节点数计算

叶子结点的计算上我们采用递归分治的思想,即

根结点的叶子节点数=左子树的叶子节点数+右子树的叶子节点数.

当然,叶子结点的判断条件根存在且左右子树都为空.

函数的递归展开图如下:

该部分代码实现如下:

//叶子节点数
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);//返回每颗子树的左右叶子节点数
}

11.实现链式二叉树左孩子节点数计算

左孩子结点的计算上我们同样采用递归分治的思想,即

根结点的左孩子节点数=左子树的左孩子节点数+右子树的左孩子节点数.

当然,左孩子结点的判断条件根存在且左子树不为空.

该函数的递归展开和叶子节点计算类似,这里就不赘述了,代码实现如下:

//左孩子节点数
int BinaryTreeLLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left != NULL)
    return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right)+1;
  else
    return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right);
}

12.实现链式二叉树右孩子节点数计算

右孩子结点的计算上我们同样采用递归分治的思想,即

根结点的右孩子节点数=左子树的右孩子节点数+右子树的右孩子节点数.

当然,右孩子结点的判断条件根结点存在且右子树不为空.

该函数的递归展开和叶子节点计算类似,这里就不赘述了,代码实现如下:

//右孩子节点数
int BinaryTreeRLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->right != NULL)
    return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right)+1;
  else
    return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right);
}

13.实现链式二叉树节点数计算

树的结点的计算上我们同样采用递归分治的思想,即

根结点的节点数=左子树的节点数+右子树的节点数.

当然,结点的判断标条件根结点存在.

该函数的递归展开和叶子节点计算类似,这里就不赘述了,代码实现如下:

//树的结点个数
int TreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  else
    return TreeSize(root->left) + TreeSize(root->right) + 1;//返回左子树个数和右子树个数加上自己
 
  //return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
  //从这条语句里体会分治的思想
}

14.实现链式二叉树高度计算

二叉树的高度计算上我们同样采用递归分治的思想,即

二叉树的高度左子树和右子树高的那个高度加上根结点自己的高度,即

二叉树的高度=左子树的高度>右子树的高度?左子树高度+1:右子树高度+1.

函数的递归展开图如下:

该部分代码实现如下:

//树高
int TreeHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
 
  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);
 
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1 ;
  //返回左子树和右子树高的那个并加上自己那份
}

15.实现链式二叉树查询某层结点个数

某层结点的计算我们同样采用递归分治的思想,即

根结点的K层节点数=左子树的K层节点数+右子树的K层节点数.

当然,K层结点的判断条件在K层且结点存在.

该函数的递归展开和高度计算类似,这里就不赘述了,代码实现如下:

//层结点个数
int TreeKLevel(BTNode* root, int k)
{
  assert(k > 0);
 
  if (root == NULL)    //思路是,对每个根结点分别求左子树第k层的结点+右子树第k层的结点
    return 0;
 
  //如果在k层,且不为空,则就是k层的有效结点
  if (k == 1)
    return 1;
 
  return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

16.实现链式二叉树查询某节点是否存在

查询某节点是否存在我们同样采用递归分治的思想,即

树中是否存在该结点取决于左子树是否存在该节点右子树是否存在该节点,

树中是否存在该结点 = 左子树是否存在该节点 || 右子树是否存在该节点

我们采取后序遍历的思想,从叶子节点逐级上传查找结果,如果没找到,就逐级传上空结点,如果找到了,就将该节点逐级传到根结点.

只要左右子树其中有一个存在这个结点,那树中就是存在该结点的.

该部分代码实现如下:

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
 
  if (root->data == x)
    return root;
  //找到了就逐级传回
 
  BTNode* lret = BinaryTreeFind(root->left, x);
  if (lret)
  {
    return lret;
  }
 
  BTNode* rret = BinaryTreeFind(root->right, x);
  if (rret)
  {
    return rret;
  }
 
  return NULL;
}

17.实现链式二叉树判断是否为完全二叉树

我们判断二叉树是否为完全二叉树的思路是利用完全二叉树的性质:

完全二叉树不为满二叉树,空节点必定连续出现在最后一层的靠右部分.

如下图所示,虚线所表示的是空结点:

因此我们利用层序遍历的思路,将所有结点的空孩子也入队,当完全二叉树遍历到第一个空结点时后面一定全为空结点,如果后面还有非空结点,那么这颗树就不是完全二叉树.

该部分代码实现如下(实现链队列部分在文末的Queue文件中):

//判断一棵树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
  //完全二叉树按层序走,非空结点一定是连续的(出过的结点的空子树也被无形中带入队了,不用担心结点在后面没有入队)
  Que q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
 
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    
    if (front==NULL)
    {
      break;
    }
    else
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
  }
 
  //判断是不是完全二叉树(即出队过程中剩余元素有没有非空的结点)
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
 
    //front不为空,就为真,就返回假
    if (front)
    {
      QueueDestroy(&q);
      return false;
    }
  }
 
  QueueDestroy(&q);
  return true;
}

18.实现翻转链式二叉树

翻转二叉树我们同样采用递归分治的思想,即

翻转二叉树=翻转左子树+翻转右子树.

我们采用后序遍历的思想,最后再翻转根节点的左右子树

该部分代码实现如下:

//翻转二叉树
BTNode* InvertTree(BTNode* root)
{
  if (root == NULL)
    return NULL;
  BTNode* tmp = InvertTree(root->right);
  root->right = InvertTree(root->left);
  root->left = tmp;
  return root;
}

19.实现链式二叉树的销毁

二叉树的销毁我们采用后序递归遍历的思想,即:先销毁左右子树,再销毁根节点

该部分代码实现如下:

//销毁树
void TreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
  //递归后序销毁
  TreeDestory(root->left);
  TreeDestory(root->right);
  free(root);
}

四.项目完整代码

我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:

BTree.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include"Queue.h"
 
typedef char 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* CreatTree(char* a, int* pi)
{
  
  if (a[(*pi)] == '#')  //不是#不++!
  {
    (*pi)++;
    return NULL;
  }
 
  BTNode* root = BuyNode(a[(*pi)]);
 
  (*pi)++;
  root->left = CreatTree(a, pi);
  root->right = CreatTree(a, pi);
 
  return root;
}
 
 
//前序遍历
void PreOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
 
  printf("%c ", root->data);
  PreOrder(root->left);
  PreOrder(root->right);
}
 
 
//中序遍历
void InOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
 
  InOrder(root->left);
  printf("%c ", root->data);
  InOrder(root->right);
}
 
 
//后序遍历
void PostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return;
  }
 
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%c ", root->data);
}
 
 
//树的结点个数
int TreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  else
    return TreeSize(root->left) + TreeSize(root->right) + 1;//返回左子树个数和右子树个数加上自己
 
  //return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
  //从这条语句里体会分治的思想
}
 
//树高
int TreeHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
 
  int leftHeight = TreeHeight(root->left);
  int rightHeight = TreeHeight(root->right);
 
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1 ;
  //返回左子树和右子树高的那个并加上自己那份
}
 
 
//层结点个数
int TreeKLevel(BTNode* root, int k)
{
  assert(k > 0);
 
  if (root == NULL)    //思路是,对每个根结点分别求左子树第k层的结点+右子树第k层的结点
    return 0;
 
  //如果在k层,且不为空,则就是k层的有效结点
  if (k == 1)
    return 1;
 
  return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}
 
 
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
 
  if (root->data == x)
    return root;
  //找到了就逐级传回
 
  BTNode* lret = BinaryTreeFind(root->left, x);
  if (lret)
  {
    return lret;
  }
 
  BTNode* rret = BinaryTreeFind(root->right, x);
  if (rret)
  {
    return rret;
  }
 
  return NULL;
}
 
 
//层序遍历(借助队列)
void LevelOrder(BTNode* root)
{
  Que q;
  QueueInit(&q);
 
  if (root)
    QueuePush(&q, root);
 
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%c ", front->data);
    if (front->left != NULL)
    {
      QueuePush(&q, front->left);
    }
    if (front->right != NULL)
    {
      QueuePush(&q, front->right);
    }
  }
 
  QueueDestroy(&q);
}
 
//判断一棵树是否是完全二叉树
bool TreeComplete(BTNode* root)
{
  //完全二叉树按层序走,非空结点一定是连续的(出过的结点的空子树也被无形中带入队了,不用担心结点在后面没有入队)
  Que q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
 
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    
    if (front==NULL)
    {
      break;
    }
    else
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
  }
 
  //判断是不是完全二叉树(即出队过程中剩余元素有没有非空的结点)
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
 
    //front不为空,就为真,就返回假
    if (front)
    {
      QueueDestroy(&q);
      return false;
    }
  }
 
  QueueDestroy(&q);
  return true;
}
 
 
//销毁树
void TreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
  //递归后序销毁
  TreeDestory(root->left);
  TreeDestory(root->right);
  free(root);
}
 
 
//叶子节点数
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);//返回每颗子树的左右叶子节点数
}
 
//左孩子节点数
int BinaryTreeLLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left != NULL)
    return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right)+1;
  else
    return BinaryTreeLLeafSize(root->left) + BinaryTreeLLeafSize(root->right);
}
 
//右孩子节点数
int BinaryTreeRLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->right != NULL)
    return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right)+1;
  else
    return BinaryTreeRLeafSize(root->left) + BinaryTreeRLeafSize(root->right);
}
 
 
//判断树空
bool BTEmpty(BTNode* root)
{
  return (!root);
}
 
 
//翻转二叉树
BTNode* InvertTree(BTNode* root)
{
  if (root == NULL)
    return NULL;
  BTNode* tmp = InvertTree(root->right);
  root->right = InvertTree(root->left);
  root->left = tmp;
  return root;
}
 
 
//菜单二叉树
void BTMenu()
{
  printf("****************************************\n");
  printf("******请选择要进行的操作          ******\n");
  printf("******1.先序建树                  ******\n");
  printf("******2.查询树是否为空            ******\n");
  printf("******3.树的先序遍历              ******\n");
  printf("******4.树的中序遍历              ******\n");
  printf("******5.树的后序遍历              ******\n");
  printf("******6.树的层序遍历              ******\n");
  printf("******7.树的叶子节点数            ******\n");
  printf("******8.树的左孩子节点个数        ******\n");
  printf("******9.树的右孩子节点个数        ******\n");
  printf("******10.树的节点个数             ******\n");
  printf("******11.树的高度                 ******\n");
  printf("******12.查询树某层的节点个数     ******\n");
  printf("******13.查询结点是否在树中       ******\n");
  printf("******14.查询树是否是完全二叉树   ******\n");
  printf("******15.翻转此树                 ******\n");
  printf("******0.退出二叉树程序            ******\n");
  printf("****************************************\n");
  printf("请选择:>");
}
 
 
int main()
{
  BTNode* root = NULL;
 
  int swi = 0;
  do         
  {
    BTMenu();
    scanf("%d", &swi);
    switch (swi)
    {
    case 0:
      TreeDestory(root); // 释放树内存
      printf("您已退出程序:>\n");
      break;
 
    case 1:
      printf("请输入树:>(以'#'表示空孩子)\n");
      char a[100];
      scanf("%s", a);
      int i = 0;
      root = CreatTree(a, &i);
      printf("已成功建树:>\n");
 
      break;
 
    case 2:
      if (BTEmpty(root) == true) //判断树空
        printf("当前树为空\n");
      else
        printf("当前树不为空\n");
 
      break;
 
    case 3:
      printf("先序遍历此树: ");    
      PreOrder(root);
      printf("\n");
 
      break;
 
    case 4:
      printf("中序遍历此树: ");
      InOrder(root);
      printf("\n");
 
      break;
 
    case 5:
      printf("后序遍历此树: ");
      PostOrder(root);
      printf("\n");
 
      break;
 
    case 6:
      printf("层序遍历此树: ");
      LevelOrder(root);
      printf("\n");
 
      break;
 
    case 7:
      printf("此树的叶子节点数有: %d\n", BinaryTreeLeafSize(root));
 
      break;
 
    case 8:
      printf("此树的左孩子节点数有: %d\n", BinaryTreeLLeafSize(root));
 
      break;
 
    case 9:
      printf("此树的右孩子节点数有: %d\n", BinaryTreeRLeafSize(root));
 
      break;
 
    case 10:
      printf("此树的节点数有:%d\n", TreeSize(root));
 
      break;
 
    case 11:
      printf("此树的高度为:%d\n", TreeHeight(root));
 
      break;
 
    case 12:
      printf("请输入你要查询的层数:>");
      int k = 0;
      scanf("%d", &k);
 
      printf("此树第%d层的节点数有:%d\n",k,TreeKLevel(root,k));
 
      break;
 
    case 13:
      printf("请输入你要查询的结点:>");
      setbuf(stdin, NULL);//之前键盘缓冲区有污染,该函数作用是清空键盘缓冲区
      BTDataType x = 0;
      scanf("%c", &x);
      //二叉树查找值为x的结点
      if (BinaryTreeFind(root, x) != NULL)
      {
        printf("结点%c在树中:>\n",x);
      }
      else
      {
        printf("结点%c不在树中:<\n",x);
      }
      
      break;
 
    case 14:
      if (TreeComplete(root))
      {
        printf("该树是完全二叉树:>\n");
      }
      else
      {
        printf("该树不是完全二叉树:<\n");
      }
 
      break;
      
    case 15:
      root = InvertTree(root);
      printf("翻转成功:>\n");
      printf("前序遍历结果为:");
      PreOrder(root);
      printf("\n");
 
      break;
 
    default:
      printf("输入错误,请重新输入\n");
 
      break;
    }
  } while (swi);
  return 0;
}

Queue.c 文件

#include"Queue.h"
 
void QueueInit(Que* pq)
{
  assert(pq);
 
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}
void QueueDestroy(Que* pq)
{
  assert(pq);
 
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
 
}
 
void QueuePush(Que* pq, QDatatype x) //入队是尾插
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
 
  if (pq->head == NULL)//头插
  {
    assert(pq->tail == NULL);//head为空,tail不为空就出事了,队头为空但是队尾不为空
    
    pq->head = pq->tail = newnode;
    
  }
  else//尾插
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
 
  pq->size++;
 
}
 
 
void QueuePop(Que* pq)//出队是头删
{
  assert(pq);
  assert(!QueueEmpty(pq));//assert为假会终止程序
 
  QNode* cur = pq;
 
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
 
  pq->size--;
 
}
 
int QueueSize(Que* pq)
{
  assert(pq);
 
  return pq->size;
 
}
 
bool QueueEmpty(Que* pq)//判空!为空返回真!
{
  assert(pq);
 
  return pq->size==0;
}
 
QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
 
}
QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->tail->data;
 
}
 
void QMenu()
{
  printf("**********************************\n");
  printf("******请选择要进行的操作    ******\n");
  printf("******1.链队列入队          ******\n");
  printf("******2.链队列出队          ******\n");
  printf("******3.取队首元素          ******\n");
  printf("******4.取队尾元素          ******\n");
  printf("******5.队列判空            ******\n");
  printf("******6.查询当前队列长      ******\n");
  printf("******7.清空队列            ******\n");
  printf("******0.退出链队列程序      ******\n");
  printf("**********************************\n");
  printf("请选择:>");
 
}

Queue.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
typedef struct BinaryTreeNode* QDatatype;
 
typedef struct QueueNode//一个是结点结构
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
 
 
typedef struct Queue//一个是队列整体结构
{
  QNode* head;
  QNode* tail;
  int size ;
}Que;
 
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
 
void QueuePush(Que* pq,QDatatype x);
void QueuePop(Que* pq);
 
int QueueSize(Que* pq);
 
bool QueueEmpty(Que* pq);
 
QDatatype QueueFront(Que* pq);
QDatatype QueueBack(Que* pq);
 
void QMenu();

结语

希望这篇链式二叉树的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!



相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
67 16
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
107 8
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
62 4
|
1月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
65 3
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0
|
2月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
37 3
|
8天前
|
存储 缓存 算法
【C语言】内存管理函数详细讲解
在C语言编程中,内存管理是至关重要的。动态内存分配函数允许程序在运行时请求和释放内存,这对于处理不确定大小的数据结构至关重要。以下是C语言内存管理函数的详细讲解,包括每个函数的功能、标准格式、示例代码、代码解释及其输出。
33 6
|
25天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明: 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数,即头文件中存在或已经定义过; 如果使用库函数,一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数,而且该函数与使用它的函数在同一个文件中,一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前,在函数的外部已做了函数声明,则在各个主调函数中不必多所调用的函数在做声明
31 6
|
2月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
44 10