【初阶数据结构篇】实现链式结构二叉树（二叉链）上篇：https://developer.aliyun.com/article/1590120?spm=a2c6h.13148508.setting.15.605e4f0eOvemXj

实现链式结构二叉树（二叉链）下篇

前言

接上一篇

实现链式结构二叉树（二叉链）上篇

二叉树实现方法

二叉树查找值为x的结点

• 分为左右子树查找，依次递推即可
• 结束条件为空：说明在这一路径上没有找到
• 结束条件找到了返回结点指针即可

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }

  BTNode* leftFind = BinaryTreeFind(root->left, x);
  if (leftFind)
  {
    return leftFind;
  }
  BTNode* rightFind = BinaryTreeFind(root->right, x);
  if (rightFind)
  {
    return rightFind;
  }
  return NULL;
}

二叉树的销毁

• 注意这里我们要改变root指针的指向，将本来指向根节点的root指针改为空，所以传二级指针（一级指针也可以，只不过在调用完记得把root置为空）
• 先销毁左右子树，最后销毁根节点
• 当为空时，不用销毁直接返回

void BinaryTreeDestory(BTNode** root)
{
  if (*root == NULL)
  {
    return;
  }
  BinaryTreeDestory(&((*root)->left));
  BinaryTreeDestory(&((*root)->right));

  free(*root);
  *root = NULL;
}

二叉树的层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层序遍历

由于递归会沿着一边路径一直递归下去，所以显然不能使用递归！

• 实现层序遍历需要额外借助数据结构：队列

• 创建并初始化队列，注意将队列结点存储的数据类型更改
• 这里我们插入的是指向结点的指针，而不是结点的值，否则找不到结点的左右孩子，所以队列结点存储的数据类型为struct BTNode*
• 首先将指向根节点的指针入队列，保存后并打印结点的值
• 根节点出队列，保证每一次取到的队列的头都是新的
• 如果根节点左右孩子不为空就将其入队列，为空则无必要，不需要打印NULL
• 重复上述操作直到队列为空

//层序遍历
//借助数据结构---队列
void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    //取队头，打印
    BTNode* front = QueueFront(&q);
    printf("%d ", front->data);
    QueuePop(&q);
    //队头节点的左右孩子入队列
    if (front->left)
      QueuePush(&q, front->left);
    if (front->right)
      QueuePush(&q, front->right);
  }
  //队列为空
  QueueDestroy(&q);
}

判断是否为完全二叉树

• 同样使用层序遍历
• 左右结点不管是否为空，都入队列
• 第一个循环用来取二叉树第一个NULL结点前的所有数据

如果是完全二叉树，跳出此循环后剩下的都是NULL结点

如果是非完全二叉树，跳出此循环后还有非空结点

• 于是第二个循环用来判断此时队列里是否有非空的指针

如果直到队列为空跳出循环说明全是空指针，返回true

反之返回false

//判断二叉树是否为完全二叉树
//---队列
bool BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  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 != NULL)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

二叉树性质选择题

• 在二叉树基础概念这篇博客中讲到了二叉树叶子结点个数==度为2结点个数+1
• 本题选B

• 由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有a一1个。

• 再根据完全二叉树的定义，度为1的结点有0个或1个

• 假设度1结点为0个，a+0+a一1=2n，得2a=2n一1，由于结点个数必须为整数，假设不成立；

• 当度为1的结点为1个时，a+1+a一1=2n，得a=n，即叶子结点个数为n。

• 本题选A

• 由2⁹-1<531<2¹⁰-1
• 说明第九层填满，第十层没有填满
• 本题选B

• 与第二题同理
• 由二叉树的定义可知，树中必定存在度为0的结点和度为2的结点，设度为0结点有a个，根据度为0的结点(即叶子结点)总比度为2的结点多一个，得度为2的结点有a一1个。
• 再根据完全二叉树的定义，度为1的结点有0个或1个
• 假设度1结点为0个，a+0+a一1=767，得2a=768，即叶子结点个数为384
• 当度为1的结点为1个时，a+1+a一1=767，不为整数，舍去。
• 本题选B

二叉树遍历选择题

• 根据层序遍历
• 从上到下，从左到右可以直接画出二叉树结构

• 根据前序遍历规则即可
• 本题选A

• 认真审题！先序遍历确定根节点
• 本题选A

• 后序遍历最后一个一定是根节点
• 中序遍历中得到根节点左右子树
• 确定一个划去一个
• 在左右子树又可以根据后序遍历确定根节点
• 再看中序遍历得到左右子树
• 重复上述操作即可画出二叉树

本题选D

• 思路和第三题一样

本题选A