EB6-输出二叉树先序遍历序列中第k个结点的值¶

代码实现¶

C
/**
 * 输出二叉树先序遍历序列中第k个结点的值（修正版）
 * @param p 当前遍历的二叉树结点
 * @param k 目标结点的位置（第几个）
 * @param n 计数器指针，记录当前已访问的结点数
 */
void printKthNodeInPreorder(BiTree p, int k, int* n) {
    // 如果当前结点不为空，则继续遍历
    if (p != NULL) {
        // 访问当前结点，计数器加1
        ++(*n);

        // 如果当前访问的是第k个结点，则输出其值
        if (*n == k) {
            printf("%c", p->data);  // 输出第k个结点的值
        }

        // 递归遍历左子树
        printKthNodeInPreorder(p->lchild, k, n);

        // 递归遍历右子树
        printKthNodeInPreorder(p->rchild, k, n);
    }
}

代码执行流程图解¶

Text Only

       A(1)
      /     \
    B(2)    C(5)
   /   \      \
  D(3) E(4)   F(6)
 /
G(7)

先序遍历顺序：A(1) → B(2) → D(3) → G(4) → E(5) → C(6) → F(7)
括号内数字表示访问顺序

查找第4个结点：
1. 访问A，n=1，1≠4
2. 访问B，n=2，2≠4
3. 访问D，n=3，3≠4
4. 访问G，n=4，4==4，输出'G'
5. 后续结点不再检查（但函数仍会继续执行）

优化版本：找到即返回¶

C
/**
 * 输出二叉树先序遍历序列中第k个结点的值（优化版）
 * 找到后立即返回，避免不必要的遍历
 * @param p 当前遍历的二叉树结点
 * @param k 目标结点的位置（第几个）
 * @param n 计数器指针，记录当前已访问的结点数
 */
void printKthNodeInPreorderOptimized(BiTree p, int k, int* n) {
    // 如果当前结点为空或已经找到目标结点，则返回
    if (p == NULL || *n >= k) {
        return;
    }

    // 访问当前结点，计数器加1
    ++(*n);

    // 如果当前访问的是第k个结点，则输出其值
    if (*n == k) {
        printf("%c", p->data);  // 输出第k个结点的值
        return;  // 找到后立即返回
    }

    // 递归遍历左子树
    printKthNodeInPreorderOptimized(p->lchild, k, n);

    // 递归遍历右子树（只有在左子树未找到的情况下才需要）
    if (*n < k) {
        printKthNodeInPreorderOptimized(p->rchild, k, n);
    }
}

复杂度分析¶

时间复杂度：O(N)¶

最坏情况：第k个结点是最后一个结点，需要遍历所有N个结点
最好情况：第k个结点是第一个结点，原版本仍需O(N)，优化版本为O(1)
平均情况：需要遍历k个结点，但最坏情况主导，仍为O(N)

空间复杂度：O(N)¶

递归调用栈：
最坏情况下（完全不平衡的二叉树），递归深度为N，空间复杂度为O(N)
最好情况下（完全平衡的二叉树），递归深度为logN，空间复杂度为O(logN)
综合考虑，空间复杂度为O(N)

相关知识点延伸¶

1. 三种遍历方式的第k个结点查找¶

C
/**
 * 中序遍历第k个结点查找
 */
void printKthNodeInInorder(BiTree p, int k, int* n) {
    if (p == NULL || *n >= k) return;

    // 先遍历左子树
    printKthNodeInInorder(p->lchild, k, n);

    // 访问当前结点
    if (*n < k) {
        ++(*n);
        if (*n == k) {
            printf("%c", p->data);
        }
        // 再遍历右子树
        printKthNodeInInorder(p->rchild, k, n);
    }
}

C
/**
 * 后序遍历第k个结点查找
 */
void printKthNodeInPostorder(BiTree p, int k, int* n) {
    if (p == NULL || *n >= k) return;

    // 先遍历左子树
    printKthNodeInPostorder(p->lchild, k, n);

    // 再遍历右子树
    printKthNodeInPostorder(p->rchild, k, n);

    // 最后访问当前结点
    if (*n < k) {
        ++(*n);
        if (*n == k) {
            printf("%c", p->data);
        }
    }
}

2. 迭代实现方式¶

C
/**
 * 迭代方式查找先序遍历第k个结点
 */
void printKthNodeInPreorderIterative(BiTree root, int k) {
    if (root == NULL || k <= 0) return;

    Stack s;
    initStack(&s);
    push(&s, root);

    int count = 0;
    while (!isEmpty(&s) && count < k) {
        BiTree p = pop(&s);
        count++;

        if (count == k) {
            printf("%c", p->data);
            return;
        }

        // 先压入右子树，再压入左子树（栈的特性）
        if (p->rchild != NULL) push(&s, p->rchild);
        if (p->lchild != NULL) push(&s, p->lchild);
    }
}

3. 返回结点指针的版本¶

C
/**
 * 返回先序遍历第k个结点的指针
 * @param p 当前遍历的二叉树结点
 * @param k 目标结点的位置
 * @param n 计数器指针
 * @return 第k个结点的指针，未找到返回NULL
 */
BiTree getKthNodeInPreorder(BiTree p, int k, int* n) {
    if (p == NULL || *n >= k) {
        return NULL;
    }

    ++(*n);
    if (*n == k) {
        return p;
    }

    BiTree leftResult = getKthNodeInPreorder(p->lchild, k, n);
    if (leftResult != NULL) {
        return leftResult;
    }

    return getKthNodeInPreorder(p->rchild, k, n);
}

使用示例¶

C
// 调用示例
int main() {
    BiTree root = createTree();  // 假设已有创建树的函数
    int count = 0;
    int k = 3;

    printf("第%d个结点的值是: ", k);
    printKthNodeInPreorder(root, k, &count);
    printf("\n");

    return 0;
}

关键要点总结¶

计数器传递：使用指针int* n来在递归调用间共享计数状态
遍历顺序：严格按照先序遍历（根-左-右）的顺序进行计数
边界处理：需要处理k超出结点总数的情况
优化策略：可以通过提前终止来提高效率
指针理解：理解指针参数在递归中的作用机制

这个算法体现了递归遍历与计数结合的典型应用场景，是理解树遍历和递归调用的重要实例。在实际应用中，根据具体需求可以选择不同的优化策略。