度为 $k$ 的树，第 $i$ 层的最多结点数公式是 $k^{i-1}$ （根结点为第 1 层）。

• 其双亲编号 $p$ 为 ${\lfloor \frac{i+k-2}{k} \rfloor}$

• 编号为i的结点的第j个孩子结点编号 $c$ 为 ${c=(i-1)k + j + 1}$

深度为 $h$ 完全二叉树满足前 $h - 1$ 层是满二叉树，且第 $h$ 层的结点从左到右连续排列

• 对于有 n 个结点的完全二叉树，编号大于 $\lfloor \frac{n}{2} \rfloor$ 的结点一定是叶子结点

二叉树中，结点总数 $n$ 为度为0的结点加上度为1的结点再加上度为2的结点：

• $n = n_0 + n_1 + n_2$
• 另一方面，二叉树中度为1的结点有一个孩子， 度为2的结点有二个孩子，根结点不是何结点的孩子，因此，结点总数为： $n = n_1 + 2n_2 + 1$
• 两式相减，得到： $n_0 = n_2+ 1$

线索化二叉树， tag == 1 则指向前驱/后继，否则左/右子节点

哈希表不是线性表，哈希表是散列结构的

Prim算法适用于稠密图，Kruskal算法适用于稀疏图

如何评价一个算法？

• 正确性

• 可读性

• 健壮性

• 效率（时间复杂度和空间复杂度）

中缀表达式转后缀表达式

string infixToPostfix(const string& infix) {
    stack<char> opStack;      // 运算符栈
    string postfix = "";      // 后缀表达式结果

    // 定义运算符优先级（数值越高，优先级越高）
    map<char, int> precedence = {
        {'+', 1}, {'-', 1},   // 加减法优先级最低
        {'*', 2}, {'/', 2},   // 乘除法优先级中等
        {'^', 3}              // 指数运算优先级最高
    };

    // 遍历中缀表达式中的每个字符
    for (int i = 0; i < infix.length(); i++) {
        char ch = infix[i];

        // 跳过空格
        if (ch == ' ') continue;

        // 情况1: 操作数（一位数字或字母）
        // 根据题目假设，操作数只有一位
        if (isalnum(ch)) {
            postfix += ch;
        }

        // 情况2: 左括号 '('
        else if (ch == '(') {
            opStack.push(ch);
        }

        // 情况3: 右括号 ')'
        else if (ch == ')') {
            // 弹出栈顶运算符并添加到后缀表达式，直到遇到左括号
            while (!opStack.empty() && opStack.top() != '(') {
                postfix += opStack.top();
                opStack.pop();
            }
            // 弹出左括号（不添加到后缀表达式）
            if (!opStack.empty()) opStack.pop();
        }

        // 情况4: 运算符 (+, -, *, /, ^)
        else {
            // 处理优先级：弹出栈顶优先级更高或相等的运算符
            while (!opStack.empty() && opStack.top() != '(' &&
                   precedence[opStack.top()] >= precedence[ch]) {
                postfix += opStack.top();
                opStack.pop();
            }
            // 当前运算符入栈
            opStack.push(ch);
        }
    }

    // 遍历完成后，将栈中剩余的运算符全部弹出
    while (!opStack.empty()) {
        postfix += opStack.top();
        opStack.pop();
    }

    return postfix;
}

栈和队列具有相同的逻辑结构

关于广义表

• 长度：元素的数目。

• 表头：非空广义表中第一个元素。

• 表尾：除表头元素之外，其余元素构成的表。

• 深度：广义表中括号的重数。

树

• $n$ 个节点， $n - 1$ 条边

对于一棵度为3的树，要使得结点数为50时高度最小，应构造为完全三叉树，即除最后一层外每层都满，最后一层从左到右填充。计算不同高度下完全三叉树的最大结点数：

• 高度为4时，最大结点数为 $1+3+9+27=40$（满三叉树），小于 $50$ ；
• 高度为5时，最大结点数为 $1+3+9+27+81=121$，大于 $50$ ，且最小结点数为 $41$ （前4层满加第5层1个结点），可容纳50个结点。

若某二叉树有5个叶结点，其权值分别为10,12,16,21,30，则其最小的带权路径长度是

• int result = 0;
  while (pq.size() > 1) {
      int a = pq.top();
      pq.pop();
      int b = pq.top();
      pq.pop();
      int sum = a + b;
      result += sum;
      pq.push(sum);
  }
  cout << result;

完全二叉树

• 一棵深度为 k、有 n 个节点的二叉树，当且仅当其 每一个节点都与深度为 k 的满二叉树中编号从 1 到 n 的节点一一对应 时，这棵二叉树被称为完全二叉树。

设二叉树只有度为0和度为2的结点，其结点个数为15， 则该二叉树的最大深度为（）

• 给定二叉树只有度为0和2的结点，总结点数为15。
  由二叉树性质：叶子结点数 $n_0 = n_2 + 1$ ，且 $n_0 + n_2 = 15$ ，解得 $n_0 = 8$ ，$n_2 = 7$ 。

• 要使得二叉树深度最大，应构造为每个内部结点的一个子树为叶子，另一个子树继续延伸，形成链状结构。此时，从根到最深叶子路径上的内部结点数为7，叶子位于第8层（根为第1层）。
  最大深度为 8（按结点层数计算）。

AVL树

具有 $n$ 个顶点的有向图最多有 $n(n - 1)$ 条边

深度有限遍历类似于二叉树的前序遍历，广度优先遍历类似于二叉树的层次遍历

平均查找长度 $ASL$

• $ASL = \sum_{i = 1}^{n} P_i \cdot C_i$

  $P_i$ 为查找第 $i$ 个元素的概率

  $C_i$ 为第 $i$ 个元素所需关键字与给定值的比较次数

• 顺序查找算法分析

  假设查找每个关键字是等概率的 $\sum_{i=0}^{n-1}P_i \cdot (i + 1) = \frac{1}{n} \cdot \frac{n(n + 1)}{2} = \frac{n + 1}{2}$

• 二分查找 $ASL = \log_{2}{(n + 1)} - 1$

• 哈希表的 $ASL$ 分两种

  • 成功：$ASL = \frac{探测次数}{元素总数}$

  • 失败：$ASL = \frac{探测次数}{哈希表长度}$

  • 意思是失败的时候要再加上1

快排partition

•   /* 哨兵划分 */
    int partition(vector<int> &nums, int left, int right) {
        // 以 nums[left] 为基准数
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left])
                j--;                // 从右向左找首个小于基准数的元素
            while (i < j && nums[i] <= nums[left])
                i++;                // 从左向右找首个大于基准数的元素
            swap(nums[i], nums[j]); // 交换这两个元素
        }
        swap(nums[i], nums[left]);  // 将基准数交换至两子数组的分界线
        return i;                   // 返回基准数的索引
    }

严蔚敏挖坑填数分区法

• 初始: [46, 79, 56, 38, 40, 84]

1. 从右找<46的数: 40，移到左边: [40, 79, 56, 38, _, 84]
2. 从左找>46的数: 79，移到右边: [40, _, 56, 38, 79, 84]
3. 从右找<46的数: 38，移到左边: [40, 38, 56, _, 79, 84]
4. 从左找>46的数: 56，移到右边: [40, 38, _, 56, 79, 84]
5. low=high=3，放入基准: [40, 38, 46, 56, 79, 84]

int Partition(SqList &L,int low,int high)    //对子表进行排序，返回枢轴位置 
{
	L.r[0]=L.r[low]; 
	int pivotkey=L.r[low];    //将关键字记录在pivotkey中 
	while(low<high)
	{
		while(low<high&&L.r[high]>=pivotkey)
		{
			--high;
		}
		L.r[low]=L.r[high];
		while(low<high&&L.r[low]<=pivotkey)
		{
			++low;
		}
		L.r[high]=L.r[low];
	} 
	L.r[low]=L.r[0];
	return low;
}
void QSort(SqList &L,int low,int high)
{
    if(low<high)
    {
    	int pivotloc=Partition(L,low,high);
    	QSort(L,low,pivotloc-1);   //左子表递归 
    	QSort(L,pivotloc+1,high);  //右子表递归 
	}
}