二叉树什么场景下会使用(二叉树的作用)

二叉树什么场景下会使用

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。分为满二叉树，完全二叉树，排序二叉树。

二叉树的作用

树,连通但没有回路的图
二叉树是一类非常重要的树形结构，它可以递归地定义如下：
二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2
。u(1)和u(2)有时分别称为T的第一和第二子树。

05 - 二叉树的认识

树形结构是一对多的关系，而且树的定义是递归的，因为在树的定义中又用到树的定义。

定义：
树是由n(n>=0)个节点组成的有限集合，其中如果n=0，是一颗空树，如果n>0,这n个节点存在且仅存在一个节点作为树的根节点，其余节点可分为m个互不相交的有限集，其中每个子集本身又是一颗符合本定义的树，称为根的子树。
每一个节点可以有零个或多个后继节点，但有且只有一个前驱节点（根节点除外）。

是一种顺序存储结构，在节点中存储节点的值，同时存放指向双亲节点的指针
优点是查找双亲方便

是一种链式存储结构，在节点中存储节点的值，同时存放指向所有包含其所有孩子节点的指针。
指针域的个数就是树的度
优点是查找孩子方便

是一种链式存储结构
有三个域

最大的优点是可以方便的实现树和二叉树的相互转换

先根遍历：

后根遍历：

层次遍历：

二叉树是有限的节点集合，这个集合或者是空，或者是由一个根节点和两颗互不相交的称为左子树和右子树的二叉树构成。

二叉树与度为2的树的差异

在一棵二叉树中，如果所有分支节点都有左孩子节点和右孩子节点，并且叶子节点都集中在二叉树的最下层，这样的二叉树就是满二叉树
满二叉树的高度为h，且有2^h-1个节点的

特点：

若二叉树最多只有最下面两层的节点的度数小于2，并且最下面一层的叶子节点都一次排列在该层最左侧的位置上，这样的二叉树就是完全二叉树

特点：

二叉查找树的节点是有序的，也叫二叉搜索树、有序二叉树、排序二叉树。
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值，若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

特点：

优点：因为有序所以便于查找

二叉树中任意一个节点的左右子树的高度相差不能大于 1，谓之平衡

特点：

1.平衡二叉树要么是一棵空树
2.要么保证左右子树的高度之差不大于 1
3.子树也必须是一颗平衡二叉树

红黑树是一种自平衡的二叉查找树，它可以进行高效的查找。

它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的，时间复杂度为O(lgn)。

特点：

1.每个节点或者是黑色，或者是红色
2.根节点是黑色
3.每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4.如果一个节点是红色的，则它的子节点必须是黑色的
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。因为需要更加平衡

过程：

示例

转化前：

转化后

将上面的反过来就可以

有两种，顺序存储二叉树和链式存储二叉树，一般使用链式存储结构，如果是完全二叉树可以使用顺序存储结构。

说明：

使用：

特点：查询快，增删慢

每个节点存储有节点数据、左孩子节点指针、右孩子指针

说明：

特点：增删快

构造原理：
同一棵树有唯一的先序序列、中序序列、后序序列，但是不同的二叉树可能有相同的先序序列、中序序列、后序序列，
所以如何根据这些序列来构造二叉树呢，需要中序序列加上先序序列（或后序序列），这是因为先序或后序会确定根节点，中序序列会确定左右孩子节点，以此来确定二叉树。

中序序列+先序序列

中序序列+后序序列

案例：
先序序列为：ABC
中序序列为：ACB

说明：

遍历是指访问二叉树中所有节点，并且每个节点只访问一次
根节点可以放在先、中，后三个地方、又因为左右子树的顺序不一样，所以可以分为六种遍历方式，再加上层次遍历，共有七种

下面以先左子树，后右子树的方式来说明

先序遍历
1、先访问根节点
2、先序遍历左子树
3、先序遍历右子树

中序遍历
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树

后序遍历
1、后序遍历左子树
2、后序遍历右子树
3、访问根节点

层次遍历
1、访问根节点
2、依次访问第二层、第三层

案例

先序遍历：1、2、4、5、7、8、3、6
中序遍历：4、2、7、5、8、1、3、6
后序遍历：4、7、8、5、2、6、3、1
层次遍历：1、2、3、4、5、6、7、8

红黑树，b+树分别用于什么场景，为什么

红黑树属于“黑平衡”的二叉树，虽然牺牲了一定的平衡性，但是add、remove操作要由优于AVL树也就是说RB-Tree的“统计性能”更佳！Java中TreeSet，TreeMap的底层都是基于RedBlackTree红黑树的；
B+树主要用在文件系统以及数据库做索引。比如磁盘存储、文件系统、MySQL数据库

声明： 我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理，本站部分文字与图片资源来自于网络，转载是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益，请立即通知我们(管理员邮箱：daokedao3713@qq.com)，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!