C++实现二叉树操作：创建与遍历

"C++代码实现二叉树的基本操作，包括创建、打印和前序遍历" 在计算机科学中，数据结构是存储和组织数据的重要方式，而二叉树是一种非常基础且常用的数据结构。二叉树由节点（或称为结点）组成，每个节点包含一个值和指向其左子节点和右子节点的指针。这里，我们讨论的是使用C++语言实现二叉树的操作。 首先，我们定义了一个名为`Bnode`的结构体，它代表二叉树中的一个节点。结构体包含三个成员：一个字符类型的数据字段`data`，以及两个指向左右子节点的指针`lson`和`rson`。 ```cpp struct Bnode { char data; struct Bnode *lson, *rson; }; ``` 接着，我们看到一个名为`Create`的函数，它用于根据中缀表达式（Infix）和后缀表达式（Suffix）创建一棵二叉树。这个函数采用递归的方式，从后缀表达式的末尾开始，找到与中缀表达式匹配的运算符，然后创建一个新节点，将运算符作为节点值，并分别递归创建左子树（对应中缀表达式的左侧部分）和右子树（对应中缀表达式的右侧部分）。 ```cpp Bnode* Create(char* Infix, char* Suffix, int length) { // ... 函数实现 ... } ``` `Print`函数用于按照层次顺序打印二叉树。它使用一个栈`stack`来存储待处理的节点，以及一个数组`control`来记录当前节点的输出宽度，以便保持层次对齐。通过不断入栈和出栈节点，以及更新输出宽度，可以按层次顺序依次打印所有节点。 ```cpp void Print(Bnode* b) { // ... 函数实现 ... } ``` `preorder`函数则执行二叉树的前序遍历。前序遍历的顺序是：根节点 -> 左子树 -> 右子树。这个函数递归地访问每个节点，先打印节点值，然后遍历左子树，最后遍历右子树。 ```cpp void preorder(Bnode* t) { // ... 函数实现 ... } ``` 此外，还有一个`THeight`函数，它的目的是计算二叉树的高度。由于题目中这部分内容不完整，假设它是一个递归函数，用于计算给定节点`t`的子树的最大高度。如果节点为空，返回-1；否则，计算左子树和右子树的高度，返回两者之间的较大值加1。 ```cpp int THeight(Bnode* t) { int h1, h2; if (t == NULL) return (-1); h1 = THeight(t->lson); h2 = THeight(t->rson); return (h1 > h2 ? h1 : h2) + 1; } ``` 总结来说，这段代码提供了创建、打印和遍历二叉树的功能。创建二叉树是基于后缀表达式的，这通常在解析表达式时用到。打印函数按照层次顺序输出树的结构，便于可视化。前序遍历则是一种常见的遍历策略，对于理解和处理二叉树的数据非常有用。最后，计算树的高度有助于理解树的形状和平衡性。这些基本操作是二叉树算法和数据结构学习中的重要组成部分。