【数据结构】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();

结语

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

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



相关文章
|
7天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
71 9
|
6天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
45 16
|
6天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
35 8
|
9天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
35 4
|
9天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
25 0
|
1天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
4天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
6天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
27 4
|
29天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
26 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
10天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

热门文章

最新文章