编辑代码

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

// 定义二叉树节点
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode *createNode(int data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入数据
TreeNode *insert(TreeNode *root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

// 中序遍历
void inorderTraversal(TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 计算叶子节点数量
void LeafSize1(TreeNode* root, int* size) {
    if (!root)
        return;
    if (!root->left && !root->right) {
        (*size)++;
    } else {
        LeafSize1(root->left, size);
        LeafSize1(root->right, size);
    }
}


int doubleBranchCount(TreeNode* root){
    int num1,num2;
    if(root==NULL){
        return 0;
    }else if(root->left == NULL || root->right == NULL){
        return 0;
    }else{
        num1 = doubleBranchCount(root->left);
        num2 = doubleBranchCount(root->right);
        return (num1+num2+1);
    }
}

void findMin(TreeNode* root, int *m) {
    if(root == NULL) return;
    if(root->data < *m) {
        (*m) = root->data;
    }

    findMin(root->left, m);
    findMin(root->right, m);
}


void sum(TreeNode* root, int *count){
    if(root == NULL) return;
    *count+=root->data;
    sum(root->left, count);
    sum(root->right, count);
}


void min(TreeNode *root){
    int min = root->data;
    if(root !=NULL){
        findMin(root, &min);
        printf("二叉树的最小值为: %d", min);
    }
} 

// 递归计算二叉树高度
int depth(TreeNode* root){
    int high1, high2;
    if(root==NULL) return 0;
    else if(root->left != NULL || root->right != NULL){
        high1 = depth(root->left);
        high2 = depth(root->right);
        return (high2 > high1 ? high2 : high1) + 1;
    }
}


// 查找x在二叉树中的层次
void findXLevel(TreeNode* root, int x, int* level) {
    if(root == NULL) return;
    (*level)++;
    if(root->data == x){
        printf("元素%d的层次为: %d", x, *level);
        return;
    }
    findXLevel(root->left, x, level);
    findXLevel(root->right, x, level);
    (*level)--;
}



// 查找x在二叉树中的层次
void findXLevel1(TreeNode* root, int x, int level) {
    if(root == NULL) return;
    if(root->data == x){
        printf("\n元素%d的层次为: %d", x, level);
        return;
    }
    findXLevel1(root->left, x, level+1);
    findXLevel1(root->right, x, level+1);
}


void findPre(TreeNode* root, int p, int *count, int *val) {
    if(root == NULL) return;
    (*count)++;
    if(*count == p) {
        *val = root->data;
        return;
    }
    findPre(root->left, p, count, val);
    findPre(root->right, p, count, val);

}



// 判断是否为二叉排序树
void judgeSort(TreeNode* root, TreeNode* pre, int* flag) {
    if(root == NULL) return;
    judgeSort(root->left, pre, flag);
    if(pre == NULL){
        pre = root;
    }else if(pre->data < root->data){
        pre = root;
    }else{
        *flag = 1;
    }
    judgeSort(root->right, pre, flag);
}


// 判断是否为平衡二叉排序树
int judgeBalance(TreeNode* root, int* flag) {
    int high1, high2;
    if(root == NULL) return 0 ;
    else if(root->left == NULL && root->right == NULL) {
        return 1; 
    }else {
        high1 = judgeBalance(root->left, flag);
        high2 = judgeBalance(root->right, flag);
        if(high1 - high2 > 1 || high1 - high2 < -1){
            *flag = 1;
        }
        return high1 > high2 ? high1 + 1: high2 + 1;
    }
}



// 输出平衡二叉排序树的平衡因子
int balanceFactor(TreeNode* root) {
    int high1, high2;
    if(root == NULL) return 0 ;
    else if(root->left == NULL && root->right == NULL) {
        return 1; 
    }else {
        high1 = balanceFactor(root->left);
        high2 = balanceFactor(root->right);
        printf("\n元素%d的平衡因子: %d", root->data, high1-high2);
        return high1 > high2 ? high1 + 1: high2 + 1;
    }
}



int main() {
    TreeNode *root = NULL;

    // 插入10条数据
    int data[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35};
    for (int i = 0; i < 10; i++) {
        root = insert(root, data[i]);
    }

    // 中序遍历验证插入结果
    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    int count = 0;
    LeafSize1(root, &count);
    printf("Number of leaf nodes: %d\n", count);

    int doubleNode = doubleBranchCount(root);
    printf("双分支结点个数: %d\n", doubleNode);
    sum(root, &count);
    printf("二叉树结点值和为: %d\n", count);
    min(root);


    printf("\n递归二叉树的深度为: %d\n", depth(root));

    int l = 0;
    int z = 1;
    findXLevel(root, 10, &l);
    findXLevel1(root, 10, 1);

    count = 0;
    int val = 0;
    int p = 5;
    findPre(root, p, &count, &val);
    printf("\n先序遍历第%d元素为: %d", p, val);

    TreeNode* pre = NULL;
    int flag = 0;
    judgeSort(root, pre, &flag);
    if(flag == 0) {
        printf("\n二叉排序树合法");
    }else if(flag == 1){
        printf("\n二叉排序树不合法");
    }

    flag = 0;
    judgeBalance(root, &flag);
    if(flag == 0) {
        printf("\n平衡二叉排序树合法");
    }else if(flag == 1){
        printf("\n平衡二叉排序树不合法");
    }


    balanceFactor(root);
    return 0;
}