内部资料，禁止传播客服热线：400-111-98111/7内部资料，禁止传播客服热线：400-111-98112/7软件设计师考试背记精要1、数组与矩阵：2、顺序表与链表对比：3、循环链表：队空条件：head=tail；队满条件：(tail+1)%size=head。4、树的概念：（1）双亲、孩子和兄弟：结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。（这里涉及到2个层次，第一个层次的子树，这棵子树的根是第一层结点的孩子结点，第一层结点是其子节点的双亲节点/父节点）。（2）结点的度：一个结点的子树的个数记为该结点的度（3）叶子节点：也称为终端结点，指度为0的结点（4）内部结点：指度不为0的结点，也称为分支节点或非终端节点。除根结点之外，分支结点也称为内部结点。（5）结点的层次：根为第一层，根的孩子为第二层，依次类推，若某节点在第i层，则其孩子结点在第i+1层（6）树的高度：一颗树的最大层次数记为树的高度（深度）5、二叉树的重要特性：（1）在二叉树的第i层上最多有2i-1个结点（i≥1）；（2）深度为k的二叉树最多有2k-1个结点（k≥1）；（3）对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。（4）如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到Llog2n˩+1层，每层从左到右），则对任一结点i（1≤i≤n），有：如果i=1，则结点i无父结点，是二叉树的根；如果i>1，则父结点是Li/2˩；如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；如果2i+1>n，则结点i无右子叶点，否则，其右子结点是结点2i+1。6、特殊的树：（1）二叉树：二叉树是每个结点最多有两个孩子的有序数，可以为空树，可以只有一个结点。（2）满二叉树：任何结点，或者是树叶，或者恰有两棵非空子树。（3）完全二叉树：最多只有最小面的两层结点的度可以小于2，并且最下面一层的结点全都集中在该层左侧的若干位置。（4）平衡二叉树：树中任一结点的左右子树高度之差不超过1。（5）查找二叉树：又称之为排序二叉树。任一结点的权值，大于其左孩子结点，小于其右孩子结点。（6）线索二叉树：在每个结点中增加两个指针域来存放遍历时得到的前驱和后继信息。内部资料，禁止传播客服热线：400-111-98113/7（7）最优二叉树：又称为哈弗曼树，它是一类带权路径长度最短的树。7、最优二叉树（哈弗曼树）的构造过程：（1）根据给定的权值集合，找出最小的两个权值，构造一棵子树将这两个权值作...
