【数据结构】二叉树（下）-阿里云开发者社区

【数据结构】二叉树（下）

2023-04-25 63

版权

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

简介： 【数据结构】二叉树（下）

二叉树的链式结构

链式二叉树的增删查改是没有意义的，建立在二叉树基础上的搜索二叉树才具备增删查改的意义。但是链式二叉树是基础，就像修房子得先打地基一样。

二叉树的遍历

首先确定一个概念，二叉树分为空树和非空树，只要是非空树就有根节点、根节点的左子树和根节点的右子树。二叉树的定义是递归式的。

二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作依次。访问节点所做的操作依赖于具体的应用问题，遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

二叉树一共有四种遍历方式，前序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）和层序遍历。

前序遍历（先根遍历）

访问根节点的操作发生在遍历其左右子树之前。在遍历时，会不断向下遍历知道遇到空树才停止。

void PrevOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("NULL ");
    return;
  }
  printf("%d ", root->data);
  PrevOrder(root->left);
  PrevOrder(root->right);
}

栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->深蓝色->粉色->金色->紫色->青色。

中序遍历（中根遍历）

访问根节点的操作放生在遍历其左右子树之间。

void InOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("NULL ");
    return;
  }
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}

栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。

后序遍历（后根遍历）

访问根节点的操作发生在遍历其左右子树之后。

void PostOrder(BTNode* root)
{
  if (NULL == root)
  {
    printf("NULL ");
    return;
  }
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->data);
}

层序遍历

从第一层开始，每层从左到右，一层一层的走。四种遍历中，只有层序遍历是非递归的，它采用的是队列来实现的。

void LevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  // 先将根节点存入队列
  if (root)
    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);
  }
  printf("\n");
  QueueDestroy(&q);
}

二叉树的构建

二叉树的构建根据三种递归的遍历方式进行构建，可以进行前序、中序、后序构建，我这里使用的是前序构建。

BTNode* CreatBinaryTree(BTDataType* a, int* pi)
{
  if (-1 == a[*pi])
  {
    (*pi)++;
    return NULL;
  }
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (NULL == root)
  {
    perror("malloc fail");
    exit(-1);
  }
  root->data = a[(*pi)++];
  root->left = CreatBinaryTree(a, pi);
  root->right = CreatBinaryTree(a, pi);
  return root;
}

二叉树的节点数

int TreeSize(BTNode* root)
{
  if (NULL == root)
  {
    return 0;
  }
  return TreeSize(root->left) + TreeSize(root->right) + 1;
}

栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色，最后返回的值是6。

二叉树的叶子数

int TreeLeafSize(BTNode* root)
{
  if (NULL == root)
  {
    return 0;
  }
  if (NULL == root->left && NULL == root->right)
  {
    return 1;
  }
  return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为3。

二叉树的高度

int TreeHeight(BTNode* root)
{
  if (NULL == root)
  {
    return 0;
  }
  int left = TreeHeight(root->left);
  int right = TreeHeight(root->right);
  return  (left > right ? left : right) + 1;
}

二叉树K层节点数

int TreeKLevelSize(BTNode* root, int k)
{
  if (NULL == root)
  {
    return 0;
  }
  if (1 == k)
  {
    return 1;
  }
  return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

查找值为X的节点

BTNode* TreeFind(BTNode* root, BTDataType x)
{
  if (NULL == root)
    return NULL;
  if (x == root->data)
    return root;
  BTNode* ret1 = TreeFind(root->left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = TreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}

栈帧空间的创建销毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示销毁。创建销毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，最后结果为数字5节点的地址

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

bool TreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  // 若队列为空，则不执行
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    // 判断front是否为空，为空则跳出循环
    if (!front)
    {
      break;
    }
    else
    {
      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;
}

二叉树的销毁

// 二叉树销毁
void TreeDestory(BTNode* root)
{
  if (NULL == root)
  {
    return;
  }
  TreeDestory(root->left);
  TreeDestory(root->right);
  free(root);
}