数据结构——二叉树

二叉树(Binary Tree)

为什么要有二叉树 二叉树结合了有序数据，链表两者的优势，在树种查找数据的素的和有序数组中一样快，插入数据和删除数据的速度和链表一样快

树的概念

节点、根节点、父节点、子节点、兄弟节点节点高度:子树的个数树的高度：所有节点度中最大值叶子节点：度为0的节点非叶子节点：度不为0的节点层数：根节点在第一层,开始计算节点的深度：从根节点到当前节点的唯一路径上的节点数量节点的高度：从当前节点到最远叶子节点的路径上的节点总数树的深度：所有节点深度中的最大值树的高度：等于树的深度有序树：树中任意接待你的子节点之间有顺序关系无序树：树中任意节点的子节点之间没有顺序关系，自由树森林：互不相交的树度：表示节点的子树du或直接继承者的数目，2度是两个孩子，或者左和右子树有两个叉树，最大度数为2。

二叉树特点

每个节点的度最大为2左子树和右子树是有顺序的，但是没有严格的要求从大到小还是从小到大二叉树是有序树

二叉树性质

非空二叉树的第i层，最多有2^(i-1)个节点(i>=1)在高度为h的二叉树上最多有2^(h)-1 个节点(h>=1)真二叉树 所有节点的度都为0或者2 满二叉树 全满，最后一层节点度都为0，其他节点度都为2 完全二叉树 对节点从上到下，从左到右、一层一层编号

二叉树的遍历

遍历是数据结构中的常见操作把所有元素都访问一边根据节点访问顺序的不同，二叉树的遍历方式有4种： 例如节点是：7,4,2,1,3,5,9,8,11,10,12 前序遍历 7,4,2,1,3,5,9,8,11,10,12用于树形结构展示 中序遍历 1、2、3、4、5、7、8、9、10、11、112、11、10、9、8 、7、5、4、3、2、1二叉搜索树的中序遍历按升序或者降序处理节点 后序遍历 1、3、2、5、4、8、10、12、11、9、7用于先子后父的操作 层序遍历 7、4、9、2、5、8、11、1、3、10、12计算二叉树的高度判断一棵树是否为完全二叉树

二叉搜索树(Binary Search Tree)

二叉搜索树的特点

二叉树的一种，应用非常广泛又被称为二叉查找树，二叉排序树任意一个节点的值都大于其左子树所有节点的值任意一个节点的值都小于其右子树所有节点的值二叉搜索树可以大大提高搜索数据的效率存储的元素必须具备可比较性，比如int，double如果是自定义类型，需要制定比较方式不允许为null

平衡二叉搜索树(balanced binary search tree)

平衡二叉搜索树的特性

平衡：当节点数量固定时，左右子树的高度越接近，这颗二叉树就越平衡经典平衡二叉搜索树，也称作自平衡二叉搜索树 AVL树红黑树Java中的 TreeMap、TreeSet、HashMap、HashSetLinux虚拟内存

AVL树

AVL树的特性

平衡因子:某节点的左右子树的高度差平衡因子的高度差在-1~1之间每个节点的左右子树高度差不超过1搜索添加删除的时间复杂度是O(logN)