二叉树遍历方法

以下为二叉树结构示例

前序访问实现：

void traversePreOrder(TreeNode* node) {
    if (node == NULL) {
        printf("N ");
        return;
    }
    printf("%d ", node->value);
    traversePreOrder(node->left);
    traversePreOrder(node->right);
}

中序访问实现：

void traverseInOrder(TreeNode* node) {
    if (node == NULL) {
        printf("N ");
        return;
    }
    traverseInOrder(node->left);
    printf("%d ", node->value);
    traverseInOrder(node->right);
}

后序访问实现：

void traversePostOrder(TreeNode* node) {
    if (node == NULL) {
        printf("N ");
        return;
    }
    traversePostOrder(node->left);
    traversePostOrder(node->right);
    printf("%d ", node->value);
}

层序访问需要借助队列结构：

void levelTraverse(TreeNode* treeRoot) {
    Queue queue;
    queueInit(&queue);
    if (treeRoot) {
        queuePush(&queue, treeRoot);
    }
    while (!queueIsEmpty(&queue)) {
        TreeNode* front = queueFront(&queue);
        queuePop(&queue);
        printf("%d ", front->value);
        if (front->left) queuePush(&queue, front->left);
        if (front->right) queuePush(&queue, front->right);
    }
}

节点数量统计：

int countNodes(TreeNode* node) {
    if (node == NULL) return 0;
    return countNodes(node->left) + countNodes(node->right) + 1;
}

叶子节点计算：

int countLeaves(TreeNode* node) {
    if (node == NULL) return 0;
    if (node->left == NULL && node->right == NULL) return 1;
    return countLeaves(node->left) + countLeaves(node->right);
}

第k层节点统计：

int countLevelNodes(TreeNode* node, int level) {
    assert(level > 0);
    if (node == NULL) return 0;
    if (level == 1) return 1;
    return countLevelNodes(node->left, level-1) + countLevelNodes(node->right, level-1);
}

值查找功能：

TreeNode* findNode(TreeNode* node, int target) {
    if (node == NULL) return NULL;
    if (node->value == target) return node;
    TreeNode* leftResult = findNode(node->left, target);
    if (leftResult != NULL) return leftResult;
    return findNode(node->right, target);
}

完全二叉树判断：

int isCompleteTree(TreeNode* root) {
Queue queue;
queueInit(&queue);
if (root) queuePush(&queue, root);

while (!queueIsEmpty(&queue)) {
TreeNode* current = queueFront(&queue);
queuePop(&queue);

if (current == NULL) break;
queuePush(&queue, current->left);
queuePush(&queue, current->right);
}

while (!queueIsEmpty(&queue)) {
if (queueFront(&queue) != NULL) return 0;
}
return 1;
}