【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.



目录
相关文章
|
2天前
|
存储
数据结构——二叉树
数据结构——二叉树
5 1
TU^
|
3天前
|
存储 算法
数据结构~~链式二叉树
数据结构~~链式二叉树
TU^
4 0
|
3天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
6天前
|
存储
数据结构初阶 初识二叉树
数据结构初阶 初识二叉树
7 0
|
10天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
10 0
|
11天前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
10 1
|
11天前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
数据结构学习记录——图应用实例-拯救007(问题描述、解题思路、伪代码解读、C语言算法实现)
10 0
|
3天前
数据结构——栈和队列
数据结构——栈和队列
7 1
|
6天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3
|
2天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)