当前位置： 首页 > article >正文

算法设计题（树和二叉树）

article 2024/11/5 1:04:41

算法设计题以二又链表为存储结构,假设二叉树 的存储结构定义如下

typedef struct BiNode {
    char data;  // 数据域
    struct BiNode *lChild;  // 左孩子指针
    struct BiNode *rChild;  // 右孩子指针
} BiNode, *BiTree;

1.求二叉树中的度数为2的结点

2.求二叉树中值最大的元素。

3.将二叉树各结点存储到一维数组中。

4.按先序输出二叉树中各结点，并输出它们所在的层次(根结点为第1层）。

5.编写算法,判断二叉树7是否是完全二叉树。

6.交换二又树各结点的左右子树。

7.写出在二叉树中查找值为的结点在树中层数的算法。

8.设计算法计算给定二叉树中单孩子结点的数目。

9.设计算法，将二叉树的所有叶子结点，按从左到右的顺序连成一个单链表，得 单链表用rChild域链接。

为了更好地理解上述算法，我们将通过一个具体的二叉树案例来演示每个算法的执行，并提供可以运行的代码。假设我们有如下二叉树结构：

        A
       / \
      B   C
     / \   \
    D   E   F

这个二叉树的根节点是 A，它有两个孩子 B 和 C，其中 B 有两个孩子 D 和 E，C 有一个孩子 F。

1. 求二叉树中的度数为2的结点

思路：

一、函数countDegreeTwoNodes的思路

  1. 首先判断传入的根节点是否为空，如果为空则直接返回 0，表示没有度为 2 的节点。
  2. 接着检查当前节点是否度为 2，即判断当前节点是否同时拥有左子树和右子树。如果是，则将计数器count置为 1；如果不是，则置为 0。
  3. 然后通过递归调用分别计算当前节点的左子树和右子树中度为 2 的节点个数，并将结果累加到count上。
  4. 最后返回count，即当前子树中度为 2 的节点总数。

二、main函数的思路

  1. 创建一个二叉树，手动初始化各个节点的值和指针关系。
  2. 调用countDegreeTwoNodes函数计算二叉树中度为 2 的节点个数。
  3. 将结果打印输出。

代码：

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

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

// 计算二叉树中度为 2 的节点个数的函数
int countDegreeTwoNodes(TreeNode *root) {
    // 如果根节点为空，返回 0
    if (!root) return 0;
    // 判断当前节点是否度为 2（即有左子树和右子树），如果是，count 置为 1，否则置为 0
    int count = (root->left && root->right)? 1 : 0;
    // 递归计算左子树中度为 2 的节点个数，并累加到 count
    count += countDegreeTwoNodes(root->left);
    // 递归计算右子树中度为 2 的节点个数，并累加到 count
    count += countDegreeTwoNodes(root->right);
    // 返回最终的度为 2 的节点个数
    return count;
}

int main() {
    // 创建二叉树的根节点
    TreeNode *root = &(TreeNode){'A', NULL, NULL};
    // 创建根节点的左子节点
    root->left = &(TreeNode){'B', NULL, NULL};
    // 创建根节点的右子节点
    root->right = &(TreeNode){'C', NULL, NULL};
    // 创建根节点左子节点的左子节点
    root->left->left = &(TreeNode){'D', NULL, NULL};
    // 创建根节点左子节点的右子节点
    root->left->right = &(TreeNode){'E', NULL, NULL};
    // 创建根节点右子节点的右子节点
    root->right->right = &(TreeNode){'F', NULL, NULL};

    int result = countDegreeTwoNodes(root);
    // 打印结果
    printf("度数为 2 的节点数：%d\n", result);
    return 0;
}

2. 求二叉树中值最大的元素

思路：

一、函数findMaxElement的思路

  1. 首先处理特殊情况，如果传入的根节点为NULL，表示是空树，此时返回空字符'\0'。
  2. 对于非空的二叉树，先将当前节点的值赋给变量max，作为当前已知的最大值的初始值。
  3. 然后通过递归调用分别查找左子树和右子树中的最大值，分别得到leftMax和rightMax。
  4. 接着将leftMax和max进行比较，如果leftMax大于max，则更新max为leftMax。
  5. 再将rightMax和max进行比较，如果rightMax大于max，则再次更新max为rightMax。
  6. 最后返回经过比较更新后的max，即整个二叉树中的最大值。

二、main函数的思路

  1. 动态分配内存创建二叉树的各个节点，并为每个节点赋予特定的值，同时建立节点之间的父子关系，构建出一个二叉树。
  2. 调用findMaxElement函数查找二叉树中的最大元素，并将结果存储在result中。
  3. 打印出二叉树中的最大元素。
  4. 最后释放动态分配的内存，以防止内存泄漏。先释放叶子节点的内存，然后依次释放较高层次节点的内存。

代码：

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

// 定义二叉树节点结构体
typedef struct BiTreeNode {
    char data;
    struct BiTreeNode *lChild;
    struct BiTreeNode *rChild;
} BiTreeNode;

char findMaxElement(BiTreeNode *root) {
    // 空节点返回空字符
    if (root == NULL) {
        return '\0';  
    }
    // 初始化当前节点的最大值
    char max = root->data;
    // 递归查找左子树和右子树的最大值
    char leftMax = findMaxElement(root->lChild);
    char rightMax = findMaxElement(root->rChild);
    // 更新最大值
    if (leftMax > max) {
        max = leftMax;
    }
    if (rightMax > max) {
        max = rightMax;
    }
    return max;  // 返回最大值
}

int main() {
    // 创建二叉树的根节点
    BiTreeNode *root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->data = 'A';
    // 创建根节点的左子节点
    root->lChild = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->lChild->data = 'B';
    // 创建根节点的右子节点
    root->rChild = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->rChild->data = 'C';
    // 创建根节点左子节点的左子节点
    root->lChild->lChild = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->lChild->lChild->data = 'D';
    // 创建根节点左子节点的右子节点
    root->lChild->rChild = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->lChild->rChild->data = 'E';
    // 创建根节点右子节点的右子节点
    root->rChild->rChild = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    root->rChild->rChild->data = 'F';

    char result = findMaxElement(root);
    printf("二叉树中的最大元素：%c\n", result);

    // 释放内存
    free(root->lChild->lChild);
    free(root->lChild->rChild);
    free(root->lChild);
    free(root->rChild->rChild);
    free(root->rChild);
    free(root);

    return 0;
}

3. 将二叉树各结点存储到一维数组中

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

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

// 将二叉树节点的值存储到数组的函数
void storeNodesToArray(TreeNode *root, char *array, int *index) {
    if (!root) return;
    array[(*index)++] = root->val;
    storeNodesToArray(root->left, array, index);
    storeNodesToArray(root->right, array, index);
}

int main() {
    // 动态创建根节点
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 'A';
    root->left = NULL;
    root->right = NULL;

    // 创建根节点的左子节点
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 'B';
    root->left->left = NULL;
    root->left->right = NULL;

    // 创建根节点的右子节点
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 'C';
    root->right->left = NULL;
    root->right->right = NULL;

    // 创建根节点左子节点的左子节点
    root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->left->val = 'D';
    root->left->left->left = NULL;
    root->left->left->right = NULL;

    // 创建根节点左子节点的右子节点
    root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->right->val = 'E';
    root->left->right->left = NULL;
    root->left->right->right = NULL;

    // 创建根节点右子节点的右子节点
    root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->right->val = 'F';
    root->right->right->left = NULL;
    root->right->right->right = NULL;

    char array[100];
    int index = 0;
    storeNodesToArray(root, array, &index);
    printf("节点顺序：");
    for (int i = 0; i < index; i++) {
        printf("%c ", array[i]);
    }
    printf("\n");

    // 释放动态分配的内存
    free(root->left->right);
    free(root->left->left);
    free(root->left);
    free(root->right->right);
    free(root->right);
    free(root);

    return 0;
}

4. 按先序输出二叉树中各结点，并输出它们所在的层次

思路：

一、函数preOrderWithLevel的思路

  1. 首先判断传入的根节点是否为空，如果为空则直接返回，不进行任何操作。
  2. 如果根节点不为空，打印当前节点的值以及对应的层级。这里的层级参数level是从外部传入的，在第一次调用时通常设为 1，表示根节点的层级。
  3. 然后通过递归调用分别处理左子树和右子树。在递归调用时，将层级参数加一，以表示进入下一层级。这样，对于每个节点，都能准确地输出其值和对应的层级。

二、main函数的思路

  1. 创建一个二叉树，手动初始化各个节点的值和指针关系。
  2. 调用preOrderWithLevel函数，从根节点开始以先序遍历的方式遍历二叉树，并输出每个节点的值和对应的层级。
#include <stdio.h>
#include <stdlib.h>

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

// 先序遍历二叉树并输出节点值和对应层级的函数
void preOrderWithLevel(TreeNode *root, int level) {
    // 如果根节点为空，直接返回
    if (!root) return;
    // 输出当前节点的值和层级
    printf("Node: %c, Level: %d\n", root->val, level);
    // 递归遍历左子树，层级加一
    preOrderWithLevel(root->left, level + 1);
    // 递归遍历右子树，层级加一
    preOrderWithLevel(root->right, level + 1);
}

int main() {
    TreeNode *root = &(TreeNode){'A', NULL, NULL};
    root->left = &(TreeNode){'B', NULL, NULL};
    root->right = &(TreeNode){'C', NULL, NULL};
    root->left->left = &(TreeNode){'D', NULL, NULL};
    root->left->right = &(TreeNode){'E', NULL, NULL};
    root->right->right = &(TreeNode){'F', NULL, NULL};

    preOrderWithLevel(root, 1);
    return 0;
}

5. 判断二叉树是否是完全二叉树

思路：

  1. 定义完全二叉树：

    • 完全二叉树是指在二叉树中，除了最后一层外，其余层都是满的，并且最后一层的节点都尽可能地靠左排列。
    • 换句话说，完全二叉树在遇到第一个空节点后，后续所有节点都必须是空的。

  2. 层次遍历：

    • 为了判断二叉树是否为完全二叉树，我们可以使用层次遍历（广度优先搜索，BFS）。层次遍历可以逐层访问节点，确保我们按从左到右的顺序检查每一层的节点。

  3. 使用队列：

    • 我们使用一个队列来辅助进行层次遍历。队列的特性是先进先出（FIFO），这保证了我们按层次顺序访问节点。
    • 初始化队列时，将根节点入队。

  4. 标志位 flag：

    • 我们设置一个标志位 flag，用于记录是否已经遇到了空节点。如果某个节点没有左孩子或右孩子，flag 就会被设置为 true。
    • 如果在 flag 被设置为 true 之后，遇到了非空节点，说明树不是完全二叉树，因为没有左孩子或右孩子的情况应该出现在最后一层的节点中。

  5. 遍历过程：

    • 从队列中取出当前节点 curr。
    • 检查当前节点的左孩子：
      • 如果左孩子存在且 flag 为 false，将左孩子入队。
      • 如果左孩子不存在，将 flag 设置为 true。
      • 如果左孩子存在但 flag 为 true，说明之前已经出现了空节点，现在又出现了非空节点，返回 false。
    • 检查当前节点的右孩子：
      • 如果右孩子存在且 flag 为 false，将右孩子入队。
      • 如果右孩子不存在，将 flag 设置为 true。
      • 如果右孩子存在但 flag 为 true，说明之前已经出现了空节点，现在又出现了非空节点，返回 false。

  6. 结束条件：

    • 如果遍历过程中没有发现任何不满足完全二叉树条件的情况，返回 true，表示树是完全二叉树。
bool isCompleteBinaryTree(BiTree root) {
    if (root == NULL) {
        return true;  // 空树是完全二叉树
    }
    BiTree queue[100];  // 使用数组模拟队列，最大假设为100个节点
    int front = 0, rear = 0;
    queue[rear++] = root;  // 将根节点入队
    bool flag = false;  // 标记是否出现了非满的情况
    while (front < rear) {
        BiTree curr = queue[front++];
        // 左孩子入队处理
        if (curr->lChild) {
            if (flag) return false;  // 如果已出现非满情况，返回false
            queue[rear++] = curr->lChild;
        } else {
            flag = true;  // 左孩子为空，后续的右孩子若出现不满则返回false
        }
        // 右孩子入队处理
        if (curr->rChild) {
            if (flag) return false;  // 同样检查右孩子
            queue[rear++] = curr->rChild;
        } else {
            flag = true;  // 右孩子为空，后面也不能有其他孩子
        }
    }
    return true;  // 遍历完毕, 是完全二叉树
}

6. 交换二叉树各结点的左右子树

解题思路：递归交换每个节点的左右子树指针。

void swapChildren(BiTree root) {
    if (root == NULL) {
        return;  // 空节点返回
    }
    // 交换左右子树
    BiTree temp = root->lChild;
    root->lChild = root->rChild;
    root->rChild = temp;
    // 递归处理左右子树
    swapChildren(root->lChild);
    swapChildren(root->rChild);
}

7. 写出在二叉树中查找值为 x 的结点在树中层数的算法

解题思路：通过递归遍历二叉树，搜索值为 x 的节点，并返回其层次，若未找到则返回 -1。

int findNodeLevel(BiTree root, char x, int level) {
    if (root == NULL) {
        return -1;  // 节点为空，返回未找到
    }
    // 找到目标节点，返回当前层次
    if (root->data == x) {
        return level;
    }
    // 递归查找左子树
    int leftLevel = findNodeLevel(root->lChild, x, level + 1);
    if (leftLevel != -1) {
        return leftLevel;  // 如果在左子树找到，直接返回
    }
    // 递归查找右子树
    return findNodeLevel(root->rChild, x, level + 1);
}

8. 设计算法计算给定二叉树中单孩子结点的数目

解题思路：遍历树，判断每个节点是否只有一个子节点并加以统计。

int countSingleChildNodes(BiTree root) {
    // 如果当前节点为空，返回0
    if (root == NULL) {
        return 0;
    }

    // 检查当前节点是否为单孩子节点
    int isSingleChild = 0;  // 初始化单孩子节点计数器

    // 判断当前节点是否有且仅有一个孩子
    if ((root->lChild == NULL && root->rChild != NULL) ||  // 只有右孩子
        (root->lChild != NULL && root->rChild == NULL)) {  // 只有左孩子
        isSingleChild = 1;  // 当前节点是单孩子节点
    }

    // 递归统计左子树和右子树的单孩子节点数
    int leftCount = countSingleChildNodes(root->lChild);  // 左子树的单孩子节点数
    int rightCount = countSingleChildNodes(root->rChild);  // 右子树的单孩子节点数

    // 返回当前节点的单孩子节点数加上左子树和右子树的单孩子节点数
    return isSingleChild + leftCount + rightCount;
}

9. 设计算法，将二叉树的所有叶子结点，按从左到右的顺序连成一个单链表，单链表用 rChild 域链接

解题思路：递归查找所有叶子节点，并通过rChild域将它们连接成链表。

BiNode* connectLeaves(BiTree root, BiNode **head, BiNode **tail) {
    if (root == NULL) {
        return NULL;  // 空节点直接返回
    }
    // 判断当前节点是否为叶子节点
    if (root->lChild == NULL && root->rChild == NULL) {
        if (*head == NULL) {
            *head = root;  // 若头节点为空，初始化头节点
            *tail = root;  // 初始化尾节点
        } else {
            (*tail)->rChild = root;  // 将尾节点的rChild指向当前叶子
            *tail = root;  // 更新尾节点
        }
    }
    // 递归查找左右子树的叶子节点
    connectLeaves(root->lChild, head, tail);
    connectLeaves(root->rChild, head, tail);
    return *head;  // 返回链表头节点
}

BiTree convertLeavesToList(BiTree root) {
    BiNode *head = NULL, *tail = NULL;  // 初始化头尾指针
    connectLeaves(root, &head, &tail);  // 调用连接叶子节点函数
    return head;  // 返回头节点作为链表
}

http://www.kler.cn/a/379438.html

相关文章：

  • 数学建模学习（135）：使用Python基于WSM、WPM、WASPAS的多准则决策分析
  • Jetson Orin NX平台自研载板 IMX477相机掉线问题调试记录
  • 基于深度学习的数据安全与可追溯性增强
  • 【Python】【数据可视化】【商务智能方法与应用】课程 作业一 飞桨AI Studio
  • openEuler 系统中 Samba 文件共享服务器管理（windows、linux文件共享操作方法）
  • 九，数据类型存储
  • 自然语言处理研究方向在跨语言处理方面有哪些新的创新思路？
  • 【c++日常刷题】两个数字的交集、点击消除、最小花费爬楼梯
  • 架构师备考-软件工程相关补充
  • Android使用scheme方式唤醒处于后台时的App场景
  • Python复习2
  • 笔记-利率学习记录
  • easy-es使用以及Es和MySQL同步
  • Go-Sqlite3学习
  • “格格不入”的星瑞东方曜，燃油市场有麻烦了
  • 进程守护SuperVisord内部的进程定时监测并重启
  • 2024年华为OD机试真题-最小的调整次数-Python-OD统一考试（E卷）
  • locust压测工具环境搭建（Linux、Mac）
  • FBX福币交易所国际油价突然大涨！美伊针锋相对
  • json-server的使用（根据json数据一键生成接口）
  • jenkins自动化构建vue(web)项目并部署(项目实战)
  • RocketMQ可视化工具- Dashboard 使用教程 (附带可下载文件)
  • gulp入门教程14：vinyl
  • Git学习记录
  • MoonNet基准测试更新
  • springboot3项目整合Mybatis-plus启动项目报错：Invalid bean definition with name ‘xxxMapper‘