满二叉树

2024年8月28日 | 阅读 7 分钟

计算机科学中的各种数据结构有助于以各种形式组织数据。树是流行的抽象数据结构，可以模拟分层树结构。树通常有一个根值和由父节点的子节点形成的子树。非线性数据结构是树。

一般树数据结构可以拥有的子节点数量没有限制。然而，二叉树的情况并非如此。本文将介绍一种特定的树数据结构——二叉树——以及二叉树的不同类型。

二叉树数据结构：究竟是什么？

二叉树是一种非线性树形数据结构，每个父节点最多有两个子节点。除了数据元素外，二叉树中的每个节点还包含左子节点和右子节点的引用。根节点是位于树结构最顶端的节点。父节点是包含其他子节点的节点。父节点的两个子节点是左子节点和右子节点。

哈希、数据压缩、网络流量路由、设置二叉堆以及构建二叉搜索树只是二叉树的一些用途。

与二叉树相关的术语和二叉树类型节点：它代表树中分支的末端。

根是树的最顶端节点。

树中每个有至少一个子节点的节点（根节点除外）称为父节点。

从根部远离时，直接来自父节点的节点称为子节点。外部节点是那些。它们是没有后代的节点。顾名思义，内部节点是至少有一个子节点的节点。树的深度：跨越树的节点和根的边的数量。从节点到最深叶子的边的数量决定了树的高度。树的高度也包括根的高度。

二叉树类型包括以下内容

满二叉树。
完全二叉树。
完美二叉树。
平衡二叉树。
退化二叉树。

二叉树有多种类型，每种类型都有其自身的特性。下面详细介绍每种二叉树类型

这里我们将详细讨论满二叉树

满二叉树

满二叉树是一种特殊的二叉树，其中每个父节点和内部节点要么有两个子节点，要么没有子节点。

它也称为“ proper binary tree”。

一种特殊的二叉树，称为满二叉树，其中每个父节点和内部节点要么有两个子节点，要么没有子节点。它也称为“ proper binary tree”。

如果二叉树 T 是一个非空树，那么如果 L 是树中的一个叶节点，I 是它的内部节点，那么 L = I + 1 将是叶节点的总数。

如果 T 有 I 个内部节点，N 是总节点数，那么总节点数将等于 N = 2I + 1

如果 T 有“N”个总节点，而“I”表示内部节点的数量，那么“I”将表示内部节点的数量 (N-1)/2

如果“T”包含“N”个总节点，“L”是叶节点的数量，那么 L = (N+1)/2 将是叶节点的数量。

如果“T”包含“L”个叶节点和“I”个内部节点，那么内部节点的数量将等于 I = L - 1

概述

令 i 表示内部节点的数量。

n = total nodes 
l = the total number of leaves
λ = number of levels

然后，

存在 (i + 1) 个叶节点。
总共有 (2i + 1) 个节点。
内部节点的数量是 (n - 1) / 2。
存在 (n + 1) / 2 个叶节点。
总共有 n 个节点 (2l - 1)。
存在数量为 (l - 1) 的内部节点。
可能存在的最多叶节点数为 (2λ - 1)。

满二叉树与完全二叉树

1. 完全二叉树的最后一个级别的节点只能有一个子节点。

满二叉树不能在每个节点上包含单个子节点。

2. 在满二叉树中，节点应从左到右填充。

满二叉树的节点可以按任何顺序填充。

3. 基于堆的数据结构通常用于完全二叉树。

满二叉树，也称为“ proper binary trees”，没有应用。

4. 近似完全二叉树是完全二叉树的另一个术语。

满二叉树通常被称为 2-tree 或 proper binary tree。

5. 满叶节点需要一个完全二叉树。

在对比这两种二叉树时，我们可以观察到以下几点：并非所有完全二叉树都是满二叉树。第一个例子证明了这一点。最底层不必从左到右填充而不留空隙，并且叶子可以出现在满二叉树的任何级别，而不仅仅是最低两个级别。这是原因。并非所有满二叉树都是完全二叉树。第二个例子是这个的示例。有一个只有一个子节点的节点，这是原因。然而，在完全二叉树中，规则最多只会由一个节点违反。

因此，从这个意义上说，满二叉树或近乎满的二叉树就是完全二叉树。当二叉树用作搜索树时，二叉树的平衡变得至关重要，因为节点的深度决定了查找相关值所需的步数。从这个角度来看，整个二叉树更受青睐，因为它更平衡。然而，对于频繁变化的值集，它可能很繁琐，因为它在添加或删除值时可能需要大量重构。因此，许多用于动态值集合中搜索的常用数据结构，如红黑树，实际上是具有附加约束的满二叉树，以确保一定程度的平衡。

C语言程序，用于创建具有 n 个节点的 L 所有可能的满二叉树的列表

struct Trees {
  int size;
  struct TreeNode* data;
};

void initialise_trees(struct Trees* trees, int number_trees) {
  trees->size = number_trees;
  trees->data = malloc(number_trees * sizeof(struct TreeNode));
}

void initialise_node(
    struct TreeNode* node,
    struct TreeNode* left,
    struct TreeNode* right) {
  node->val = 0;
  node->left = left;
  node->right = right;
}

/* Given the range [first, last) calculate the total number of FBT that can be made */
int calculate_number_trees(struct Trees* first, struct Trees* last) {
  int ret = 0;
  while (first < --last) {
    ret += (first++)->size * last->size * 2;
  }
  if (first == last) {
    ret += first->size * last->size;
  }
  return ret;
}

struct TreeNode* clone_tree(struct TreeNode* root) { 
  if (!root) {
    return NULL;
  }
    
  struct TreeNode* const ret = malloc(sizeof(struct TreeNode));
  ret->val = root->val;
  ret->left = clone_tree(root->left);
  ret->right = clone_tree(root->right);
  return ret;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct TreeNode** allPossibleFBT(int N, int* returnSize){
  if (N % 2 == 0)
  {
    *returnSize = 0;
    return NULL;
  } else if (N == 1) {
    *returnSize = 1;
    struct TreeNode** const ret = malloc(sizeof(struct TreeNode*));
    ret[0] = malloc(sizeof(struct TreeNode));
    initialise_node(ret[0], NULL, NULL);
    return ret;
  }

  /* Cache[n] will hold all the trees that can be made from n * 2 + 1 nodes */
  int number_cache = N / 2;
  struct Trees* const cache = malloc(number_cache * sizeof(struct Trees));
  struct Trees* left_branch;
  struct Trees* right_branch;
  initialise_trees(cache, 1);
  initialise_node(cache[0].data, NULL, NULL);

  /* Build up a cache of all posibilites of N - 2 nodes to build the final 
   * answer from */
  for (int root = 1; root < number_cache; ++root) {
    left_branch = &cache[0];
    right_branch = &cache[root];
    int number_trees = calculate_number_trees(left_branch, right_branch);
    initialise_trees(&cache[root], number_trees);
    
    struct TreeNode* curr = cache[root].data;
    while (cache != right_branch--) {
      for (int left = 0; left < left_branch->size; ++left) {
        for (int right = 0; right < right_branch->size; ++right) {
          initialise_node(curr++, &left_branch->data[left], &right_branch->data[right]);
        }
      }
      ++left_branch;
    }
  }
 
  /* Build the final answer by cloning the interconnected trees */
  left_branch = &cache[0];
  right_branch = &cache[number_cache];
  *returnSize = calculate_number_trees(left_branch, right_branch);
  struct TreeNode** const ret = malloc(*returnSize * sizeof(struct TreeNode*));
  struct TreeNode** curr = ret;
  
  while (cache != right_branch--) {
    for (int left = 0; left < left_branch->size; ++left) {
      for (int right = 0; right < right_branch->size; ++right) {
        *curr = malloc(sizeof(struct TreeNode));
        initialise_node(*(curr++), clone_tree(&left_branch->data[left]), clone_tree(&right_branch->data[right]));
      }
    }
    ++left_branch;
  }

  for (int i = 0; i < number_cache; ++i) {
    free(cache[i].data);
  }
  free(cache);
  
  return ret;
}

输出

n = 7 [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]

下一个主题二叉树的左视图

满二叉树

二叉树数据结构：究竟是什么？

二叉树类型包括以下内容

满二叉树

满二叉树与完全二叉树

C语言程序，用于创建具有 n 个节点的 L 所有可能的满二叉树的列表

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

满二叉树

二叉树数据结构：究竟是什么？

二叉树类型包括以下内容

满二叉树

满二叉树与完全二叉树

C语言程序，用于创建具有 n 个节点的 L 所有可能的满二叉树的列表

相关帖子

三元搜索树

使用 DSU 检测图中的循环

将二叉树展平成链表

如何在 C++ 中使用 Qdebug 打印字符串字面量和 Qstring

归并排序的递归关系

计数排序 vs 桶排序

并查集算法中的按秩合并和路径压缩

如何在单个数组中高效实现 k 个栈

形成回文所需的最少插入次数

遍历 N 元树的方法数量

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器