12.30平衡二叉树、生成树&最短路、链表、排序、二叉树——数算选择题专练

1

平衡二叉树

节点数目一定时，平衡因子为±1时，树最高。

平衡二叉树，左右子树都是平衡的，最少要满足一个式子，即维护左右都是AVL,最多就是满二叉树，节点总数为2^(h-1)；最少的时候，每个非叶子节点的度数都是1，即都只有一个孩子

高度为N的AVL,最少的话，要左子树为N-1高的AVL,右子树为N-2高的AVL，即

生成树&最短路

在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。（T）

画一个圆?

?若连通图上各边的权值均不相同，则该图的最小生成树是唯一的。

由k算法，即由边从小到大的顺序构造，如果边权值各不相同，那么构造出来的最小生成树唯一，就是唯一的顺序，从小到大?

关于带权无向图的最小生成树问题，若图中某回路上的边权值各不相同，则其中权值最小的边一定在某最小生成树中。

n个顶点一个环，那么这个图里有n个边，从中选一条边去掉，就是生成树，即C1N=N

链表

s->next=p->next;

p->next=s;

排序?

每次选最小的，然后缩小范围，如果是要问交换次数，最多就是换n-1次；需要交换就意味着此时这个位置上的元素不是最后正确的位置，应该把正确的元素放在这里

并非倒序为n-1,因为需要交换是意味着位置不对，如果是倒序的话，最大的和最小的换一下，相当于一下子确定了两个最终的，即最大的移到了最大的位置上，最小的移到了最小的位置上，如果要是N-1，就是每次只会让最小的移到位置上，然后那个交换的元素没有交换到最后正确的位置上

    for (int i = 1; i <= n - 1; i++) {//当前要确定的第i小的数
        int t = i;//备选首先设置为i
        for ( j = i + 1; j <= n; j++) {//从后续未排的牌堆里选一个最小的
            if (arr[j] < arr[t]) {
                t = j;
            }
        }
        if (t != i)swap(arr[i], arr[t]);//交换，确定第i小
    }

二叉树

可形成2种

入度=出度，除根节点外每个节点有一个入度，则n-1=n1+2n2=n0+n1+n2-1,故n0=n2+1

为49