二叉树的定义就是1个节点上不超过2个孩子。
严格二叉树就是每一个节点上都只有2个孩子，除了叶子节点
完全二叉树就是底层可能没有填满，但是其他层一定是填满的，并且底层的节点都集中在该层的最左边的一些位置。所以完美二叉树就是完全二叉树的特例。并且完全二叉树的高度是[log2(n)]n是节点个数，[]向下取整。
关于完美二叉树：设高度为h，节点数量为n，那么n=2^(h+1)-1,可以解出来h=log2(n+1)-1。
完美二叉树中的所有的层级都会被填满。(讨论层级的话那么根节点为第0层)
一个节点的深度被定义为从根节点到该节点的路径上的边的个数。根节点为0，这里认为0即可。
一个二叉树的高度等于它的最大深度等于根节点的高度。高度是指从节点到叶子节点的最长路径上的边的个数。(这样的话就不把根节点计入高度了)，只有一个节点的树的高度为0，空树的高度是-1.
对树的操作比如搜索插入删除，时间复杂度都与其高度正比，即O(h),所以一般要求树的高度越低越好，对于完美二叉树和完全二叉树来说时间复杂度是O（log2(n)）,而最差情况下的稀疏树(和链表差不多)是O（n-1），如果n等于2的100次方，那么差距就会非常大。所以要求树尽量平衡。
平衡二叉树就是要求每一个节点的左孩子和右孩子的高度差diff不大于k,一般k取1.
diff=| hleft-hright |。即左子树的高度减去右子树的高度的绝对值。
一般来说创建一个二叉树可以使用链表的方式，一个数据域，二个指针域。对于1个完全二叉树可以用数组创建，左孩子的索引是2i+1,右孩子的索引是2i+2。从索引为0开始，树从左到右依次存储数据域。
二叉搜索树的特点就是任何一个节点的左孩子小于该节点，右孩子大于该节点。
二叉搜索树原来搜索为log2(n)和二分查找的O一样，没想到原理也几乎一样，对于二分查找start和end限定了搜索空间，每次查找都是使得搜索空间/2，设开始的搜索空间大小是n，假设经过了k次搜索找到了目标值，那么n/2^k=1(1表示搜索空间大小为1)，那么k=log2(n),二叉搜索树同理，在每个节点上都在做选择，如果小于目标就在右树查找，大于目标了就在左树里查找，每一次都是使得搜索空间/2，直到搜索空间为1. 基于实现这样的目标必须要求尽量平衡，树越平衡，看起来更像一课树，如果像一条链表的话，O仍是O(n)。
二叉搜索树的插入和删除都会改变树的平衡性，如果平衡性被打破的很严重那么就不能按照二分搜索的方法去看时间复杂度，所以必须的调整树，使其变的平衡。另外符合搜索二叉树要求的完美二叉树是最合适的用来搜索，插入，删除的容器。
原来递归，栈，堆的调用是这样的，就这次的二叉搜索树的构造为案例，当我在main函数里执行到了insert函数时，系统在栈里给insert函数分配一个帧栈内存，然后保存这个insert函数里变量的值，接下来就是套娃，我还是画图吧比较方便。
中序遍历搜索二叉树得到一组排好序的数据。