【037-week1】算法训练营第一周学习总结

[SymerBoy]

1二叉树：
每个结点最多有两个子树的树结构，分为左子树和右子树
2二叉搜索树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值

二分查找：要求线性表必须采用顺序存储结构，而且表中元素是有序排列；

例如1,2,5,6,8,10,11,15； 是根据有序排列，
如果从数组中查询n所在下标位置，则只需要先从数组中间开始查询，如果中间值大于n,则向左遍历,反正从右边开始查询;
时间复杂度O(logN)

[lizhaochao]

二分查找：要求线性表必须采用顺序存储结构，而且表中元素是有序排列；

例如1,2,5,6,8,10,11,15； 是根据有序排列，
如果从数组中查询n所在下标位置，则只需要先从数组中间开始查询，如果中间值大于n,则向左遍历,反正从右边开始查询;
时间复杂度O(logN)

提到了时间复杂度是O(logN)，那空间复杂度呢，应该是O(1)
空间复杂度的定义是除了原本需要的空间外还需要多少空间，如果不再需要了就是O(1)

[sodexx7]

2二叉搜索树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值
二叉搜索树的定义还需加上一条：该性质对所有子树都使用。并且二叉搜索树，中序遍历为升序排序

[XHShirley]

谢谢你噢同学～ 把二叉树和二叉搜索树的性质总结了出来。其实这是两种特别的“树”，可以一起把“树”的遍历的规则和代码模版一起总结出来～