1. 数据结构与算法/

·561 字·3 分钟· loading
demo007x
作者
demo007x

完全二叉树
#

我们知道树是一种非线性数据结构。它对儿童数量没有限制。二叉树有一个限制,因为树的任何节点最多有两个子节点:左子节点和右子节点。

什么是完全二叉树?
#

完全二叉树是一种特殊类型的二叉树,其中树的所有级别都被完全填充,除了最低级别的节点从尽可能左侧填充之外。

完全二叉树的一些术语:
#

  • 根: 没有边来自父节点的节点。示例-节点A
  • 子节点: 具有某些传入边的节点称为子节点。示例 – 节点 B、F 分别是 A 和 C 的子节点。
  • 兄弟节点:具有相同父节点的节点是兄弟节点。示例 - D、E 是兄弟姐妹,因为他们有相同的父母 B。
  • 节点的度数: 特定父节点的子节点数量。示例 - A 的次数为 2,C 的次数为 1。D 的次数为 0。
  • 内部/外部节点: 叶节点是外部节点,非叶节点是内部节点。
  • 级别: 计算到达目标节点的路径中的节点数。示例 - 由于节点 A 和 E 形成路径,因此节点 D 的级别为 2。
  • 高度: 到达目标节点的边数,根的高度为 0。示例 – 节点 E 的高度为 2,因为它有两条距根的边。

我们知道是一种非线性数据结构。它对叶子节点数量没有限制。二叉树有一个限制,因为树的任何节点最多有两个子节点:左子节点和右子节点.

什么是完全二叉树?
#

完全二叉树是一种特殊类型的二叉树,其中树的所有级别都被完全填充,除了最低级别的节点尽可能左侧填充之外。

完全二叉树

完全二叉树的一些术语:
#

  • :没有边来自父节点的节点。示例-节点A
  • 子节点: 具有某些传入边的节点称为子节点。示例 – 节点 B、F 分别是 A 和 C 的子节点。
  • 兄弟节点:具有相同父节点的节点是兄弟节点。示例 - D、E 是兄弟姐妹,因为他们有相同的父母 B。
  • 节点的度数: 特定父节点的子节点数量。示例 - A 的次数为 2,C 的次数为 1。D 的次数为 0。
  • 内部/外部节点: 叶节点是外部节点,非叶节点是内部节点。
  • 级别: 计算到达目标节点的路径中的节点数。示例 - 由于节点 A 和 E 形成路径,因此节点 D 的级别为 2。
  • 高度:到达目标节点的边数,根的高度为 0。示例 – 节点 E 的高度为 2,因为它有两条距根的边。

完全二叉树的性质:
#

  • 完全二叉树被称为真二叉树,其中所有叶子都具有相同的深度。
  • 在完全二叉树中,深度d处的节点数为 2 d
  • 在具有n 个节点的完全二叉树中,树的高度为log(n+1)
  • 除最后一个级别外所有级别均已满。

完美二叉树与完全二叉树:
#

具有最大节点数、高度为“h”的二叉树是完美二叉树。 对于给定高度h,节点的最大数量为 2h+1-1

高度为 h 的完全二叉树是高度为h-1的完美二叉树,并且在最后一层中元素按从左到右的顺序存储。

示例1:
#

二叉树

给定二叉树的高度为 2,该树中的最大节点数为 n = 2 h+1 -1 = 22+1 -1 = 23 -1 = 7。 因此我们可以断定它是一个完美的二叉树。 现在对于一个完整的二叉树,它的高度达到h-1,即;1、最后一层元素按照从左到右的顺序存储。因此它也是一棵完全二叉树。这是存储在数组中时元素的表示形式

img

元素逐级存储在数组中。在数组中,所有元素都是连续存储的。

示例2:
#

一棵二叉树

给定二叉树的高度为 2,节点的最大数量为 2h+1 – 1 = 22+1 – 1 = 2 3 – 1 = 7。 但树中的节点数是6。因此它不是完美的二叉树。 现在对于一个完整的二叉树,它的高度达到 h-1,即;1 和最后一级元素按从左到右的顺序存储。因此这是一个完全二叉树。将元素存储在数组中,它会像;

元素逐级存储在数组中

示例3:
#

一棵二叉树

二叉树的高度为2,最多可以有7个节点,但只有5个节点,因此它不是完美的二叉树。 在完全二叉树的情况下,我们看到在最后一层元素不是从左到右顺序填充的。所以它不是一个完全二叉树

元素逐级存储在数组中

数组中的元素不连续。

完整二叉树与完全二叉树:
#

对于满二叉树,每个节点有 2 个子节点或 0 个子节点。

示例1:
#

一棵二叉树

在给定的二叉树中,没有度数为 1 的节点,每个节点有 2 个或 0 个子节点,因此它是一个满二叉树

对于完全二叉树,元素是逐层存储的,而不是从最后一层的最左边开始。因此这不是一个完整的二叉树。数组表示形式为:

元素逐级存储在数组中

示例2:
#

二叉树

在给定的二叉树中,没有度为 1 的节点。每个节点的度为 2 或 0。因此,它是满二叉树

对于完全二叉树,元素是逐层存储的,并从最后一层的最左边开始填充。因此这是一个完全二叉树。下面是树的数组表示:

元素逐级存储在数组中

示例3:

一棵二叉树

在给定的二叉树中,节点 B 的度数为 1,这违反了满二叉树的属性,因此它不是满二叉树

对于完全二叉树,元素是逐层存储的,并从最后一层的最左边开始填充。因此这是一个完全二叉树。二叉树的数组表示为:

元素逐级存储在数组中

示例4:

一棵二叉树

在给定的二叉树中,节点 C 的度数为 1,这违反了满二叉树的属性,因此它不是满二叉树

对于完全二叉树,元素是逐层存储的,并从最后一层的最左边开始填充。这里节点 E 违反了条件。因此这不是一个完整的二叉树

完全二叉树的创建:
#

我们知道,完全二叉树是一棵树,其中除了最后一层(例如l)之外,所有其他层都有(2l)个节点,并且节点从左到右排列。 可以使用数组来表示。如果父级是索引i则左子级位于2i+1,右子级位于2i+2

完全二叉树及其数组表示

算法:

为了创建完全二叉树,我们需要一个 队列数据结构来跟踪插入的节点。

**步骤1:**当树为空时,用新节点初始化根。

**步骤2:**如果树不为空,则获取前面的元素

  • 如果前面的元素没有左子节点,则将左子节点设置为新节点
  • 如果右子节点不存在,则将右子节点设置为新节点

**步骤 3:**如果该节点有两个子节点,则将其从队列中弹出

**步骤4:**将新数据入队。

考虑下面的数组:

  1. 第一个元素将是根(索引处的值 = 0

img

A 被视为根

  1. 下一个元素(索引 = 1处)将是左元素,第三个元素(索引 = 2)将是根的右子元素

img

B 作为A左孩子,D 作为A右孩子

  1. 第四个(索引 = 3)和第五个元素(索引 = 4)将是 B 节点的左右子节点

img

EFB的左孩子和右孩子

  1. 下一个元素(索引= 5)将是节点D的左子节点

img

G 成为 D 节点的左子节点

这就是完整二叉树的创建方式。

完全二叉树的应用:
#

  • 堆排序
  • 基于堆排序的数据结构

顺序方式从给定数组构造完整二叉树
#

给定一个元素数组,我们的任务是以顺序方式从该数组构造一个完整的二叉树。也就是说,数组左侧的元素将从第 0 层开始逐层填充到树中。

示例:

输入:arr[] = {1, 2, 3, 4, 5, 6}
输出:以下树的根
                  1
                 / \
                2   3
               / \ /
              4  5 6


输入:arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6, 6}
输出:以下树的根
                   1
                  / \
                 2   3
                / \ / \
               4  5 6 6
              / \/
             6  66

我们仔细观察,我们可以看到,如果父节点位于数组中的索引 i 处,则该节点的左子节点位于索引 (2i + 1) 处,右子节点位于索引处 (2i + 2)在数组中。 利用这个概念,我们可以通过选择父节点来轻松插入左节点和右节点。我们将插入数组中存在的第一个元素作为树中第 0 层的根节点,并开始遍历数组,对于每个节点,我们将在树的左侧和右侧插入子节点。

下面是执行此操作的递归程序:

JavaScript 代码
#


let root

class Node {
    constructor(data) {
        this.left = null
        this.right = null
        this.data = data
    }
}

// 将 arr 数组中的元素构造为二叉树
function insertLevelOrder(arr, i) {
    let root = null
    if (i < arr.length) {
      root = new Node(arr[i]);
      // 设置节点的左节点
      root.left = insertLevelOrder(arr, 2 * i + 1);
      // 设置节点的右节点
      root.right = insertLevelOrder(arr, 2 * i + 2);
    }
    return root
}

// 按树结构打印元素
function inOrder(root) {
    if (root != null) {
        console.log("元素的值:" + root.data);
        inOrder(root.left)
        inOrder(root.right)
    }
}

let arr = [1, 2, 3, 4, 5, 6, 6, 6, 6];
// 将数组转换为树结构
root = insertLevelOrder(arr, 0);
// 打印树结构的元素
inOrder(root);

输出结果: [1 2 4 6 6 5 3 6 6]

Golang 代码
#

package main

import (
	"fmt"
	"testing"
)

type Node struct {
	Left  *Node
	Right *Node
	Data  int
}

// 给定数据构建二叉树
func insertLevelOrder(arr []int, index int) *Node {
	var node *Node
	if index < len(arr) {
		node = &Node{
			Left:  insertLevelOrder(arr, 2*index+1),
			Right: insertLevelOrder(arr, 2*index+2),
			Data:  arr[index],
		}
	}
	return node
}

func inOrder(node *Node) []int {
	var rest []int
	if node != nil {
		rest = append(rest, node.Data)
		rest = append(rest, inOrder(node.Left)...)
		rest = append(rest, inOrder(node.Right)...)
	}
	return rest
}

func Test_main(t *testing.T) {
	var arr = []int{1, 2, 3, 4, 5, 6, 6, 6, 6}
	node := insertLevelOrder(arr, 0)
	result := inOrder(node)
	fmt.Println(result)
}

输出结果: [1 2 4 6 6 5 3 6 6]