了解完全二叉树_完全二叉树

了解完全二叉树_完全二叉树文章目录满二叉树vs完全二叉树如何创建完全二叉树?C示例数组索引与树元素的关系完全二叉树应用参考文档    在本教程中,您将学习完全二叉树及其不同类型。此外,您还将找到C语言的示例。    完全二叉树是一种二叉树,其中所有级别都已完全填充,但最低级别可能从左开始填充。    完全二叉树就像满二叉树,但有两个主要区别:所有叶元素必须向左倾斜。最后一个叶子元素可能没有正确的同级,即一个完全二叉树不一定是一个满二叉树。满二叉树vs完全二叉树如何创建完全二叉树?选择列表的第一个_数据结构完全二叉树有什么用

文章目录

          • 满二叉树 vs 完全二叉树
          • 如何创建完全二叉树?
          • C示例
          • 数组索引与树元素的关系
          • 完全二叉树应用
          • 参考文档

    在本教程中,您将学习完全二叉树及其不同类型。此外,您还将找到C语言的示例。
    完全二叉树是一种二叉树,其中所有级别都已完全填充,但最低级别可能从左开始填充。
    完全二叉树就像满二叉树,但有两个主要区别:

  1. 所有叶元素必须向左倾斜。
  2. 最后一个叶子元素可能没有正确的同级,即一个完全二叉树不一定是一个满二叉树。

在这里插入图片描述

满二叉树 vs 完全二叉树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

如何创建完全二叉树?
  1. 选择列表的第一个元素作为根节点。(I级元素的数量:1)
    在这里插入图片描述
  2. 将第二个元素作为根节点的左子元素,将第三个元素作为右子元素。(II级元素的数量:2)

在这里插入图片描述

  1. 将接下来的两个元素作为第二级左节点的子元素。同样,将接下来的两个元素作为第二层右节点的子元素。(III级元素的数量:2)
  2. 不断重复,直到到达最后一个元素

在这里插入图片描述

C示例
// Checking if a binary tree is a complete binary tree in C

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

struct Node { 
   
  int key;
  struct Node *left, *right;
};

// Node creation
struct Node *newNode(char k) { 
   
  struct Node *node = (struct Node *)malloc(sizeof(struct Node));
  node->key = k;
  node->right = node->left = NULL;
  return node;
}

// Count the number of nodes
int countNumNodes(struct Node *root) { 
   
  if (root == NULL)
    return (0);
  return (1 + countNumNodes(root->left) + countNumNodes(root->right));
}

// Check if the tree is a complete binary tree
bool checkComplete(struct Node *root, int index, int numberNodes) { 
   
  // Check if the tree is complete
  if (root == NULL)
    return true;

  if (index >= numberNodes)
    return false;

  return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes));
}

int main() { 
   
  struct Node *root = NULL;
  root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);

  int node_count = countNumNodes(root);
  int index = 0;

  if (checkComplete(root, index, node_count))
    printf("The tree is a complete binary tree\n");
  else
    printf("The tree is not a complete binary tree\n");
}
数组索引与树元素的关系

    一个完全二叉树有一个有趣的属性,我们可以用它来找到任何节点的子节点和父节点。
    如果数组中任何元素的索引为 i,则索引 2i+1 中的元素将成为左子级,索引 2i+2 中的元素将成为右子级。此外,索引 i 处任何元素的父元素由 (i-1)/2 的下界给出。
    让我们测试一下,

Left child of 1 (index 0)
= element in (2*0+1) index 
= element in 1 index 
= 12


Right child of 1
= element in (2*0+2) index
= element in 2 index 
= 9

Similarly,
Left child of 12 (index 1)
= element in (2*1+1) index
= element in 3 index
= 5

Right child of 12
= element in (2*1+2) index
= element in 4 index
= 6

    我们还要确认规则适用于查找任何节点的父节点

Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1

Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

    理解数组索引到树位置的这种映射对于理解堆数据结构如何工作以及如何用于实现堆排序至关重要。

完全二叉树应用
  • 基于堆的数据结构
  • 堆排序
参考文档

[1]Parewa Labs Pvt. Ltd.Complete Binary Tree[EB/OL].https://www.programiz.com/dsa/complete-binary-tree,2020-01-01.

今天的文章了解完全二叉树_完全二叉树分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/59171.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注