二叉树解决了什么问题?_合肥千锋IT培训

二叉树解决了什么问题?

来源：千锋教育

发布人：xqq

时间： 2023-10-17 16:51:04

一、二叉树解决了什么问题

1、元素搜索

二叉树的快速查找性质使其非常适合于元素搜索。通过二叉树的查找操作，可以高效地搜索指定元素是否存在于树中。

2、数据排序

二叉搜索树还可以用于数据排序。具体地说，将数据插入到二叉搜索树中，并按照一定规则遍历树，就可以得到有序的数据。

3、反向顺序遍历

通过对二叉树的左右子树遍历顺序进行逆序遍历，可以实现反向顺序遍历。这在某些场景下非常有用，例如一个日志文件，需要按时间逆序输出。

4、构建有效的数据结构

二叉树可以应用到各种算法和系统中，提供高效的数据存储和查找，非常适用于构建各种有效的数据结构，例如哈希表、堆等，这些数据结构在计算机科学中被广泛使用。

二、二叉树性质

1、一般二叉树性质

在非空二叉树的i层上，至多有2^i-1个节点(i>=1)。通过归纳法论证。在深度为K的二叉树上非常多有2^k-1个结点（k>=1)。通过归纳法论证。对于任何一棵非空的二叉树,如果叶节点个数为n₀，度数为2的节点个数为n₂，则有: n0 = n₂ + 1。

在一棵二叉树中，除了叶子结点（度为0）之外，就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2；在二叉树中结点总数为T，而连线数为T-1。所以有：n0+n1+n2-1 = 2*n2 +n1；最后得到n0 = n2+1。

2、完全二叉树性质

具有n的结点的完全二叉树的深度为log₂n+1：

满二叉树是完全二叉树，对于深度为k的满二叉树中结点数量是2^k-1 = n，完全二叉树结点数量肯定非常多2^k-1，同时完全二叉树倒数第二层肯定是满的（倒数名列前茅层有结点，那么倒是第二层序号和满二叉树相同），所以完全二叉树的结点数最少大于少一层的满二叉树，为2^k-1-1。

根据上面推断得出：2^k-1-1< n=<2^k-1，因为结点数Nn为整数那么n<=2^k-1可以推出n<=2^k，n>2^k-1-1可以推出 n>=2^k-1，所以2^k-1k 。即可得k-1<=log₂n2n]+1。

如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有：

如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整如果2i>n那么节点i没有左孩子，否则其左孩子为2i如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

三、特殊的二叉树及其特点

1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少。

2、满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。就是完美圆满的意思，关键在于树的平衡。

根据满二叉树的定义，得到其特点为：

叶子只能出现在最下一层。非叶子结点度一定是2。在同样深度的二叉树中，满二叉树的结点个数非常多，叶子树非常多。

3、完全二叉树

对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。

其中关键点是按层序编号，然后对应查找。

结合完全二叉树定义得到其特点：

叶子结点只能出现在最下一层（满二叉树继承而来）。最下层叶子结点一定集中在左部连续位置。倒数第二层，如有叶子节点，一定出现在右部连续位置。同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

延伸阅读1：平衡二叉树

平衡二叉树或者是一颗空树，或者是具有以下性质的二叉树：它的左子树和右子树的深度之差的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。平衡因子(bf)：结点的左子树的深度减去右子树的深度，那么显然-1<=bf<=1。很显然，平衡二叉树是在二叉排序树(BST)上引入的，就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。