树

概念

根 节点

• 父节点
• 子节点
• 叶子节点
• 度 层数 深度

二叉树

一个节点的度为0，1，2 完全二叉树:最下层节点度为0，其余节点为2。

二叉树遍历

采用递归实现，调整输出语句的位置

1.前序遍历

根-左-右

2.中序遍历

左-根-右

3.后序遍历

左-右-根

两种遍历能否确定唯一二叉树

中序遍历+前序遍历或后续遍历：YES
前序遍历+后续遍历:No

原理

通过前序或者后续可以确定根节点，通过根节点可以在中序遍历中取得左子树和右子树。然后从取得的左右子树中在前/后序遍历中取得根节点，以此类推确定唯一的树。

后序+中序确定前序代码

用DFS来构建二叉树，同时输出前序遍历结果。后序遍历总是可以确定当前树的根节点，然后利用确定的根节点在中序遍历的字符串中的位置分割出左子树和右子树。然后进行递归调用，根据先左后右继续构建，当长度为1时直接输出节点。当左/右子树不存在时停止继续递归(pos = 0,pos =b.length()-1);

void dfs(string m, string b)
{
    if(b.length() == 1)
    {
        cout << b;
    }
    else
    {
        char t = b[b.length() - 1];
        cout << t;
        int pos = m.find(t);
        if(pos > 0)
            dfs(m.substr(0, pos), b.substr(0, pos));
        if(pos <b.length()-1)
            dfs(m.substr(pos + 1), b.substr(pos, b.length()-pos-1));
    }
}

证明：当一棵根节点为1的满二叉树的节点i的左右子节点分别为2*i和2*i+1

1. 归纳奠基

对于根节点 (i = 1)：

• 左子节点的索引是 (2 \times 1 = 2)。
• 右子节点的索引是 (2 \times 1 + 1 = 3)。

显然满足。

2. 归纳假设

假设对于某个节点 (i = k)，其左子节点的索引为 (2 \times k)，右子节点的索引为 (2 \times k + 1)。

3. 归纳递推

需要证明，对于节点 (i = k+1)，其左子节点的索引为 (2 \times (k+1))，右子节点的索引为 (2 \times (k+1) + 1)。

根据完全二叉树的层次遍历顺序，节点 (i = k+1) 的子节点紧随着 (i = k) 的子节点入队。根据归纳假设，我们知道 (i = k) 的左右子节点分别为 (2 \times k) 和 (2 \times k + 1)。

因此，节点 (i = k+1) 的左右子节点应该是：

• 左子节点索引为 (2 \times (k+1) = 2 \times k + 2) 。
• 右子节点索引为 (2 \times (k+1) + 1 = 2 \times k + 3)。

证毕。

结论

通过数学归纳法，证明了在一个根节点为1的完全二叉树中，任意节点 (i) 的左子节点索引为 (2 \times i)，右子节点索引为 (2 \times i + 1)。这也解释了为什么线段树的节点子节点的索引是 (i \times 2) 和 (i \times 2 + 1)：线段树可以看作是一种二叉树，但是它的空节点也进行编号，所以它的一个节点的左右儿子节点编号和相同规模的完全二叉树的左右子节点的编号相同。