【初阶数据结构篇】实现链式结构二叉树（二叉链）下篇

2024-08-19 23

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 要改变root指针的指向，将本来指向根节点的root指针改为空，所以传二级指针（一级指针也可以，只不过在调用完记得把root置为空）。

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