三、树（14 题）

校订文本 · 对照材料 · 专题阅读 · 保留代码与校订注 · 本次导入快照

三、树（14 题）

默认结构

typedef struct BTNode {
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
} BTNode, *BiTree;

1. 判断二叉树是否为正则二叉树

正则二叉树中每个结点的度只能为 0 或 2。

bool isRegularBinaryTree(BiTree root) {
    if (root == NULL)
        return true;

    bool hasLeft = root->lchild != NULL;
    bool hasRight = root->rchild != NULL;
    if (hasLeft != hasRight)
        return false;

    return isRegularBinaryTree(root->lchild)
        && isRegularBinaryTree(root->rchild);
}

复杂度： 时间 O(n)，递归栈空间 O(h)；最坏情况下 h=n。

2. 将二叉表达式树转为等价中缀表达式（2017 年统考题）

void printInfix(BiTree root, int depth) {
    if (root == NULL)
        return;

    bool isOperator = root->lchild != NULL || root->rchild != NULL;
    if (isOperator && depth > 0)
        printf("(");

    printInfix(root->lchild, depth + 1);
    printf("%c", root->data);
    printInfix(root->rchild, depth + 1);

    if (isOperator && depth > 0)
        printf(")");
}

调用方式：printInfix(root, 0);。

复杂度： 时间 O(n)，递归栈空间 O(h)。

核心思路： 按中序遍历输出；除根结点外，每棵非叶子子树外加括号，从而保持原表达式树的运算次序。

3. 计算二叉表达式树的值

下面假设叶子结点为字符 '0'..'9'，内部结点为 +、-、*、/。

int evaluateExpressionTree(BiTree root) {
    if (root->lchild == NULL && root->rchild == NULL)
        return root->data - '0';

    int left = evaluateExpressionTree(root->lchild);
    int right = evaluateExpressionTree(root->rchild);

    switch (root->data) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/': return left / right;
        default:  return 0;  // 实际程序中应报告非法运算符
    }
}

复杂度： 时间 O(n)，递归栈空间 O(h)。

若叶子是变量（如 a、b），需另行传入变量到数值的映射；若允许除数为零，也必须增加错误处理。

4. 输出根结点到每个叶子结点的路径

void printRootToLeafPaths(BiTree root, char path[], int depth) {
    if (root == NULL)
        return;

    path[depth] = root->data;
    depth++;

    if (root->lchild == NULL && root->rchild == NULL) {
        for (int i = 0; i < depth; i++)
            printf("%c%s", path[i], i + 1 == depth ? "\n" : " -> ");
        return;
    }

    printRootToLeafPaths(root->lchild, path, depth);
    printRootToLeafPaths(root->rchild, path, depth);
}

复杂度： 遍历时间 O(n)，加上输出本身所需时间；辅助数组和递归栈均为 O(h)。

若要按“叶子到根”输出，只需在叶子处将循环改为从 depth-1 递减到 0。

5. 增加 parent 指针并输出每个结点到根的路径

typedef struct ParentBTNode {
    char data;
    struct ParentBTNode *lchild;
    struct ParentBTNode *rchild;
    struct ParentBTNode *parent;
} ParentBTNode, *ParentBiTree;

void setParents(ParentBiTree root, ParentBiTree parent) {
    if (root == NULL)
        return;

    root->parent = parent;
    setParents(root->lchild, root);
    setParents(root->rchild, root);
}

void printAllPathsToRoot(ParentBiTree root) {
    if (root == NULL)
        return;

    for (ParentBiTree p = root; p != NULL; p = p->parent)
        printf("%c%s", p->data, p->parent == NULL ? "\n" : " -> ");

    printAllPathsToRoot(root->lchild);
    printAllPathsToRoot(root->rchild);
}

先调用 setParents(root, NULL)，再调用 printAllPathsToRoot(root)。

复杂度： 设置双亲指针为 O(n)；输出全部路径最坏为 O(nh)，递归栈为 O(h)。

校订注：原稿将“输出所有结点到根路径”的总时间直接标为 O(n)，忽略了路径输出量；在退化树中总输出长度可达 O(n²)。

6. 求结点 p、q 的最近公共祖先

链式存储

BiTree lowestCommonAncestor(BiTree root, BiTree p, BiTree q) {
    if (root == NULL || root == p || root == q)
        return root;

    BiTree left = lowestCommonAncestor(root->lchild, p, q);
    BiTree right = lowestCommonAncestor(root->rchild, p, q);

    if (left != NULL && right != NULL)
        return root;
    return left != NULL ? left : right;
}

复杂度： 时间 O(n)，递归栈空间 O(h)。假定 p、q 均存在于树中。

顺序存储（下标从 0 开始）

BiTree lowestCommonAncestorInArray(BiTree nodes[], int i, int j) {
    while (i != j) {
        if (i > j)
            i = (i - 1) / 2;
        else
            j = (j - 1) / 2;
    }
    return nodes[i];
}

复杂度： 时间 O(h)，额外空间 O(1)；对完全二叉树有 h=O(log n)。

7. 用层序遍历求二叉树高度

int treeHeightByLevelOrder(BiTree root) {
    if (root == NULL)
        return 0;

    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int height = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        while (front < levelEnd) {
            BiTree node = queue[front++];
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
        height++;
    }

    return height;
}

复杂度： 时间 O(n)，队列空间 O(n)。

校订注：原稿在 if (bt != NULL) 与函数末尾附近多出一个右花括号，且空树路径没有明确返回值；本版已整理。

8. 计算二叉树的带权路径长度 WPL（2014 年统考题）

假定叶子结点的 data 可解释为数值权重，根的深度为 0。

递归法

int weightedPathLength(BiTree root, int depth) {
    if (root == NULL)
        return 0;

    if (root->lchild == NULL && root->rchild == NULL)
        return root->data * depth;

    return weightedPathLength(root->lchild, depth + 1)
         + weightedPathLength(root->rchild, depth + 1);
}

调用方式：weightedPathLength(root, 0)。

层序遍历法

int weightedPathLengthByLevel(BiTree root) {
    if (root == NULL)
        return 0;

    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int depth = 0, wpl = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        while (front < levelEnd) {
            BiTree node = queue[front++];
            if (node->lchild == NULL && node->rchild == NULL)
                wpl += node->data * depth;
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
        depth++;
    }

    return wpl;
}

复杂度： 两种方法时间均为 O(n)；递归法栈空间 O(h)，层序法队列空间 O(n)。

9. 求二叉树的宽度

int maxTreeWidth(BiTree root) {
    if (root == NULL)
        return 0;

    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int maxWidth = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        int width = levelEnd - front;
        if (width > maxWidth)
            maxWidth = width;

        while (front < levelEnd) {
            BiTree node = queue[front++];
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
    }

    return maxWidth;
}

复杂度： 时间 O(n)，队列空间 O(n)。

递归法也可用 count[level] 统计每层结点数，遍历结束后取数组最大值；其递归栈为 O(h)，层计数数组为 O(h)。

10. 判断二叉树是否为满二叉树

这里“满二叉树”指高度为 h 时恰有 2^h-1 个结点的二叉树。

void countNodesAndHeight(BiTree root, int depth,
                         int *nodeCount, int *height) {
    if (root == NULL)
        return;

    (*nodeCount)++;
    if (depth > *height)
        *height = depth;

    countNodesAndHeight(root->lchild, depth + 1, nodeCount, height);
    countNodesAndHeight(root->rchild, depth + 1, nodeCount, height);
}

bool isFullBinaryTree(BiTree root) {
    int nodeCount = 0;
    int height = 0;
    countNodesAndHeight(root, 1, &nodeCount, &height);

    long long expected = (1LL << height) - 1;
    return nodeCount == expected;
}

复杂度： 时间 O(n)，递归栈空间 O(h)。

11. 满二叉树先序序列与后序序列互转

满二叉树的左右子树结点数相等，因此可以直接按区间长度折半。

void preorderToPostorder(char pre[], int preL, int preR,
                         char post[], int postL, int postR) {
    if (preL > preR)
        return;

    post[postR] = pre[preL];
    if (preL == preR)
        return;

    int subtreeSize = (preR - preL) / 2;
    preorderToPostorder(pre, preL + 1, preL + subtreeSize,
                        post, postL, postL + subtreeSize - 1);
    preorderToPostorder(pre, preL + subtreeSize + 1, preR,
                        post, postL + subtreeSize, postR - 1);
}

void postorderToPreorder(char post[], int postL, int postR,
                         char pre[], int preL, int preR) {
    if (postL > postR)
        return;

    pre[preL] = post[postR];
    if (postL == postR)
        return;

    int subtreeSize = (postR - postL) / 2;
    postorderToPreorder(post, postL, postL + subtreeSize - 1,
                        pre, preL + 1, preL + subtreeSize);
    postorderToPreorder(post, postL + subtreeSize, postR - 1,
                        pre, preL + subtreeSize + 1, preR);
}

复杂度： 时间 O(n)，递归栈空间 O(h)。

12. 根据遍历序列建立二叉链表

先序序列 + 中序序列

BiTree buildFromPreIn(char pre[], int preL, int preR,
                      char in[], int inL, int inR) {
    if (preL > preR || inL > inR)
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = pre[preL];

    int split = inL;
    while (split <= inR && in[split] != root->data)
        split++;

    int leftSize = split - inL;
    root->lchild = buildFromPreIn(pre, preL + 1, preL + leftSize,
                                  in, inL, split - 1);
    root->rchild = buildFromPreIn(pre, preL + leftSize + 1, preR,
                                  in, split + 1, inR);
    return root;
}

后序序列 + 中序序列

BiTree buildFromPostIn(char post[], int postL, int postR,
                       char in[], int inL, int inR) {
    if (postL > postR || inL > inR)
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = post[postR];

    int split = inL;
    while (split <= inR && in[split] != root->data)
        split++;

    int leftSize = split - inL;
    root->lchild = buildFromPostIn(post, postL, postL + leftSize - 1,
                                   in, inL, split - 1);
    root->rchild = buildFromPostIn(post, postL + leftSize, postR - 1,
                                   in, split + 1, inR);
    return root;
}

复杂度： 上述直接线性查找中序根位置的写法，最坏时间 O(n²)，递归栈 O(h)；若预先建立“元素值到中序下标”的哈希映射，可将时间降为 O(n)。

13. 二叉链表与顺序存储数组互转

二叉链表转数组

void treeToArray(BiTree root, char A[], int index, int capacity) {
    if (root == NULL || index >= capacity)
        return;

    A[index] = root->data;
    treeToArray(root->lchild, A, 2 * index + 1, capacity);
    treeToArray(root->rchild, A, 2 * index + 2, capacity);
}

调用前应将数组所有位置初始化为表示空结点的 '#'。

数组转二叉链表

BiTree arrayToTree(char A[], int index, int n) {
    if (index >= n || A[index] == '#')
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = A[index];
    root->lchild = arrayToTree(A, 2 * index + 1, n);
    root->rchild = arrayToTree(A, 2 * index + 2, n);
    return root;
}

复杂度： 对有效数组范围进行递归访问，时间 O(n)，递归栈空间 O(h)；稀疏且很深的树使用顺序存储可能浪费大量数组空间。

14. 统计顺序存储二叉树的叶子结点数

int countArrayLeaves(char A[], int index, int n) {
    if (index >= n || A[index] == '#')
        return 0;

    int left = 2 * index + 1;
    int right = 2 * index + 2;
    bool leftEmpty = left >= n || A[left] == '#';
    bool rightEmpty = right >= n || A[right] == '#';

    if (leftEmpty && rightEmpty)
        return 1;

    return countArrayLeaves(A, left, n)
         + countArrayLeaves(A, right, n);
}

复杂度： 时间 O(n)，递归栈空间 O(h)。

---