二叉树的基本内容

二叉树的基本内容 为什么会有树这种数据结构

完全二叉树：从上到下，从左到右一次平铺

 

一个数组查询的最低复杂度可以为O1（在我们知道下表的前提下）

然而我们面对的数组大多是无序二不确定的数据结构，我们则需要for循环，一个for

循环的时间复杂度为O（n）级别。

有序序列的时间复杂度logn：利用折半查找法：定义出数组的第一位置和最后一个位置，两者相加除以2，得到中间值的位置，一次循环，得到logn级别的时间复杂度。

因为我们很难追求O1级别的时间复杂度，所以我们要尽力追求logn级别的时间复杂度；

八大排序中，最快的快排的时间复杂度nlogn，这样难免会得不偿失。

一个无序链表的查询，可即便是有序的，也没有办法用折半查找法，（不能确定位置，数组中可以通过下标代替地址而链表不能）。同样的while循环查询，数组快于链表（数组的地址是连续的）。

我们最优的时间复杂度为logn，然而链表和数组都无法达到，更何况栈和队列。为此产生了树这种数据结构。

树

一个链表是由一个值和一个地址组成，树要注意自己的值和左右

 

链表只需要观察下一个地址是谁，而树要注意的是lnext和rnext

 

我们这这样可以看出，通过树来擦找数据，就是一个折半查找发

法。 

问题在于，树有很多种结构，完全二叉树本身是无序的，不可能达到我们希望的时间复杂度。

 

所以我们呢需要的是有序二叉树（左边的节点比右边的节点大），这样才能保证在logn级别

 

概念

常用概念：

1、节点：根节点A，叶子节点E F G H，父节点，子节点

2、节点的权：节点上的值

3、路径：从根节点到该节点所经过的线路

4、层：同一个级别为一层

5、子树：一个完整树当中的一个小的片段

6、树的高度：从根节点到最下面的节点经历的层数

 

分类

树的分类分为两种：二叉树和多叉树