EB4-二叉树最大值结点查找

代码实现

/**
 * 在二叉树中查找值最大的结点
 * @param p 当前遍历的二叉树结点
 * @param m 指向最大值结点的指针的地址
 */
void findMaxNode(BiTree p, BiTree *m) {
    // 如果当前结点不为空，则继续遍历
    if (p != NULL) {
        // 如果m指向的结点为空，或者当前结点的值大于m指向结点的值
        // 则更新m指向当前结点# 二叉树最大值结点查找函数分析
        if ((*m) == NULL || p->data > (*m)->data) {
            *m = p;  // 更新最大值结点指针
        }

        // 递归遍历左子树
        findMaxNode(p->lchild, m);

        // 递归遍历右子树
        findMaxNode(p->rchild, m);
    }
}

代码执行流程图解

       5
      / \
     3   8
    / \   \
   2   4   9
  /
 1

执行过程：
1. 访问根节点5，m=NULL，更新m指向5
2. 递归访问左子树(3)
   - 访问3，3>5? 否，m仍指向5
   - 递归访问2，2>5? 否，m仍指向5
   - 递归访问1，1>5? 否，m仍指向5
3. 递归访问右子树(8)
   - 访问8，8>5? 是，更新m指向8
   - 递归访问9，9>8? 是，更新m指向9
最终：m指向值为9的结点

复杂度分析

时间复杂度：O(N)

• 分析过程：
• 函数需要遍历二叉树的每一个结点 exactly 一次
• 对于每个结点，只进行常数时间的比较操作
• 设二叉树有N个结点，则总时间复杂度为O(N)

空间复杂度：O(N)

• 分析过程：
• 主要消耗在递归调用栈的空间
• 最坏情况下（完全不平衡的二叉树，退化为链表），递归深度为N，空间复杂度为O(N)
• 最好情况下（完全平衡的二叉树），递归深度为logN，空间复杂度为O(logN)
• 综合考虑，空间复杂度为O(N)

相关知识点延伸

1. 二叉树遍历方式

// 前序遍历（根-左-右）- 本题使用的方式
void preorder(BiTree p) {
    if (p != NULL) {
        visit(p);           // 处理当前结点
        preorder(p->lchild); // 遍历左子树
        preorder(p->rchild); // 遍历右子树
    }
}

// 中序遍历（左-根-右）
void inorder(BiTree p) {
    if (p != NULL) {
        inorder(p->lchild);
        visit(p);
        inorder(p->rchild);
    }
}

// 后序遍历（左-右-根）
void postorder(BiTree p) {
    if (p != NULL) {
        postorder(p->lchild);
        postorder(p->rchild);
        visit(p);
    }
}

2. 迭代实现方式（使用栈）

/**
 * 迭代方式查找二叉树最大值结点
 */
void findMaxNodeIterative(BiTree root, BiTree *m) {
    if (root == NULL) return;

    Stack s;  // 假设有栈结构
    initStack(&s);
    push(&s, root);
    *m = root;

    while (!isEmpty(&s)) {
        BiTree p = pop(&s);

        // 更新最大值结点
        if (p->data > (*m)->data) {
            *m = p;
        }

        // 将子结点入栈
        if (p->rchild != NULL) push(&s, p->rchild);
        if (p->lchild != NULL) push(&s, p->lchild);
    }
}

3. 层序遍历实现（使用队列）

/**
 * 层序遍历方式查找最大值结点
 */
void findMaxNodeLevelOrder(BiTree root, BiTree *m) {
    if (root == NULL) return;

    Queue q;  // 假设有队列结构
    initQueue(&q);
    enqueue(&q, root);
    *m = root;

    while (!isEmpty(&q)) {
        BiTree p = dequeue(&q);

        // 更新最大值结点
        if (p->data > (*m)->data) {
            *m = p;
        }

        // 将子结点入队
        if (p->lchild != NULL) enqueue(&q, p->lchild);
        if (p->rchild != NULL) enqueue(&q, p->rchild);
    }
}

关键要点总结

1. 指针的指针使用：BiTree *m 用于在递归过程中保持对最大结点引用的更新
2. 递归遍历：采用前序遍历确保每个结点都被访问到
3. 比较逻辑：需要处理初始情况（*m == NULL）和一般情况
4. 完整遍历：必须访问所有结点才能确定最大值

这个算法虽然简单，但体现了二叉树遍历的基本思想和指针操作的技巧，在数据结构算法中具有代表性。