数据结构 之二叉树

遍历

        遍历二叉树，有三种遍历方式：

                前序      中序（最常用）       后序

        前序 中序 后序 遍历的步骤是相同  只是顺序不同

前序遍历顺序

       先输出当前节点      在遍历左节点    在遍历右节点

 中序遍历顺序

        先遍历左节点        在输出当前节点    在遍历右节点

后序遍历顺序

         先便利左节点       在遍历右节点     在输出当前节点

   可以看出所谓的前中后序 是是输出当前节点数的顺序    前序第一个输出当前节点      中序第二个   后续最后一个

   又因为中序是按照数值大小顺序来的  所以中序最常见 

二叉树效率：

       二叉树和数组与链表对比    在有100w的数据项的无序数组和链表对比 查 插入  删除都最少50w次的改动 比较

 在100万数据的树上只需要20次的比较  再加上很少的时间去连接数据项

       所以树所有的常用数据存储操作都有很高的数据效率

      遍历不如其他操作快  但是遍历在大型数据库中不是常用操作

 如果二叉树是平衡的  效率为：O(logN)，如果是不平衡的  (最极端的情况,存入树中的数据是升序或降序排列的,那么二叉树就是链表),效率为: O(N)     所以二叉树在随机保存数值的情况下效率最高

缺点：

            如果二叉树是极端不平衡的(此时的二叉树就是一个链表),它的效率为O(N),即使数值是随机的,如果数据的量够大,也有可能有一部分的数值是有序的(就像你抛硬币的时间足够长,会有一段时间出现一直抛正面或反面),造成二叉树会变成是局部不平衡的,这样它的效率会介于O(logN)到O(N).