【数据结构】C语言实现链式二叉树(附完整运行代码)-阿里云开发者社区

一.了解项目功能

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

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

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

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

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

二叉树的先序建树.

二叉树的新节点创建.

二叉树的判空

二叉树的先序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的层序遍历

二叉树的叶子结点数

二叉树的左孩子节点数

二叉树的右孩子节点数

二叉树的结点数

二叉树的高度

查询二叉树某层的结点个数

查询某节点是否在二叉树中

查询此树是否是完全二叉树

翻转二叉树

销毁二叉树

二.项目功能演示

要编写一个链式二叉树项目，首先要明确我们想要达到的效果是什么样，下面我将用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结构体类型时应由一个数据成员类型及两个指向该结构体的结构体的指针组成.

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

具体思路如下:

使用malloc动态开辟结点空间

对结点结构体内容进行初始化

处理完毕,返回该新结点

该部分代码实现如下:

//获取二叉树结点
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.实现链式二叉树的先序建树

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

先在主函数接收先序排列的建树字符串

再将其传入建树函数递归建树

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

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

该部分实现代码如下:

//前序建树
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.实现链式二叉树的先序遍历

先序遍历的思路是:

先访问根节点

再递归访问左子树

再递归访问右子树

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

该部分代码实现如下:

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

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

中序遍历的思路是:

先递归访问左子树

再访问根节点

最后递归访问右子树

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

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

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

后序遍历的思路是:

先递归访问左子树

再递归访问右子树

最后访问根节点

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

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

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

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

将根节点入队

如果队首结点不为空,将队首结点不为空的孩子入队

访问队首元素并将其出队

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

层序遍历算法演示如下:

该部分实现代码如下(链队列的实现在文末的两个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();

结语

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

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

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

一.了解项目功能

二.项目功能演示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18.实现翻转链式二叉树

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

四.项目完整代码

BTree.c文件

Queue.c 文件

Queue.h文件

结语

热门文章

最新文章

相关课程

相关电子书