Java 学习~（基础概念理论） what 是 树，二叉树（满二叉和完全二叉），二叉树遍历说明，有序二叉树_java 完全二叉树时间复杂度

树本身是链式存储结构

前言

在实际应用过程中链表本身的时间复杂度为O(n)级别，在长度比较短的情况下认为是O(1)级别。但过于长了呢？有没有什么办法能降低长链表的时间复杂度O(n)呢？

比O(n)级别小的复杂度有 O(logn)和O(1)，O(1)级别的时间复杂度基本处于一种理论阶段，很少有算法能达到O(1)级别复杂度。那有没有办法能把复杂度降低到O(logn)级别呢？

logn 有一句话叫循环减半logn。O(n)级别复杂度是利用循环从前到后进行遍历，O(logn)级别是利用循环每次折一半数据。数组中查找某一元素有折半查找法，时间复杂度为O(logn)，但是前提是有序数组。

而链表不一定要有序，也能达到O(logn)级别复杂度，那就是-------树

普通的   树 

 一颗平凡的树：

 树的组成部分：

1.节点 :A,B,C.....G 都是节点。

        节点又分:根节点（就一个）： A

                        父节点（有孩子的节点）：A ,B,C,D

                        子节点：E,F,G

                        叶子节点（没有子孩子的节点）：E,F,G

2.节点的权：节点的值 

3.路径：根节点到该节点走过的节点。

                根节点是A，假如是到G节点，路径就为：A,B,D,G

4.层的概念：就字面意思，有几层，此例有 4 层

5.子树：除根节点之外的树，圈圈中的都可以叫子树。

               

6.树的高度：有几层，上面说了 4 层，所有高度是 4

7.森林：多颗 子树 构成森林。

此例是二叉树，树可能有很多叉，都遵循这 7 个概念。二叉树在实际应用中比较多

二叉树------（ 满二叉树 和 完全二叉树 ）

 每个节点下最多有两个节点，成为二叉树。（有三个称为三叉树 。。。。。）

二叉树有两个门神：满二叉树 和 完全二叉树

        满二叉树：最后一层 数据 铺满的。个个父节点都有两个孩子。   

     ​​​​​                                ​​        

        完全二叉树：从上到下，从左到右依次进行平铺就是完全二叉树。上方这个满二叉树，也是完全二叉树。但如果少一个孩子：

                这还是一个完全二叉树，但不是满二叉树（因为最后一层没铺满）。

          但        这就不是一个完全二叉树，没有遵循 从上到下 从左到右 依次 排序。什么叫依次，注意！

     -----------------------------------------------------------------------------------------------------------------------------

          二叉树的遍历说明：

 

                                                               ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​   例子​​​​​​​        ​​​​​​​​​​​​​​

 层次遍历：就是  5，4，7，2，3，6，8。一层一层写下来。

先序遍历：先输出父节点，再遍历出左子树，在遍历输出右子树

      先根据规则  5,4,7----- 4 也是父节点再根据规则------>5,4,2,3,7------7也是父节点----->5 423 768

中序遍历：先 左， 再 父， 再 右。

          4,5,7----->父4 的左右---->2,4,3, 5 , 7------父7的左右----->2,4,3, 5, 6,7,8

后序遍历：先左 ，再右，再父

        4,7,5------->父4 的左右---->2,3,4,7,5------->父7的左右----->2,3,4,6,8,7,5

有序二叉树

利用树这种链式存储结构也能达到O(logn)级别时间复杂度，树的存储和读取的效率比较高，但不是所有的 树 都能达到O(logn)。

只有一些特殊的树：比如有序二叉树

有序二叉树 特性：树的根节点，必须大于等于左子树，必须小于等于右子树。如当前这棵树的时间复杂度就是O(logn),每次查询都能折掉一半数据 。

 当链表短就认为是O(1)级别，当特别长的时间达到O(n)级别，能不能 瞬间 转换成树呢！

有序二叉树 的插入 不能 是有序的，

  。。。根据有序二叉树的特性排列， 这样是不是就又成一个链表啦，大量有序就失去了平衡的特点。