1 二叉树的二叉链表存储结构及基本算法的设计与实现 （1）二叉树的创建 （2）二叉树的销毁 （3）二叉树的遍历（先序遍历、中序遍历、后序遍历和层次遍历） （4）用括号表示法输出二叉树模块图

### 二叉树的二叉链表存储结构 在计算机科学中，二叉树是一种重要的数据结构。为了有效地管理和操作二叉树，通常采用二叉链表作为其存储方式之一。每个结点由三部分组成：指向左孩子的指针、数据域和指向右孩子的指针。 #### 结构定义 ```c++ typedef struct BiTNode { char data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode,*BiTree; ``` ### 基本算法设计与实现 #### 创建二叉树 通过前序序列可以唯一确定一棵二叉树。这里提供一种基于字符输入构建的方法： ```c++ void CreateBiTree(BiTree &T){ char ch; cin >> ch; if(ch == '#') T = NULL; else{ T = new BiTnode; T->data = ch; CreateBiTree(T->lchild); // 构建左子树 CreateBiTree(T->rchild); // 构建右子树 } } ``` #### 销毁二叉树 释放内存空间并使该二叉树为空的过程称为销毁二叉树。 ```c++ void DestroyBiTree(BiTree &T){ if (T != nullptr) { // 若当前节点不为空，则继续处理 DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); delete T; // 删除此节点所占的空间 T = nullptr; // 将指针置为NULL防止悬挂指针 } } ``` #### 遍历方法 ##### 先序遍历（Preorder Traversal） 按照访问根节点 -> 访问左子树 -> 访问右子树的方式依次递归地遍历整棵树。 ```c++ void PreOrderTraverse(BiTree T,void(*Visit)(char)){ if (T!=nullptr){ // 如果不是空树则执行下面语句 Visit(T->data); // 处理根节点的数据 PreOrderTraverse(T->lchild,Visit);// 对左子树做相同的操作 PreOrderTraverse(T->rchild,Visit);// 对右子树做相同的操作 } } ``` ##### 中序遍历（Inorder Traversal） 遵循访问左子树 -> 访问根节点 -> 访问右子树的原则来遍历整个二叉树。 ```c++ void InOrderTraverse(BiTree T,void(*Visit)(char)){ if (T!=nullptr){ InOrderTraverse(T->lchild,Visit); Visit(T->data); InOrderTraverse(T->rchild,Visit); } } ``` ##### 后序遍历（Postorder Traversal） 采取先访问左右子树再回溯到父节点进行访问的形式完成遍历过程。 ```c++ void PostOrderTraverse(BiTree T,void(*Visit)(char)){ if (T!=nullptr){ PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); } } ``` ##### 层次遍历（Level Order Traversal） 层次遍历是指按层顺序逐层扫描各节点，在同一层内自左向右依次读取各个顶点的信息。 ```c++ #include <queue> using namespace std; void LevelOrderTraverse(BiTree T,void (*Visit)(char)) { queue<BiTNode*> q; if (!T) return ; q.push(T); while(!q.empty()){ auto node=q.front(); q.pop(); Visit(node->data); if(node->lchild) q.push(node->lchild); if(node->rchild) q.push(node->rchild); } } ``` #### 使用括号表示法输出二叉树模块图 对于给定的一棵二叉树，可以通过特定格式打印出来以便于观察其形态特征。具体做法如下所示: ```cpp string TreeToString(const BiTree& root) { if(root==nullptr)return "()"; string res="("+to_string(root->data)+","; res+=TreeToString(root->lchild); res=res+","; res+=TreeToString(root->rchild); res+=")"; return res; } // 打印函数调用例子 cout<<TreeToString(tree)<<endl; ``` 上述代码实现了将二叉树转换成字符串形式的功能，其中`()`代表空子树；`(A,B,C)`分别对应着根节点及其左右两个分支的内容[^1]。