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

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

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.定义二叉链存储结构。 2.建立二叉链表存储的二叉树。 3.实现二叉树的先序遍历、中序遍历和后序遍历。 4.实现求二叉树的高度、求结点双亲、统计叶子结点数目的操作。编写测试主函数，测试所实现的操作，并进行分析用c语言编写一个程序 能输入字母

1. 定义二叉链存储结构通常涉及创建两个指针变量，一个用于存储当前节点的数据（比如整型或字符），另一个称为`left`和`right`，分别指向左子节点和右子节点，如果子节点不存在，则指针可以为`NULL`。结构体定义大致如下：

typedef struct Node {
    char data; // 存储数据
    struct Node* left;
    struct Node* right;
} TreeNode;

2. 构建二叉链表存储的二叉树，通过递归或迭代的方式插入节点，每个新节点会作为父节点的子节点连接到原有的二叉链上。

3. 实现二叉树的遍历有三种基本方法：
- 先序遍历（根-左-右）：

     void preOrderTraversal(TreeNode* node) {
         if (node != NULL) {
             printf("%c ", node->data);
             preOrderTraversal(node->left);
             preOrderTraversal(node->right);
         }
     }

- 中序遍历（左-根-右）：

     void inOrderTraversal(TreeNode* node) {
         if (node != NULL) {
             inOrderTraversal(node->left);
             printf("%c ", node->data);
             inOrderTraversal(node->right);
         }
     }

- 后序遍历（左-右-根）：

     void postOrderTraversal(TreeNode* node) {
         if (node != NULL) {
             postOrderTraversal(node->left);
             postOrderTraversal(node->right);
             printf("%c ", node->data);
         }
     }

4. 求二叉树高度、结点双亲和叶节点数目：
- 高度（递归法）：

     int height(TreeNode* node) {
         return (node == NULL) ? 0 : 1 + max(height(node->left), height(node->right));
     }

- 双亲查找（非递归，借助栈）：

     TreeNode* findParent(TreeNode* node, TreeNode* root) {
         // ... 算法省略 ...
     }

- 统计叶子结点：

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

5. 测试主函数示例：

   int main() {
       // 初始化二叉树
       TreeNode* tree = createBinaryTree(); // 假设createBinaryTree已定义

       // 遍历并打印结果
       printf("Preorder Traversal: ");
       preOrderTraversal(tree);
       printf("\nInorder Traversal: ");
       inOrderTraversal(tree);
       printf("\nPostorder Traversal: ");
       postOrderTraversal(tree);

       // 计算高度、双亲等
       int heightResult = height(tree);
       printf("\nHeight of the tree is: %d\n", heightResult);
       TreeNode* parent = findParent(root, someNode); // 假设someNode是已知节点
       // ...

       return 0;
   }

关于输入字母的问题，这个例子假设已经处理了用户输入的字节，如果需要从用户输入读取字母构建二叉树，你需要添加相应的输入部分，例如`scanf`函数获取字符，并在创建节点时使用它。

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;
}