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

万字超全详解：二叉树的基本操作（C语言版本）（下）

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

三、二叉树的基本操作（链表版本）

1.链表节点结构体

//使用链表的 形式来实现二叉树的基本操作
#define MaxSize 20
typedef struct TreeNode {
  int data;//数据域
  struct TreeNode* lchild;
  struct TreeNode* rchild;//指向左右孩子结点
}BiNode,*BiTree;

2.先序创建二叉树

//先序创建二叉树
BiTree CreateTree() {
  int data;
  scanf("%d", &data);  //这样每一次输入都会进行传值操作  直到输入的数值小于0然后开始右结点  使用递归的方法进行创建二叉树
  BiTree root;
  if (data <= 0) {
    return NULL;
  }
  else {
    root = (BiTree)malloc(sizeof(BiNode));
    root->data = data;
    root->lchild = CreateTree();
    root->rchild = CreateTree();//先序传参  制造先序二叉树
  }
  return root;
}

1）中序后序创建二叉树

  中序、后序创建二叉树的代码实现就是更改先序创建二叉树中的  root->data = data;  位置

更改递归的先后就可以，到这个地方大家应该就明白如何操作了（我看了一圈的csdn也没有多少人去说明这个事情，这是我在群里问了其他人的回复：更换递归和root->data = data；的位置）

3.先序遍历二叉树

1）递归操作

所有的二叉树的遍历，不管先序、中序、后序，都可以通过递归的形式是实现。这个是最简单，最好理解的方式。在不强调不能使用递归的前提下，建议优先使用递归。

先序、中序、后序，只是跟上文那个什么序进行遍历创建二叉树一个道理，更改递归的位置即可~

//先序遍历
//1.递归操作  实现先序遍历
void PreTreeTraverse(BiTree root) {
  if (root) {
    //只要根节点不是空
    printf("%d", root->data);
    PreTreeTraverse(root->lchild);
    PreTreeTraverse(root->rchild);
  }
}

2）非递归操作

非递归操作中，先序、中序、后序操作都有不同，所以这个比较难理解和记忆，但是有一个共同点是，都需要使用辅助栈的形式（定义一个类似于栈的 BiTree数组）！！！

这个写法大概思路是创建辅助栈，然后创建新节点，然后判断是否根节点为NULL（NULL的话不需要 遍历直接返回），设置栈数组的变量top  提前赋值为-1（任意都可以  按照个人习惯来），然后是top++（top现在为0）将root赋值给stack[0]  然后进入while循环（判断依据是栈中有没有元素 top>-1），因为是先序所以直接输出root节点数据，然后使用 if 语句判断是否有左右孩子（先判断右孩子的原因是，使得最后一个放进去的是左孩子节点，这样出栈的时候，是左孩子先出）

//2.非递归操作
//引入辅助栈
void PreOrderTraverseNonRec(BiTree root) {
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  if (root != NULL) {
    //表示非空树
    top++;
    stack[top] = root;//将root放在stack数组中
    //栈不空的时候循环
    while (top > -1) {    //这个写法牛逼的地方在于 首先是先输出根结点的数值然后出栈top--然后判断是否有右孩子，放进栈里面 然后
      //出栈并访问结点       //这个时候如果有孩子的话 top>-1 还能进入while循环 然后输出左孩子（有的话）然后出栈 在判断这个孩子有没有左右孩子，一旦是没有了，你们前面压栈的右孩子就可以输出了
                           //输出右孩子之后，出栈 然后进行判断右孩子是由有左右孩子   模拟递归操纵s
      p = stack[top];
      top--;
      printf("%d", p->data);
      //右孩子入栈
      if (p->rchild != NULL) {
        top++;
        stack[top] = p->rchild;
      }
      //左孩子入栈
      if (p->lchild != NULL) {
        top++;
        stack[top] = p->rchild;
      }
    }
  }
}

4.中序遍历二叉树

1）递归操作

这个时候就能发现，有一定的规律在递归操作上

//有了先序遍历操作就可以写出来中序和后序遍历操作
//2.中序遍历
//1）递归操作
void InTreeTreaver(BiTree root) {
  if (root) {
    //判断根节点是否为空
    InTreeTreaver(root->lchild);
    printf("%d", root->data);
    InTreeTreaver(root->rchild);
  }
}

2）非递归操作

//2)非递归
void InTreeTreaver2(BiTree root) {
  //创建临时栈
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  if (root) {
    p = root;
    while (top > -1 || p != NULL) {
      //扫描所有的左孩子进栈   其实在左孩子进栈的过程中就只剩下右孩子
      while (p != NULL) {
        top++;
        stack[top] = p;
        p = p->lchild;
      }
      //扫描完成之后开始出栈
      if (top > -1) {
        p = stack[top];
        printf("%d", p->data);
        top--;
        //扫描右孩子
        p = p->rchild;
      }
    }
  }
}

5.后序遍历二叉树

1）递归操作

//3.后序遍历
void PostTreeTraverse(BiTree root) {
  if (root) {
    PostTreeTraverse(root->lchild);
    PostTreeTraverse(root->rchild);
    printf("%d", root->data);
  }
}

2）非递归操作

//2)非递归
 //后序遍历二叉树:非递归实现 
void PostOrderTraverseNonRec(BiTree root) {
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  int sign;
  if (root != NULL) {
    do {
      //root节点入栈
      while (root != NULL) {
        top++;
        stack[top] = root;
        root = root->lchild;
      }
      //p指向栈顶前一个已访问节点
      p = NULL;
      //置root为已访问
      sign = 1;
      while (top != -1 && sign) {
        //取出栈顶节点
        root = stack[top];
        //右孩子不存在或右孩子已访问则访问root
        if (root->rchild == p) {
          printf("%d ", root->data);
          top--;
          //p指向被访问的节点
          p = root;
        }
        else {
          //root指向右孩子节点
          root = root->rchild;
          //置未访问标记
          sign = 0;
        }
      }
    } while (top != -1);
  }
}

6.求第k层节点的个数

/遇到叶子节点  正好  因为你想要的是第k层 所以就k-1递归 然后等你到第k层的时候也就是k=1的时候 自然就返回1 了

你输入的第k层，在递归k-1次之后到达第k层，自然就返回1了 ，然后就得到对应第k层的数值了

int LevelNodeNum(BiTree root,int k) {
  //进行判断是否为空 或者k数值不对
  if (root == NULL || k < 1) {
    return 0;
  }
  if (k == 1) {
    return 1;//遇到叶子节点  正好  因为你想要的是第k层 所以就k-1递归 然后等你到第k层的时候也就是k=1的时候 自然就返回1 了
  }
  else {
    return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild,k - 1);
  }
}

7.求二叉树的深度

//求二叉树的最大深度
//使用递归的方式来实现
int maxTreeDeapth(BiTree root) {
  if (root) {
    int maxLeft = maxTreeDeapth(root->lchild);
    int maxRight = maxTreeDeapth(root->rchild);
    if (maxLeft > maxRight) {
      return maxLeft + 1;
    }
    else {
      return maxRight + 1;
    }
  }
  return 0;
}

8.二叉树的叶子节点的个数

//求二叉树叶子节点个数
int LeafNodeNum(BiTree root) {
  //这一步是为了判断是否为空树  空树自然叶子节点为0
  if (root == NULL) {
    return 0;
  }
  if (root->lchild == NULL && root->rchild == NULL) {
    return 1;//叶子节点的特点  没有孩子  所以用递归  可以得到叶子节点的个数
  }
  else {
    return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
  }
}

9.二叉树的总节点的个数

求二叉树的叶子节点的个数和求总结点的个数，不同的是在使用递归的时候，如果是为了求叶子节点只需要在这个节点没有左右孩子的时候 return 1  在递归的时候不会+1

但是在求总结点个数的时候，使用递归的时候都会+1，这个+1表示的是加上这个节点了，其他方面没有不同

//二叉树的总节点个数
//使用递归的方法实现
int CountNode(BiTree root) {
  if (root) {
    if (root->lchild == NULL && root->rchild == NULL) {
      return 1;//遇到叶子节点返回1
    }
    else {
      return CountNode(root->lchild) + CountNode(root->rchild)+1;
      //每一次正常运行都会加一并表示节点，直到遇到叶子节点返回数值1
    }
  }
}

10.递归查找指定元素x的节点

先进行左孩子递归一直找，找不到的时候就会使用右孩子递归了，如果再找不到就返回NULL，表示没有这个元素为x的节点

//查找元素为x的节点
//采用递归的方法
BiTree SearchNode(BiTree root, int x) {
  if (root) {//这个是判断是否为NULL空树   第二是为了判断左右孩子是否为NULL
    if (root->data == x) {
      return root;//如果数据对了就返回相应节点
    }
    else {
      BiTree p;//创建新节点位置
      p = SearchNode(root->lchild, x);//使用遍历 先左孩子进行比较 
      if (!p) {//左孩子比较完成之后在进行右孩子递归比较  只要有有孩子就可以一直比较
        p = SearchNode(root->rchild, x);
      }
      return p;
    }
  }
  return NULL;
}

11.全部代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//使用链表的 形式来实现二叉树的基本操作
#define MaxSize 20
typedef struct TreeNode {
  int data;//数据域
  struct TreeNode* lchild;
  struct TreeNode* rchild;//指向左右孩子结点
}BiNode,*BiTree;
//我们规定，节点值必须为大于0的数值 ，如果是0表示奇数继续往下创建子节点的操作
//二叉树的操作通常使用递归的方法，二叉树的操作可以分为两类，一类是需要改变二叉树的结构，比如二叉树的创建，结点的删除等等
//这类操作，传入的二叉树的 结点参数为二叉树指针的地址，这种参数的传入，便于更改二叉树结构体的指针
//我们使用递归的方法创建左右子树
//第一种创建二叉树，使用一级指针
//先序创建二叉树
BiTree CreateTree() {
  int data;
  scanf("%d", &data);  //这样每一次输入都会进行传值操作  直到输入的数值小于0然后开始右结点  使用递归的方法进行创建二叉树
  BiTree root;
  if (data <= 0) {
    return NULL;
  }
  else {
    root = (BiTree)malloc(sizeof(BiNode));
    root->data = data;
    root->lchild = CreateTree();
    root->rchild = CreateTree();//先序传参  制造先序二叉树
  }
  return root;
}
//先序遍历
//1.递归操作  实现先序遍历
void PreTreeTraverse(BiTree root) {
  if (root) {
    //只要根节点不是空
    printf("%d", root->data);
    PreTreeTraverse(root->lchild);
    PreTreeTraverse(root->rchild);
  }
}
//2.非递归操作
//引入辅助栈
void PreOrderTraverseNonRec(BiTree root) {
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  if (root != NULL) {
    //表示非空树
    top++;
    stack[top] = root;//将root放在stack数组中
    //栈不空的时候循环
    while (top > -1) {    //这个写法牛逼的地方在于 首先是先输出根结点的数值然后出栈top--然后判断是否有右孩子，放进栈里面 然后
      //出栈并访问结点       //这个时候如果有孩子的话 top>-1 还能进入while循环 然后输出左孩子（有的话）然后出栈 在判断这个孩子有没有左右孩子，一旦是没有了，你们前面压栈的右孩子就可以输出了
                           //输出右孩子之后，出栈 然后进行判断右孩子是由有左右孩子   模拟递归操纵s
      p = stack[top];
      top--;
      printf("%d", p->data);
      //右孩子入栈
      if (p->rchild != NULL) {
        top++;
        stack[top] = p->rchild;
      }
      //左孩子入栈
      if (p->lchild != NULL) {
        top++;
        stack[top] = p->rchild;
      }
    }
  }
}
//有了先序遍历操作就可以写出来中序和后序遍历操作
//2.中序遍历
//1）递归操作
void InTreeTreaver(BiTree root) {
  if (root) {
    //判断根节点是否为空
    InTreeTreaver(root->lchild);
    printf("%d", root->data);
    InTreeTreaver(root->rchild);
  }
}
//2)非递归
void InTreeTreaver2(BiTree root) {
  //创建临时栈
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  if (root) {
    p = root;
    while (top > -1 || p != NULL) {
      //扫描所有的左孩子进栈   其实在左孩子进栈的过程中就只剩下右孩子
      while (p != NULL) {
        top++;
        stack[top] = p;
        p = p->lchild;
      }
      //扫描完成之后开始出栈
      if (top > -1) {
        p = stack[top];
        printf("%d", p->data);
        top--;
        //扫描右孩子
        p = p->rchild;
      }
    }
  }
}
//3.后序遍历
void PostTreeTraverse(BiTree root) {
  if (root) {
    PostTreeTraverse(root->lchild);
    PostTreeTraverse(root->rchild);
    printf("%d", root->data);
  }
}
//2)非递归
 //后序遍历二叉树:非递归实现 
void PostOrderTraverseNonRec(BiTree root) {
  BiTree stack[MaxSize];
  BiTree p;
  int top = -1;
  int sign;
  if (root != NULL) {
    do {
      //root节点入栈
      while (root != NULL) {
        top++;
        stack[top] = root;
        root = root->lchild;
      }
      //p指向栈顶前一个已访问节点
      p = NULL;
      //置root为已访问
      sign = 1;
      while (top != -1 && sign) {
        //取出栈顶节点
        root = stack[top];
        //右孩子不存在或右孩子已访问则访问root
        if (root->rchild == p) {
          printf("%d ", root->data);
          top--;
          //p指向被访问的节点
          p = root;
        }
        else {
          //root指向右孩子节点
          root = root->rchild;
          //置未访问标记
          sign = 0;
        }
      }
    } while (top != -1);
  }
}
//求二叉树的最大深度
//使用递归的方式来实现
int maxTreeDeapth(BiTree root) {
  if (root) {
    int maxLeft = maxTreeDeapth(root->lchild);
    int maxRight = maxTreeDeapth(root->rchild);
    if (maxLeft > maxRight) {
      return maxLeft + 1;
    }
    else {
      return maxRight + 1;
    }
  }
  return 0;
}
//求二叉树叶子节点个数
int LeafNodeNum(BiTree root) {
  //这一步是为了判断是否为空树  空树自然叶子节点为0
  if (root == NULL) {
    return 0;
  }
  if (root->lchild == NULL && root->rchild == NULL) {
    return 1;//叶子节点的特点  没有孩子  所以用递归  可以得到叶子节点的个数
  }
  else {
    return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
  }
}
/// <summary>
/// 求k层节点个数
/// </summary>
/// <returns></returns>
int LevelNodeNum(BiTree root,int k) {
  //进行判断是否为空 或者k数值不对
  if (root == NULL || k < 1) {
    return 0;
  }
  if (k == 1) {
    return 1;//遇到叶子节点  正好  因为你想要的是第k层 所以就k-1递归 然后等你到第k层的时候也就是k=1的时候 自然就返回1 了
  }
  else {
    return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild,k - 1);
  }
}
//二叉树的总节点个数
//使用递归的方法实现
int CountNode(BiTree root) {
  if (root) {
    if (root->lchild == NULL && root->rchild == NULL) {
      return 1;//遇到叶子节点返回1
    }
    else {
      return CountNode(root->lchild) + CountNode(root->rchild)+1;
      //每一次正常运行都会加一并表示节点，直到遇到叶子节点返回数值1
    }
  }
}
//查找元素为x的节点
//采用递归的方法
BiTree SearchNode(BiTree root, int x) {
  if (root) {//这个是判断是否为NULL空树   第二是为了判断左右孩子是否为NULL
    if (root->data == x) {
      return root;//如果数据对了就返回相应节点
    }
    else {
      BiTree p;//创建新节点位置
      p = SearchNode(root->lchild, x);//使用遍历 先左孩子进行比较 
      if (!p) {//左孩子比较完成之后在进行右孩子递归比较  只要有有孩子就可以一直比较
        p = SearchNode(root->rchild, x);
      }
      return p;
    }
  }
  return NULL;
}
int main()
{
  BiTree root = NULL;
  root = CreateTree();
  PreTreeTraverse(root);
  printf("\n");
  int len = maxTreeDeapth(root);
  printf("%d",len);
  printf("\n");
  int num=LevelNodeNum(root, 2);
  printf("%d\n", num);
  printf("%d\n", CountNode(root));
  return 0;
}

总结

     1.  对于二叉树的学习，我已经使用过了顺序表的形式和链表的形式，感觉上，第一次在二叉树上发现了递归的神奇用处，之前使用的递归的时候都是一些很小的问题的解决，这一次在二叉树的遍历上面，无论是如何实现的二叉树，在进行先序、中序、后序等遍历的时候，使用递归的方法是最为简单，也是最好理解的。

     2.虽然在学过Java之后觉得C为基础的数据结构真的好麻烦，Java会有相应的框架，一时畏难心理就有了，但是在最近的学习来看，数据结构是一门很有意思的课程，在这个地方，感受到数据结构的魅力，希望大家不要畏难，感受敲完代码理解代码的那一刻的快乐，大家加油！！！

文章标签：
Java
C语言
关键词：
C语言二叉树
二叉树C语言
C语言版本
C语言基本操作
二叉树基本操作C语言版本
容颜寄语-26413
目录
相关文章
hahaha无
|
4月前
|
存储 C语言
c语言——二叉树
二叉树的概念在这里就不进行过多的赘述，那么主要说一下我认为重要的部分，第一点就是二叉树里面部分概念的理解：就比如说，你对于如何构建二叉树，掌握的十分深刻，但刷题的时候对于一些题目所给的概念不清楚，导致看不明白题目，这课不好，二叉树的概念如下图所示,其实都很简单，主要是当给他的名字时，你明不明白。还有对于满二叉树与完全二叉树。
hahaha无
73 0
ephemerals__
|
11月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
712 8
小徐在进步
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手，详细介绍了先序、中序和后序遍历方法，并探讨了如何构建二叉树及线索二叉树的概念。接着，文章讲解了树和森林的存储结构，特别是如何将树与森林转换为二叉树形式，以便利用二叉树的遍历方法。最后，讨论了树和森林的遍历算法，包括先根、后根和层次遍历。通过这些内容，读者可以全面了解二叉树及其相关概念。
小徐在进步
255 6
小徐在进步
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构，其中节点的度为其分支数量，树的度为树中最大节点度数。二叉树是一种特殊的树，其节点最多有两个子节点，具有多种性质，如叶子节点数与度为2的节点数之间的关系。此外，还介绍了二叉树的不同形态，包括满二叉树、完全二叉树、二叉排序树和平衡二叉树，并探讨了二叉树的顺序存储和链式存储结构。
小徐在进步
207 3
小徐在进步
|
存储 算法 C语言
C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现
这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
小徐在进步
310 2
小徐在进步
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
321 2
梦笔生花伟
|
机器学习/深度学习 存储 C语言
C语言的二叉树
1.树概念及结构 1.1树的概念 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 补充定义: 有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。 1.2 树的相关概念 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6 叶节点或终端
梦笔生花伟
80 0
osswangxining
|
24天前
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数，通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配，并建议检查返回值以确保读取成功，提升程序健壮性。
osswangxining
611 0
蓝易云
|
3月前
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用，可以有效管理字符串和内存操作，它们是C语言编程中不可或缺的工具。
蓝易云
251 15
RossyYan
|
9月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定（头歌实践教学平台习题）【合集】
本内容介绍了编写一个判断素数的子函数的任务，涵盖循环控制与跳转语句、算术运算符（%）、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码，测试说明提供了输入输出示例，最后给出通关代码和测试结果。 任务核心：编写判断素数的子函数并在主函数中调用，涉及循环结构和条件判断。
RossyYan
390 23