树

二叉树

每个节点最多有两个叉，分别是左子节点和右子节点

满二叉树

完全二叉树

便于使用数组存储，更节省空间
堆就是一种完全二叉树

二叉树遍历

前序
中序
后序

二叉树遍历时间复杂度

O(n)

二叉查找树（二叉搜索树）

支持动静态数据集合的快速插入，删除，查找操作，快速查找最大结点和最小节点，前驱结点和后继结点

特点
树种任意一个节点，其左子节点中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值
中序遍历可输出有序数据序列，时间复杂度O(n)

支持重复数据的二叉查找树
1，通过链表支持动态扩容的数组，把值相同的数据存储在同一个节点上
2，放在他的右子树中，查找时遇到形同结点不停止查找直到找到叶子结点为止

复杂度分析
极度退化的链表O(n)
最理想情况下是完全二叉树（或满二叉树）O(height)时间复杂度都跟树的高度成正比