二叉树的理论知识

二叉树结点计算方法是：2*k-1，k为深度。

满二叉树：

节点都是对称的，每层节点都是满的。

 完全二叉树：

二叉树的最底层从左至右拥有节点，中间断开就不为完全二叉树了

 断开节点

 满二叉树一定是完全二叉树哦~

二叉搜索树：

顾名思义，方便遍历搜索节点的二叉树，遍历的时间复杂度是O(logN)。

实现左节点小于（大于）根节点

右节点大于（小于）根节点。

平衡二叉搜索树：

 定义方式为左右节点的深度绝对值!>=2

二叉树的存储方式：

 一种是直接使用链表进行存储：

定义如下：

package shuJuJieGouYuSuanFa.erChaShu;
 
public class MyErChaShu {
    MyErChaShu l;
    MyErChaShu r;
    int val;
 
    public MyErChaShu() {
    }
 
    public MyErChaShu(MyErChaShu l, MyErChaShu r, int val) {
        this.l = l;
        this.r = r;
        this.val = val;
    }
 
    public MyErChaShu(int val) {
        this.val = val;
    }
}

这是一种比较常见的方式。也是一种令我头疼不已的方式，看见二叉树就开始头疼了！！

使用数组存储:

这种方式我认为使用的效率不高，如果不是满二叉树的话，有许多下标对应的位置都是空的，空间利用度差了一点。

2^(k)-1个空间大小。

节点的左节点计算方式为：

2*i+1；

右节点计算方式：

2^(h)-1

二叉树的遍历方式：

前序遍历：(28条消息) 前序遍历笔记_小肖在路上的博客-CSDN博客

中序遍历：(28条消息) 中序遍历笔记_小肖在路上的博客-CSDN博客_中序遍历过程 

后续遍历：我还没写，以后补上~

其实记遍历有一个技巧：

前序遍历为：中、左、右

中序遍历为：左、中、右

后序遍历为：左、右、中

发现了吧~~没错！！所谓的前序后续什么什么的，描叙的是根节点“中”的遍历顺序