上机实验三 图的最小生成树算法设计 西安石油大学数据结构

二叉树设计

实验名称：二叉树设计

（1）实验目的：

1） 掌握二叉树的逻辑结构。

2） 掌握二叉树的二叉链表存储结构；

3） 掌握基于二叉链表存储的二叉树的遍历等操作的实现。

（2）主要内容：

1） 定义二叉链存储结构。

2） 实现二叉树的建立（利用扩展先序序列建立二叉链表存储的二叉树）、二叉树的遍历、统计二叉树结点数、求二叉树高度、打印二叉树等操作。

3） 编写一个测试主函数，建立如下二叉树，并测试所设计的算法。

二叉树的基本概念

二叉树是一种常见的树形数据结构，每个节点最多有两个子节点，分别称为左节点和右节点。如果一个节点没有左或右子节点，则对应的子节点为空。二叉树可以为空，如果不为空，则必须包含一个根节点。

二叉树的定义可以使用递归方式来描述，即一个二叉树要么为空，要么由一个根节点和两个分别为左子树和右子树的二叉树组成。在实际应用中，二叉树通常用于表示层次结构、搜索树等。

二叉树的遍历方式包括前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。其中，前序遍历顺序是：先访问根节点，然后依次遍历左子树和右子树；中序遍历顺序是：先访问左子树，然后遍历根节点，最后遍历右子树；后序遍历顺序是：先访问左子树，然后依次遍历右子树和根节点。

二叉树还有一种广义的遍历方式，叫做层序遍历，也称为广度优先遍历。层序遍历按照从上到下、从左到右的顺序依次访问每个节点。

二叉树的应用非常广泛，比如在搜索算法中用于二分查找和决策树等。

二叉树是一种树形数据结构，在其中每个节点最多有两个子节点。以下是二叉树的一些基本概念：

1. 根节点（Root Node）：二叉树的顶层节点，没有父节点。它是整个二叉树的起点。
   
2. 子节点（Child Node）：一个节点的直接下方节点称为其子节点。一个节点最多可以有两个子节点，分别称为左子节点和右子节点。
   
3. 父节点（Parent Node）：一个节点的直接上方节点称为其父节点。
   
4. 叶节点（Leaf Node）：没有子节点的节点称为叶节点，也可以称为终端节点。
   
5. 内部节点（Internal Node）：除了叶节点以外的所有节点都被称为内部节点。
   
6. 兄弟节点（Sibling Node）：具有相同父节点的节点被称为兄弟节点。
   
7. 节点的度（Node Degree）：节点的度表示它拥有的子节点数目，在二叉树中，节点的度最大为2。
   
8. 节点的层级（Node Level）：根节点的层级为0，其他节点的层级等于其父节点的层级加1。
   
9. 树的高度（Tree Height）：树的高度是指从根节点到最远叶节点的层数。
   
10. 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层的节点都被填满，且最后一层的节点都靠左排列。
    
11. 满二叉树（Full Binary Tree）：除了叶节点外，每个节点都有两个子节点。
    

二叉树常见用途

二叉树在计算机科学和软件工程中有广泛的应用。以下是二叉树的一些常见用途：

1. 搜索算法：二叉搜索树（BST）是一种特殊的二叉树，其中左子树的节点值小于根节点，右子树的节点值大于根节点。这种特性使得二叉搜索树非常适合实现搜索算法，例如二分查找。
   
2. 排序算法：堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。二叉堆是一种特殊的完全二叉树，具有堆属性，可以高效地进行插入、删除最大/最小元素等操作。
   
3. 表达式求值：二叉表达式树（Expression Tree）可以用于解析和求值数学表达式。每个操作符作为一个节点，其左右子节点分别表示操作符的操作数。
   
4. 文件系统和目录结构：二叉树可以用于建模文件系统和目录结构。每个节点表示一个目录或文件，左子节点和右子节点连接到下级目录或文件。
   
5. 线索二叉树：线索二叉树（Threaded Binary Tree）可以优化二叉树的遍历过程。通过添加前驱和后继指针，可以避免使用递归或栈来实现遍历。
   
6. 数据压缩：霍夫曼树（Huffman Tree）是一种特殊的二叉树，用于数据压缩中的霍夫曼编码。在霍夫曼编码中，频率较高的字符被分配较短的编码，从而实现数据的高效压缩。
   
7. 机器学习和决策树：决策树是一种基于二叉树结构的分类和回归模型。每个节点表示一个属性或特征，根据不同属性的取值进行分支，最终到达叶节点表示分类或回归结果。
   

除了上述用途，二叉树还可以作为其他数据结构的基础，例如AVL树、红黑树等。对于广义的树形结构，二叉树可以通过适当的扩展和变形来表示和处理，提供了更大的灵活性和效率。

二叉树的二叉链表存储结构

二叉树的二叉链表存储结构是指使用指向左右子节点的指针，将每个节点的数据和其左右子节点连接起来，以构成二叉树。具体来说，每个节点包含三个域：数据域、左子节点指针域和右子节点指针域，如下所示：

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left_child;
    BinaryTreeNode* right_child;
};

在二叉链表存储结构中，每个节点都包含一个数据元素和两个指针域，其中指针域可能为 NULL。如果指针域为 NULL，则表示该节点没有对应的左/右子节点。

考虑如何创建一个简单的二叉树，如下图所示：

10
       /  \
      5   15
         /  \
        12  20

可以使用以下 C++ 代码构建此二叉树：

BinaryTreeNode* root = new BinaryTreeNode {10, nullptr, nullptr};
root->left_child = new BinaryTreeNode {5, nullptr, nullptr};
root->right_child = new BinaryTreeNode {15, nullptr, nullptr};
root->right_child->left_child = new BinaryTreeNode {12, nullptr, nullptr};
root->right_child->right_child = new BinaryTreeNode {20, nullptr, nullptr};

这里通过 new 运算符动态创建每个节点，并在需要时设置其左右子节点指针。

二叉链表存储结构的优点是可以很方便地遍历二叉树，例如使用递归实现前序、中序和后序遍历。由于每个节点有两个指针域，因此需要额外的空间来存储这些指针。此外，二叉链表存储结构相对于顺序存储结构，插入和删除操作更为高效。

除了前、中、后序遍历之外，二叉树的二叉链表存储结构还允许进行其他类型的遍历，例如层次遍历和镜像遍历。

层次遍历是一种广度优先搜索（BFS）的算法，按照从上到下、从左到右的顺序依次访问每个节点。层次遍历可以使用队列来实现，将根节点加入队列，然后逐层遍历其子节点。对于当前访问的节点，首先将其子节点加入队列，然后出队队首节点继续访问。直到队列为空，遍历结束。

下面是 C++ 实现层次遍历的代码：

void level_order_traversal(BinaryTreeNode* root) {
    if (root == nullptr) return;
    queue<BinaryTreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        cout << current->data << " ";
        if (current->left_child != nullptr) q.push(current->left_child);
        if (current->right_child != nullptr) q.push(current->right_child);
    }
}

镜像遍历（Mirror Traversal）是指访问二叉树的一个镜像，也就是先访问右子树再访问左子树。镜像遍历可以利用递归实现，并将左右子树的访问顺序交换即可。

下面是 C++ 实现镜像遍历的代码：

void mirror_traversal(BinaryTreeNode* root) {
    if (root == nullptr) return;
    mirror_traversal(root->right_child);
    cout << root->data << " ";
    mirror_traversal(root->left_child);
}

二叉树的二叉链表存储结构可以方便地实现这些遍历算法，并提供了高效的插入和删除操作。在使用二叉树时，可以根据具体场景选择适合的存储结构，以达到更好的性能和实现效果。

1
  / \
 2   3
    / \
   4   5
  /
 6

二叉链存储结构

什么是二叉链存储结构

二叉链存储结构是一种常用的表示二叉树的存储方式，它使用节点对象和引用来表示二叉树的结构。

它将每个节点分别表示为一个包含该节点的数据、一个指向其左子树的指针、一个指向其右子树的指针以及一个指向其父节点的指针的结构体。这样，每个节点可以通过其左右子树的指针进行遍历和访问，同时也可以通过其父节点的指针追溯到其祖先节点。

二叉链存储结构相对于其他二叉树存储结构的优点在于，可以方便地实现一些操作，例如：给定一个节点，可以快速地找到其父节点；给定两个节点，可以快速地计算它们之间的距离（即它们的最近公共祖先到它们的距离之和）。

在使用二叉链存储结构时，由于每个节点都包含其父节点的指针，因此需要额外的空间开销。同时，为了避免出现环形引用，通常会将根节点的父节点指针设置为 NULL 。

以下是一个简单的 C++ 实现，包括二叉链存储结构的定义、建立二叉树、遍历、统计节点数、求二叉树高度和打印二叉树的操作。

#include <iostream>
using namespace std;
// 定义二叉树的节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 建立二叉树
TreeNode* createBinaryTree(string s, int& index) {
    if (index >= s.length()) {
        return NULL;
    }
    if (s[index] == '#') {
        index++;
        return NULL;
    }
    TreeNode* root = new TreeNode(s[index] - '0');
    index++;
    root->left = createBinaryTree(s, index);
    root->right = createBinaryTree(s, index);
    return root;
}
// 先序遍历
void preorderTraversal(TreeNode* root) {
    if (root) {
        cout << root->val << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}
// 统计节点数
int countNodes(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}
// 求二叉树高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}
// 打印二叉树
void printBinaryTree(TreeNode* root, int level) {
    if (root == NULL) {
        return;
    }
    printBinaryTree(root->right, level + 1);
    for (int i = 0; i < level; i++) {
        cout << "    ";
    }
    cout << root->val << endl;
    printBinaryTree(root->left, level + 1);
}
int main() {
    string s = "123##4#6##5##";
    int index = 0;
    TreeNode* root = createBinaryTree(s, index);
    
    // 测试先序遍历
    cout << "Preorder traversal: ";
    preorderTraversal(root);
    cout << endl;
    
    // 测试统计节点数
    cout << "Number of nodes: " << countNodes(root) << endl;
    
    // 测试求二叉树高度
    cout << "Height of the binary tree: " << getHeight(root) << endl;
    
    // 测试打印二叉树
    cout << "Print the binary tree:" << endl;
    printBinaryTree(root, 0);
    
    return 0;
}

意见和建议

这段代码的实现有一些问题和可以改进的地方：

1. 输入校验不足：代码中对输入的字符串格式没有进行校验，如果输入的字符串不符合预期的二叉树表示形式，可能会导致程序出错。
   
2. 没有内存释放：在创建二叉树的过程中使用了 new 关键字来动态分配内存，但在程序结束时没有释放这些内存，可能会导致内存泄漏。
   
3. 打印二叉树的格式化问题：当前的打印函数输出的二叉树结构不够美观，可以考虑使用更好的格式化方法来打印二叉树，使其更易于理解。
   
4. 缺乏错误处理：代码中没有对可能出现的错误情况进行处理，比如在创建二叉树过程中发生内存分配失败，或者输入的字符串格式不正确时，程序没有提供相应的异常处理。
   
5. 全局变量的使用：代码中使用了全局变量 index 来记录当前处理的字符位置，这种做法不利于代码的可维护性和可移植性。
   

建议改进的地方包括：

1. 增加输入校验：在创建二叉树的过程中，可以增加对输入字符串格式的校验，确保输入的字符串能够正确表示一个二叉树。
   
2. 添加内存释放：在程序结束时，应该释放通过 new 分配的内存，避免内存泄漏问题。
   
3. 优化打印函数：可以考虑使用更好的方法来打印二叉树，例如按层级打印，或者使用图形化的方式呈现二叉树结构。
   
4. 增加错误处理：对可能出现的错误情况进行处理，比如在内存分配失败时给出相应的提示，或者对输入格式不正确的情况进行处理。
   
5. 减少全局变量的使用：避免使用全局变量，尽量将变量的作用域限制在函数内部，以提高代码的可维护性和可读性。
   

综上所述，对这段代码的改进包括增加输入校验、添加内存释放、优化打印函数、增加错误处理和减少全局变量的使用。