10.30二叉树一些性质，找公共祖先（一般与搜索树），操作的复杂度，选择题细节

课上

 

一些结论，性质

n0,n1,n2指的是子结点的数量，n0没有子节点，叶子结点

n=2*n2+n1+1,若n1为奇数，则n为偶数，不然，则为奇数

满二叉树

没有度为1的结点，即每个结点要么没有孩子结点，要么就有两个孩子结点

没有孩子结点的结点一定是叶子结点

回顾 

寻找二叉搜索树最近公共祖先

思路是找到从根节点到两个结点的路径，由于是一个树，所以最开始的路径是一定一样的，即在同一颗树上至少具有相同的根节点，然后一直往下走，走到最后一个分岔口，开始分叉，即路径中最后一个相同的结点时，就是最近公共祖先

始终保持最近的相同结点，可以在退出时直接返回最后一个相同的结点，即最近公共祖先

找根节点到目标结点的路径，是从根节点开始

每次迭代中，先入当前结点，再更新，最后迭代结束，加入目标值

寻找二叉树的公共祖先

思路还是找路径，然后返回最后一个相同的结点

但由于不是搜索树，不满足左子树比根节点小，右子树比根节点大的性质，所以找路径的方法不同

采用dfs方式找路径，如果已经找到了，或者是叶子结点尝试继续向下，则直接返回

不然就是还没找到，先把当前的结点入列，然后判断是不是目标值，如果是就打上标记并直接返回

不然，继续递归向下

遍历两个孩子，看flag,如果在左子树里找到了，flag就会为1，那么在右子树中就不会继续递归，不然继续

最后都遍历完后，可能找到了，也可能没找到，找到了就直接返回，不操作，不然就说明当下的子树里没有，应该回溯

二叉树性质，复杂度

对于二叉树，我们维护一个堆，插入和依次获取元素的时间复杂度皆为O(logn)

插入

将元素插入最后一位，再进行向上冒泡，即如果父节点的值小于被插入的元素，父节点下移，被插入的元素上移。时间复杂度取决于树的高度h。而完全二叉树的树的高度为[logn+1]的上取整，所示时间复杂度为O(logn)。

n是插入前的树的结点数，插入完后n++

选择题

 

 

插入排序需要不断移动左序列，即遍历到的位置之前是有序的，后面是无序的，只有到最后才完全有序；选择排序是每次选一个最大的交换到序列的相应尾端位置；冒泡排序也是这个思路，只不过选择排序是选后交换，每次只用一次，但冒泡排序选和交换同时进行，每次至少需要一次

快速排序在有序时最慢为n^2，原因

标记，一些与……无关的排序

元素的移动次数与关键字的初始排列次序无关的是：基数排序

元素的比较次数与初始序列无关是：选择排序

算法的时间复杂度与初始序列无关的是：选择排序

最坏的情况和最好的情况恰好相反，在指定好比较的方向下

如果是从左到右，每次都和有序的第一个（当前的最小）比较，那么逆序是最好，顺序是最坏

这时插入的判断条件是找到左边为空或比左边大，右边为空或比右边小的位置

如果是从右到左，每次都和有序的最后一个（当前的最大）比较，那么逆序是最坏，顺序是最好

因为逆序时，每次接下来的牌都是当前的最小，顺序时，每次的牌都是当前的最大