二叉树设计
实验名称：二叉树设计
（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，则表示该节点没有对应的左/右子节点。
考虑如何创建一个简单的二叉树，如下图所示：
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; }
意见和建议
这段代码的实现有一些问题和可以改进的地方：
- 输入校验不足：代码中对输入的字符串格式没有进行校验，如果输入的字符串不符合预期的二叉树表示形式，可能会导致程序出错。
- 没有内存释放：在创建二叉树的过程中使用了
new关键字来动态分配内存，但在程序结束时没有释放这些内存，可能会导致内存泄漏。 - 打印二叉树的格式化问题：当前的打印函数输出的二叉树结构不够美观，可以考虑使用更好的格式化方法来打印二叉树，使其更易于理解。
- 缺乏错误处理：代码中没有对可能出现的错误情况进行处理，比如在创建二叉树过程中发生内存分配失败，或者输入的字符串格式不正确时，程序没有提供相应的异常处理。
- 全局变量的使用：代码中使用了全局变量
index来记录当前处理的字符位置，这种做法不利于代码的可维护性和可移植性。
建议改进的地方包括：
- 增加输入校验：在创建二叉树的过程中，可以增加对输入字符串格式的校验，确保输入的字符串能够正确表示一个二叉树。
- 添加内存释放：在程序结束时，应该释放通过
new分配的内存，避免内存泄漏问题。 - 优化打印函数：可以考虑使用更好的方法来打印二叉树，例如按层级打印，或者使用图形化的方式呈现二叉树结构。
- 增加错误处理：对可能出现的错误情况进行处理，比如在内存分配失败时给出相应的提示，或者对输入格式不正确的情况进行处理。
- 减少全局变量的使用：避免使用全局变量，尽量将变量的作用域限制在函数内部，以提高代码的可维护性和可读性。
综上所述，对这段代码的改进包括增加输入校验、添加内存释放、优化打印函数、增加错误处理和减少全局变量的使用。
