实现创建二叉树并求高度的算法分析

创建二叉树的算法可以采用递归的方式，具体步骤如下：

1. 创建一个二叉树结点的数据结构，包括数据域和左右子树指针。
2. 定义一个函数 createBinaryTree()，接收一个数组和数组长度作为参数。
3. 在 createBinaryTree() 函数中，首先判断数组长度是否为 0，如果是，则返回空指针。
4. 如果数组长度不为 0，取数组中间的元素作为根节点，创建一个二叉树结点。
5. 递归调用 createBinaryTree() 函数，传入数组左半部分作为左子树的元素，传入数组右半部分作为右子树的元素。
6. 将左右子树的返回值分别赋给根节点的左右子树指针。
7. 返回根节点。

求二叉树高度的算法可以采用递归的方式，具体步骤如下：

1. 定义一个函数 getHeight()，接收一个二叉树结点指针作为参数。
2. 在 getHeight() 函数中，首先判断二叉树结点指针是否为空，如果是，则返回 0。
3. 如果二叉树结点指针不为空，递归调用 getHeight() 函数，分别计算左右子树的高度。
4. 取左右子树高度的最大值，加上 1（当前结点的高度），作为当前结点的高度，返回。

时间复杂度：

创建二叉树的时间复杂度为 O(n)，其中 n 为数组长度。

求二叉树高度的时间复杂度为 O(n)，其中 n 为二叉树结点数。

空间复杂度：

创建二叉树的空间复杂度为 O(n)，其中 n 为数组长度。

求二叉树高度的空间复杂度为 O(h)，其中 h 为二叉树高度。

相关问题

1．完成的功能包括如下几点： ①编程实现建立一棵二叉树，然后对其进行先序、中序和后序遍历。 分析：将要输入的二叉树按照其对应的完全二叉树的顺序输入，若当前位置不存在结点则输入@ ②显示二叉树 ③求二叉树的高度及二叉树的叶子个数等等 ④在主函数中设计一个简单的菜单，分别调试上述算法 C语言数据结构主函数代码

以下是一个简单的C语言数据结构程序，实现了上述要求的功能：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    char val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 先序遍历
void preorder(struct TreeNode *root) {
    if (root) {
        printf("%c ", root->val);
        preorder(root->left);
        preorder(root->right);
    }
}

// 中序遍历
void inorder(struct TreeNode *root) {
    if (root) {
        inorder(root->left);
        printf("%c ", root->val);
        inorder(root->right);
    }
}

// 后序遍历
void postorder(struct TreeNode *root) {
    if (root) {
        postorder(root->left);
        postorder(root->right);
        printf("%c ", root->val);
    }
}

// 创建二叉树
struct TreeNode* createTree() {
    struct TreeNode *root;
    char val;
    scanf("%c", &val);
    if (val == '@') {
        root = NULL;
    } else {
        root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val = val;
        root->left = createTree();
        root->right = createTree();
    }
    return root;
}

// 显示二叉树
void printTree(struct TreeNode *root, int depth) {
    if (root) {
        int i;
        for (i = 0; i < depth; i++) {
            printf("  ");
        }
        printf("%c\n", root->val);
        printTree(root->left, depth + 1);
        printTree(root->right, depth + 1);
    }
}

// 计算二叉树高度
int getHeight(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
}

// 计算二叉树叶子节点个数
int getLeafCount(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL) {
        return 1;
    } else {
        return getLeafCount(root->left) + getLeafCount(root->right);
    }
}

int main() {
    struct TreeNode *root;
    int choice;

    printf("请输入二叉树的结点，空结点用@表示：\n");
    root = createTree();

    while (1) {
        printf("\n");
        printf("1. 先序遍历\n");
        printf("2. 中序遍历\n");
        printf("3. 后序遍历\n");
        printf("4. 显示二叉树\n");
        printf("5. 计算二叉树高度\n");
        printf("6. 计算二叉树叶子节点个数\n");
        printf("7. 退出\n");
        printf("请输入您的选择：");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("先序遍历结果为：");
                preorder(root);
                printf("\n");
                break;
            case 2:
                printf("中序遍历结果为：");
                inorder(root);
                printf("\n");
                break;
            case 3:
                printf("后序遍历结果为：");
                postorder(root);
                printf("\n");
                break;
            case 4:
                printf("二叉树如下：\n");
                printTree(root, 0);
                break;
            case 5:
                printf("二叉树高度为：%d\n", getHeight(root));
                break;
            case 6:
                printf("二叉树叶子节点个数为：%d\n", getLeafCount(root));
                break;
            case 7:
                exit(0);
            default:
                printf("输入有误，请重新输入。\n");
                break;
        }
    }

    return 0;
}

二叉树基本操作重要算法的实现代码c语言和算法的时间复杂度和空间复杂度

二叉树基本操作包括：创建二叉树、遍历二叉树、查找节点、插入节点、删除节点等。下面是这些操作的实现代码和时间/空间复杂度分析。

1. 创建二叉树

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) { // -1表示该节点为空
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(n)，即为递归栈的深度，最坏情况下为树的高度，即n。

2. 遍历二叉树

（1）前序遍历

void preorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

（2）中序遍历

void inorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

（3）后序遍历

void postorder(struct TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

3. 查找节点

struct TreeNode* find(struct TreeNode *root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    struct TreeNode *left = find(root->left, val);
    struct TreeNode *right = find(root->right, val);
    return left == NULL ? right : left;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

4. 插入节点

void insert(struct TreeNode *root, int val) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL) {
        root->left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->left->val = val;
        root->left->left = NULL;
        root->left->right = NULL;
        return;
    }
    if (root->right == NULL) {
        root->right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->right->val = val;
        root->right->left = NULL;
        root->right->right = NULL;
        return;
    }
    insert(root->left, val);
    insert(root->right, val);
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。

5. 删除节点

struct TreeNode* delete(struct TreeNode *root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (root->val == val) {
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        if (root->left == NULL) {
            struct TreeNode *right = root->right;
            free(root);
            return right;
        }
        if (root->right == NULL) {
            struct TreeNode *left = root->left;
            free(root);
            return left;
        }
        struct TreeNode *min = root->right;
        while (min->left != NULL) {
            min = min->left;
        }
        root->val = min->val;
        root->right = delete(root->right, min->val);
    } else if (root->val > val) {
        root->left = delete(root->left, val);
    } else {
        root->right = delete(root->right, val);
    }
    return root;
}

时间复杂度：O(n)，n为二叉树的节点数，因为要遍历每个节点。

空间复杂度：O(h)，h为二叉树的高度，最坏情况下为n。