完全二叉树的高度C语言

完全二叉树的高度可以通过递归的方式来计算。下面是一个用C语言实现的计算完全二叉树高度的函数：

typedef struct tree_t {
    tree_datatype data; // 数据域
    struct tree_t *lchild; // 指向左子树的结构体指针
    struct tree_t *rchild; // 指向右子树的结构体指针
} bitree_t;

int getHeight(bitree_t *root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = getHeight(root->lchild);
        int rightHeight = getHeight(root->rchild);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

在上面的代码中，`getHeight`函数使用递归的方式计算完全二叉树的高度。如果根节点为空，则返回0；否则，分别计算左子树和右子树的高度，并返回较大的那个高度加1。

相关问题

实验内容 1、以二叉链表作存储结构，设计求二叉树高度的算法。 2、一棵 n 个结点的完全二叉树用向量作存储结构，用非递归算法实现对该二叉树进行前 序遍历。 用c语言输出代码

在C语言中，我们可以采用递归或迭代的方式来实现这两个实验内容。

1. **求二叉树高度**（非递归方式）：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int height(TreeNode* root) {
    // 如果根节点为空，高度为0
    if (root == NULL) return 0;
    
    // 左右子树的高度加一作为当前的高度，取较大值
    int left_height = height(root->left);
    int right_height = height(root->right);
    return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

int main() {
    // 创建示例二叉树并计算其高度
    TreeNode* tree = // 初始化二叉树...
    printf("The height of the binary tree is: %d\n", height(tree));
    return 0;
}

2. **完全二叉树前序遍历（非递归方式，用数组表示）**：

#include <stdio.h>
#define MAX_TREE_SIZE 100 // 你可以根据需要调整

void preorderTraversal(int arr[], int n, int index=0) {
    for (int i = 0; i < n; ++i) {
        printf("%d ", arr[index]); // 遍历元素
        if (index * 2 + 1 < n) { // 如果左孩子存在，继续遍历
            preorderTraversal(arr, n, index * 2 + 1);
        }
        if (index * 2 + 2 < n && arr[index * 2 + 2] != -1) { // 如果右孩子存在，继续遍历
            preorderTraversal(arr, n, index * 2 + 2);
        } else { // 否则结束当前层
            break;
        }
    }
}

int main() {
    // 初始化完全二叉树到数组arr中...
    int arr[MAX_TREE_SIZE];
    // 填充数组并调用前序遍历
    preorderTraversal(arr, n); // n为二叉树的实际结点数
    return 0;
}

c语言求完全二叉树节点个数

在C语言中，求完全二叉树节点个数可以采用以下方法：

1. 定义一个结构体表示二叉树节点，包含左右子节点指针和节点值等信息。

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

2. 定义一个函数countNodes，用于计算完全二叉树节点个数，函数参数为指向根节点的指针。

int countNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = 0, rightHeight = 0;
    struct TreeNode *left = root, *right = root;
    while (left) {
        leftHeight++;
        left = left->left;
    }
    while (right) {
        rightHeight++;
        right = right->right;
    }
    if (leftHeight == rightHeight) {
        return (1 << leftHeight) - 1;
    } else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}

3. 在countNodes函数中，首先判断根节点是否为空，如果为空则返回0。否则，分别计算左右子树的高度leftHeight和rightHeight。如果leftHeight等于rightHeight，则说明该二叉树是满二叉树，节点个数为(2^leftHeight)-1，直接返回。否则，递归计算左右子树的节点个数，加上根节点1即可。

注意：这里使用了位运算，1<<n等价于2^n。