二叉树Binary Tree

Ysjt | 深 ™

2024-06-28 18:12:19

发布于：广东

9阅读

0回复

0点赞

以下内容为二叉树Binary Tree,本文同步CSDN^[1]

数的定义与相关概念

树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：①有且仅有一个特定的称为根（Root）的结点；②当n>1时，其余结点可分为m（m>0）个互不相交的有限集

$T 1 {T}_{1}T 1 、T 2 {T}_{2}T_{2} 、… 、T {m -1} $

，其中每一个集合本身又是一棵树，并且称为根的子树（Sub Tree）。(图1)

树的相关概念

树的术语：

（1）路径：在两个节点之间，一系列的边和节点的组合。路径的长度是组成路径的边数。

（2）深度：一个节点的深度是指从根节点到该节点的最长路径上的边数。根节点的深度为0。

（3）层次：树的层次从根开始定义，根为第一层，根的子节点为第二层，以此类推。

（4）高度：树的高度是从叶子节点开始自底向上逐层累加的路径上边的数量。根节点的高度就是树的高度。

在C++中，树的存储结构主要有两种：顺序存储和链式存储。不同的存储结构对应着不同的表示方法，如孩子表示法、双亲表示法、孩子兄弟表示法等。

顺序存储：顺序存储通常用于完全二叉树。在完全二叉树中，除了最后一层外，其他层的节点数是满的，并且最后一层的节点都靠左排列。这种特性使得完全二叉树可以使用数组进行顺序存储，其中每个节点的索引与其在树中的位置相关。
链式存储：链式存储通过节点和指针来表示树中的关系。每个节点包含数据域和指向其子节点的指针域。链式存储方式更加灵活，适用于各种类型的树。

上述代码(代码在最后)展示了如何使用孩子表示法来创建一个树，其中每个节点都有一个指向其子节点的指针列表。这种方式可以很直观地表示一个节点的所有子节点，但是在查找父节点时不够高效，因为父节点的信息并未存储在当前节点中。

在双亲表示法中，每个节点不仅包含数据域和指向其子节点的指针，还包含一个指向其父节点的指针。这使得我们可以方便地访问一个节点的父节点，但可能需要额外的空间来存储父节点的指针。

在双亲表示法中，我们可以沿着父节点的指针向上遍历树，直到找到根节点或者到达一个父节点为空的节点。这种表示法在需要频繁进行父子节点关系查询时比较有用。

孩子兄弟表示法是一种结合了孩子表示法和双亲表示法的思想的方法。在这种表示法中，每个节点包含指向其第一个孩子节点的指针和指向其下一个兄弟节点的指针。这种表示法对于二叉树非常自然，并且可以很方便地表示任何类型的树。

在这种表示法中，通过firstChild可以访问到该节点的所有子节点，而通过nextSibling可以遍历该节点的所有兄弟节点。这种方法特别适合处理那些子节点之间没有顺序要求的树结构。

每种存储结构都有其适用的场景和优缺点，例如顺序存储适合表示完全二叉树，而链式存储则更加灵活，能够表示任意结构的树。在实际应用中，需要根据具体需求和树的特点来选择适当的存储结构.

代码原文链接：

树的计算公式 (通用)

变量说明

度为 $m$ 的结点数 = $n_{m}$

$i $: 第 $i$ 层或第 $i $号结点;

$h $: 树的高度;

$ceil$ 向上取整, $floor$ 向下取整

总结点数= $n_{0}+n_{1}+.....+m_{m}$

总分支数= $1\times n_{1}+2\times n_{2}+......+m\times n_{m}$

度为 $m$ 的树的第 $i$ 层最多有 $m^{i-1}$ 个结点( $i\geq 1$ )

高度为 $h$ 的 $m$ 叉树最多有 $m^{h-1}\div m-1$ 个结点

具有 $n$ 个结点的 $m$ 叉树的最小高度为 $ceil(log_{m}(n(m-1)))$

二叉树计算公式

非空二叉树中 $n_{0}=n_{2}+1$

非空二叉树中结点数为 $n$ 时, $边数 = n − 1$

高为 $h$ 的二叉树最多有 $2^{h-1}$ 个结点

满二叉树计算公式

编号问题 : 编号为 $i$ 的结点双亲为 $floor(i\div 2)$

左孩子编号为 $2i$

右孩子编号为 $2i+1$

完全二叉树计算公式

编号问题 : 编号为 $i$ 的结点 :

$(i\leqslant floor(n\div 2) )$ 则 i 为分支结点, 否则 i 就是叶子结点

按层编号, 当编号为 i 的结点为叶子结点或只含左子节点 , 则编号大于 i 的都是叶子结点;

总结点数为奇数, 每个分支节点都要左右子结点;

总结点数为偶数, 编号最大者 $(i=n\div 2)$ 只有左叶子节点;

n个结点的完全二叉树的高度为 $h=ceil(log_{2}(n+1))$ 或 $h=floor(log_{2}(n+1))$

若某节点编号为 i :

$2i\leqslant n$ i的左子节点编号为 $2i$ , 否则就是没有左子节点;

$2i+1\leqslant n$ i的右子节点编号为 $2i+1$ , 否则就是没有右子节点;

最后一个分支结点的编号为 $floor(n\div 2)$

本文参考资料:
C++树详解
 【数据结构与算法 C/C++】树/二叉树计算公式总结
 C++的数据结构(五）：树和存储结构及示例
 编程学习中心

废话文学:文章打字时长:2小时27分56秒

~~(累死我了)~~

CSDN账号 ↩︎

有帮助，赞一个

去预览

0/2000

这里空空如也

数的定义与相关概念

树的相关概念

树的计算公式 (通用)

变量说明

总结点数=n0+n1+.....+mmn_{0}+n_{1}+.....+m_{m}n0​+n1​+.....+mm​

总分支数=1×n1+2×n2+......+m×nm1\times n_{1}+2\times n_{2}+......+m\times n_{m}1×n1​+2×n2​+......+m×nm​

度为mmm的树的第iii层最多有mi−1m^{i-1}mi−1个结点(i≥1i\geq 1i≥1)

高度为hhh的mmm叉树最多有mh−1÷m−1m^{h-1}\div m-1mh−1÷m−1个结点

具有 nnn个结点的 mmm叉树的最小高度为ceil(logm(n(m−1)))ceil(log_{m}(n(m-1)))ceil(logm​(n(m−1)))

二叉树计算公式

非空二叉树中n0=n2+1n_{0}=n_{2}+1n0​=n2​+1

非空二叉树中 结点数为nnn时,边数=n−1边数 = n − 1边数=n−1

高为hhh的二叉树最多有2h−12^{h-1}2h−1个结点

满二叉树计算公式

编号问题 : 编号为iii的结点双亲为 floor(i÷2)floor(i\div 2)floor(i÷2)

左孩子编号为 2i2i2i

右孩子编号为 2i+12i+12i+1