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

二叉树设计

实验名称：二叉树设计

（1）实验目的：

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

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

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

（2）主要内容：

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

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

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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

二叉树的基本概念

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

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

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

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

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

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

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

二叉树常见用途

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

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

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

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

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

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

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

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

可以使用以下 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);
}

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

二叉链存储结构

什么是二叉链存储结构

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

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

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

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

意见和建议

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

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