【C语言/数据结构】二叉树(层序遍历|判断完全二叉树|性质)

简介: 【C语言/数据结构】二叉树(层序遍历|判断完全二叉树|性质)

层序遍历

层序遍历需要用到队列的思想。


这里先给出要用的队列相关函数

//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
//插入
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
  perror("malloc fail");
  return;
  }
  newnode->val = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
  pq->ptail = pq->phead = newnode;
  }
  else
  {
  pq->ptail->next = newnode;
  pq->ptail = newnode;
  }
  pq->size++;
}
//删除
void QueuePop(Queue* pq) 
{
  assert(pq);
  assert(pq->phead);
  QNode* del = pq->phead;
  pq->phead = pq->phead->next;
  free(del);
  del = NULL;
  if (pq->phead == NULL)
  {
  pq->ptail = NULL; 
  }
  pq->size--;
}
//取队头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->phead->val;
}
 //判断是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->phead == NULL;
}
//节点个数
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}


队列的声明


typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{ 
  QDataType val;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;

注意:第一行typedef的是节点的指针。因为队列里存放二叉树的节点的指针时,我们才可以通过节点的指针找到下一个节点。


层序遍历函数实现

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  QueuePush(&q, root);
  int levelSize = 1;
  while (!QueueEmpty(&q))
  {
  // 一层一层出
  while (levelSize--)
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    printf("%d ", front->data);
    if (front->left)
    QueuePush(&q, front->left);
    if (front->right)
    QueuePush(&q, front->right);
  }
  printf("\n");
  levelSize = QueueSize(&q);
  }
  printf("\n");
  QueueDestroy(&q);
}


分析:将根结点push进队列,然后取队头,打印,删队头。再把该节点的两个子节点push进队列。如此循环,直到队列为空。Pop删除时,我们free掉的是队列的Node,不是树的Node,二者不会相互影响。取队头时,返回值是队列里节点的值,这个值就是树的节点的指针。levelSize控制一层一层出,打印出来的效果是一层一层的。某一层打印结束时,levelSize更新为队列里的节点个数,如此循环,就能一层一层打印。




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


函数实现


// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  QueuePush(&q, root);
  int levelSize = 1;
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q); 
  if (front == NULL)
    break;
  QueuePush(&q, front->left);
  QueuePush(&q, front->right);
  }
  // 前面遇到空以后,后面还有非空就不是完全二叉树
  while (!QueueEmpty(&q))
  {
  BTNode* front = QueueFront(&q);
  QueuePop(&q);
  if (front)
  {
    QueueDestroy(&q);
    return false;
  }
  }
  QueueDestroy(&q);
  return true;
}

分析:前面的过程与层序相似,只不过在遇到空时,就结束循环。接着来到第二个while循环,当遇到非空时,if语句执行,就会直接返回false。如果后面都是空,if语句就不执行,最后就会返回true。


二叉树性质


这里分析第3个,其余在前几篇博客已说明。(n0表示度为0,n2表示度为2)


分析:第3个的意思是,度为0的节点的个数是度为2的节点个数+1。


当只有一个节点时,n0为1个,n2为0个。增加一个节点,减少一个n0,增加一个n0,所以n0不变。再如下图所示,再增加一个节点,n2就变为1个,n0也会增加1个,但是n1就会减少。因此有关系:n0=n2+1.



目录
相关文章
|
25天前
|
机器学习/深度学习 算法 C语言
【趣学C语言和数据结构100例】11-15
本文介绍了五个C语言编程问题及其实现,包括矩阵对角线元素之和、有序数组插入、数组逆序、杨辉三角输出和魔方阵生成。每个问题不仅涉及基本的数组操作,还涵盖了算法设计的核心思想,如循环、条件判断和递归。通过解决这些问题,读者可以加深对C语言和数据结构的理解,提升编程技能。这些问题的解决过程展示了如何有效处理数组和矩阵,以及如何利用算法优化程序性能,为实际应用提供了宝贵的实践经验。
49 4
【趣学C语言和数据结构100例】11-15
|
17天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
28 1
|
25天前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
41 4
|
25天前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
38 4
|
25天前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
35 4
|
25天前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
40 4
|
25天前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
34 4
|
25天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现,涵盖链表与数组操作,如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例,帮助读者深入理解数据结构与算法设计的核心思想,提升编程技能。
32 4
|
25天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】51-55
本文介绍了五个关于链表操作的C语言实现案例,包括删除单链表中的重复元素、从两个有序链表中查找公共元素、判断一个链表是否为另一链表的连续子序列、判断循环双链表是否对称及合并两个循环单链表。每个案例都详细解析了算法思路与实现方法,涵盖了链表操作的多种场景,旨在帮助读者深入理解链表数据结构的应用,提升算法设计与编程能力。
36 4
|
25天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】16-20
本文精选了五个C语言编程问题,涵盖数组操作、字符串处理等基础领域。包括查找二维数组中的鞍点、折半查找法、统计文章中字符数量、电文解密及字符串连接。每个问题都附有详细的代码实现与分析,旨在帮助读者理解算法逻辑,提升编程技巧。通过这些实践,不仅能锻炼编程能力,还能加深对数据结构和算法的理解,为未来的学习和工作打下坚实基础。
57 4

热门文章

最新文章