AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构（初阶）—— 二叉树② ---链式结构(2)

2022-11-24 70
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构（初阶）—— 二叉树② ---链式结构(2)

10.二叉树查找值为x的节点 

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    //如果树为空，则找不到
  if (root == NULL)
  {
    return NULL;
  }
    //根节点与找的值相等
  if (root->data == x)
  {
    return root;
  }
    //遍历左子树去找
  BTNode* leftret = BinaryTreeFind(root->left, x);
    //左子树找完都没有，加个判断，让其返回去右子树找
  if (leftret)
  {
    return leftret;
  }
    //遍历右子树去找
  BTNode* rightret = BinaryTreeFind(root->right, x);
    //右子树找完都没有
  if (rightret)
  {
    return rightret;
  }
    //到这里就找不到了
  return NULL;
}

11.二叉树层序遍历

层序遍历：从上至下，从左至右；和队列的特点一样，先进先出；

思路：先入二叉树的根节点，然后Pop出去，再入根节点的左右孩子，每次Pop一个节点，其孩子入队列；

1ecd1b2606ed46e9956a89f231c9802c.png

这里我们用到了队列，队列和二叉树如何联系起来呢？

//Queue.h
struct BinaryTreeNode;//前置声明
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
/***************************************************************/
//test.c
typedef char BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;//结点
  struct BinaryTreeNode* left;//左子树
  struct BinaryTreeNode* right;//右子树
}BTNode;

原来使用队列的时候我们是让其存储的整形数据，我们这里将其设计为存储二叉树节点的指针；

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%c ", front->data);
    //孩子带进队列
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
  }
  printf("\n");
  QueueDestroy(&q);
}

12.判断是否为完全二叉树

1ecd1b2606ed46e9956a89f231c9802c.png

//判断一棵二叉树是不是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  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);
    }
  }
  //遇到空以后，检查队列中剩下的节点
  //1.剩下的全是空，则是完全二叉树
  //2.剩下的是非空，则不是完全二叉树
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

13.二叉树的销毁 

// 二叉树销毁(用后序的方式来释放)
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
}

三、源代码

Queue.h 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
struct BinaryTreeNode;//前置声明
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//取队头的数据
QDataType QueueFront(Queue* pq);
//取队尾的数据
QDataType QueueBack(Queue* pq);
//计算有多少个数据
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c 

#include "Queue.h"
//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur != NULL)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  //此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
}
//取队头的数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//计算有多少个数据
int QueueSize(Queue* pq)
{
  assert(pq);
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
    ++n;
    cur = cur->next;
  }
  return n;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

test.c

#include "Queue.h"
typedef char BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;//结点
  struct BinaryTreeNode* left;//左子树
  struct BinaryTreeNode* right;//右子树
}BTNode;
//二叉树的初始化
BTNode* BuyNode(BTDataType x);
//创建二叉树
BTNode* CreatBinaryTree();
//二叉树的前序遍历
void PreOrder(BTNode* root);
//二叉树的中序遍历
void InOrder(BTNode* root);
//二叉树的后序遍历
void PostOrder(BTNode* root);
//二叉树的结点个数
int BinaryTreeSize1(BTNode* root);
void BinaryTreeSize2(BTNode* root, int* pn);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root);
//判断是都为完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
/*************************************************************************************/
//二叉树的初始化
BTNode* BuyNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  newnode->data = x;
  newnode->left = newnode->right = NULL;
  return newnode;
}
//创建二叉树
BTNode* CreatBinaryTree()
{
  BTNode* nodeA = BuyNode('A');
  BTNode* nodeB = BuyNode('B');
  BTNode* nodeC = BuyNode('C');
  BTNode* nodeD = BuyNode('D');
  BTNode* nodeE = BuyNode('E');
  BTNode* nodeF = BuyNode('F');
  nodeA->left = nodeB;
  nodeA->right = nodeC;
  nodeB->left = nodeD;
  nodeC->left = nodeE;
  nodeC->right = nodeF;
  return nodeA;
}
//二叉树的前序遍历
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 BinaryTreeSize1(BTNode* root)
{
  return root == NULL ? 0 : 
    BinaryTreeSize1(root->left) 
    + BinaryTreeSize1(root->right) + 1;
}
//方法二
void BinaryTreeSize2(BTNode* root, int* pn)
{
  if (root == NULL)
  {
    return;
  }
  ++(*pn);
  BinaryTreeSize2(root->left, pn);
  BinaryTreeSize2(root->right, pn);
}
/*******************************************************/
// 二叉树叶子节点个数
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 >= 1);
  if (root == NULL)
  {
    return 0;
  }
  if (k == 1)
  {
    return 1;
  }
  //root不等于空，k也不等于1，说明root这棵树的第k节点在字树里面
  //转换成求左右子树的第k-1的节点数量；
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int leftDepth = BinaryTreeDepth(root->left);
  int rightDepth = BinaryTreeDepth(root->right);
  return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  //如果树为空，则找不到
  if (root == NULL)
  {
    return NULL;
  }
  //根节点与找的值相等
  if (root->data == x)
  {
    return root;
  }
  //遍历左子树去找
  BTNode* leftret = BinaryTreeFind(root->left, x);
  //左子树找完都没有，加个判断，让其返回去右子树找
  if (leftret)
  {
    return leftret;
  }
  //遍历右子树去找
  BTNode* rightret = BinaryTreeFind(root->right, x);
  //右子树找完都没有
  if (rightret)
  {
    return rightret;
  }
  //到这里就找不到了
  return NULL;
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%c ", front->data);
    //孩子带进队列
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
  }
  printf("\n");
  QueueDestroy(&q);
}
//判断一棵二叉树是不是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  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);
    }
  }
  //遇到空以后，检查队列中剩下的节点
  //1.剩下的全是空，则是完全二叉树
  //2.剩下的是非空，则不是完全二叉树
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  printf("前序遍历：");
  PreOrder(root);
  printf("\n\n");
  printf("中序遍历：");
  InOrder(root);
  printf("\n\n");
  printf("后序遍历：");
  PostOrder(root);
  printf("\n\n");
  printf("二叉树节点个数,方法1：");
  printf("%d\n\n", BinaryTreeSize1(root));
  printf("二叉树节点个数,方法2：");
  int n = 0;
  BinaryTreeSize2(root, &n);
  printf("%d\n\n", n);
  printf("二叉树叶子节点个数：");
  printf("%d\n\n", BinaryTreeLeafSize(root));
  printf("二叉树第3层节点个数：");
  int k = 3;
  printf("%d\n\n", BinaryTreeLevelKSize(root, k));
  printf("二叉树深度:");
  printf("%d\n\n", BinaryTreeDepth(root));
  printf("二叉树C结点前序遍历:");
  BTNode* cur = BinaryTreeFind(root, 'C');
  PreOrder(cur);
  printf("\n\n");
  printf("层序遍历：");
  BinaryTreeLevelOrder(root);
  printf("\n");
  printf("是否为完全二叉树0/1：");
  printf("%d\n", BinaryTreeComplete(root));
  BinaryTreeDestory(root);
  root = NULL;
  return 0;
}

运行效果

1ecd1b2606ed46e9956a89f231c9802c.png

二叉树链式结构的实现主要是递归思想，加上队列的混合使用，不熟悉的小伙伴可以去看这里


数据结构（初阶）——栈和队列②https://blog.csdn.net/sjsjnsjnn/article/details/124086038?spm=1001.2014.3001.5501


想要熟练掌握，需要小伙伴亲自画图分析理解，并自行编写代码实现，查找错误点，仔细分析


文章标签：
存储
关键词：
数据结构二叉树
数据结构结构
数据结构二叉树结构
数据结构二叉树链式结构
数据结构链式
霄沫凡M
目录
相关文章
三三是该溜子
|
8天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
22 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
XIAZHI
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
97 4
ephemerals__
|
2月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
104 16
ephemerals__
|
2月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
143 8
java冯坚持
|
3月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
32 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
3月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
39 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
阿客不是客
|
3月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
34 0
阿客不是客
|
3月前
探索顺序结构：栈的实现方式
探索顺序结构：栈的实现方式
阿客不是客
36 0
java冯坚持
|
3月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
35 0
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
236 9

热门文章

最新文章

  • 1
    Python编程数据结构的深入理解
  • 2
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 3
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 4
    Python 中的数据结构与其他编程语言数据结构的区别
  • 5
    C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
  • 6
    Python 中的数据结构和算法优化策略
  • 7
    Python 中数据结构和算法的关系
  • 8
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 9
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 10
    Pandas数据结构：Series与DataFrame
  • 1
    【Python进阶（七）】——Series数据结构
    186
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1335
  • 3
    深入浅出数据结构之布隆过滤器
    75
  • 4
    数据结构/C++：位图 & 布隆过滤器
    49
  • 5
    数据结构/C++：哈希表
    84
  • 6
    数据结构/C++：红黑树
    47
  • 7
    数据结构/C++：AVL树
    49
  • 8
    栈的基本应用
    64
  • 9
    栈与队列理解
    49
  • 10
    数据结构/C++：二叉搜索树
    54

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • Python语言基础 - 列表、元组、字典、集合

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月