链表、二叉树的应用和算法设计

Question

链表、二叉树的应用和算法设计

2．实验内容
（1）将两个单链表合并为一个单链表。
（2）求二叉树中的结点个数、叶子结点个数以及某结点的层次。

实验环境
硬件环境：Windows7及以上版本操作系统
软件环境：Dev C++\VC++6.0

能否有兄弟帮忙解决一下实验方法和步骤还有程序及测试结果

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

实验方法和步骤：

1. 将两个单链表合并为一个单链表：
   （1）定义一个新的链表作为合并后的结果链表，初始化为空链表。
   （2）遍历第一个链表，将每个节点插入到结果链表的末尾。
   （3）再遍历第二个链表，将每个节点插入到结果链表的末尾。
   （4）返回合并后的链表。

2. 求二叉树的结点个数、叶子结点个数以及某结点的层次：
   （1）结点个数：使用递归的方法，若二叉树为空，则结点个数为0；否则，结点个数为根节点加上左子树的结点个数和右子树的结点个数之和。
   （2）叶子结点个数：使用递归的方法，若二叉树为空，则叶子结点个数为0；若二叉树只有一个结点，则叶子结点个数为1；否则，叶子结点个数为左子树的叶子结点个数加上右子树的叶子结点个数之和。
   （3）某结点的层次：使用递归的方法，若二叉树为空，则返回0；若二叉树的根结点为目标结点，则返回1；否则，在左子树中递归查找目标结点，在右子树中递归查找目标结点，返回结果较大的层次值加1。

程序示例及测试结果：
以下是C++语言的程序示例：

#include <iostream>
using namespace std;

// 定义单链表节点的结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 将两个单链表合并为一个单链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);  // 创建一个哑节点作为结果链表的头节点
    ListNode* cur = dummy;  // cur指针用于遍历结果链表

    // 遍历l1和l2，比较节点的值，并将较小的节点插入到结果链表的末尾
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    // 若l1或l2还有剩余节点，直接将剩余节点接到结果链表的末尾
    if (l1) {
        cur->next = l1;
    }
    if (l2) {
        cur->next = l2;
    }

    return dummy->next;  // 返回结果链表的头节点（哑节点的下一个节点）
}

// 定义二叉树节点的结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 求二叉树的结点个数
int countNodes(TreeNode* root) {
    if (!root) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 求二叉树的叶子结点个数
int countLeaves(TreeNode* root) {
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

// 求某结点的层次
int findLevel(TreeNode* root, int target, int level) {
    if (!root) {
        return 0;
    }
    if (root->val == target) {
        return level;
    }
    int leftLevel = findLevel(root->left, target, level + 1);
    int rightLevel = findLevel(root->right, target, level + 1);
    if (leftLevel > rightLevel) {
        return leftLevel;
    } else {
        return rightLevel;
    }
}

int main() {
    // 单链表合并示例
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    ListNode* mergedList = mergeTwoLists(l1, l2);

    cout << "Merged List: ";
    ListNode* p = mergedList;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;

    // 二叉树操作示例
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    int nodeCount = countNodes(root);
    int leafCount = countLeaves(root);
    int targetNode = 5;
    int nodeLevel = findLevel(root, targetNode, 1);

    cout << "Node Count: " << nodeCount << endl;
    cout << "Leaf Count: " << leafCount << endl;
    cout << "Level of Node " << targetNode << ": " << nodeLevel << endl;

    return 0;
}

输出结果为：

Merged List: 1 2 3 4 5 6
Node Count: 7
Leaf Count: 4
Level of Node 5: 3

以上示例代码中包括了两个操作的函数实现以及测试样例。你可以将这段代码拷贝到Dev C++或VC++6.0中编译并运行，验证其正确性。