### 伪代码
1. **CreateBiTree**:
- 读取一个字符 `ch`。
- 如果 `ch` 是 `#`，则当前节点为空。
- 否则，创建一个新节点 `T`，将 `ch` 赋值给 `T` 的数据域。
- 递归创建 `T` 的左子树。
- 递归创建 `T` 的右子树。
2. **PreOrderTraverse**:
- 如果 `T` 不为空，先访问根节点，再递归访问左子树，最后递归访问右子树。
3. **InOrderTraverse**:
- 如果 `T` 不为空，先递归访问左子树，再访问根节点，最后递归访问右子树。
4. **PostOrderTraverse**:
- 如果 `T` 不为空，先递归访问左子树，再递归访问右子树，最后访问根节点。
5. **main**:
- 创建二叉树 `T`。
- 调用前序遍历函数。
- 调用中序遍历函数。
- 调用后序遍历函数。
### C++代码
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;typedef char ElemType;
typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;Status CreateBiTree(BiTree &T) { // 算法6.4// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，// 构造二叉链表表示的二叉树T。char ch;scanf(" %c", &ch);if (ch == '#') T = NULL;else {if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;T->data = ch; // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}return OK;
} // CreateBiTreeStatus PreOrderTraverse(BiTree T) {// 前序遍历二叉树T的递归算法if (T) {printf("%c", T->data); // 访问根节点PreOrderTraverse(T->lchild); // 递归遍历左子树PreOrderTraverse(T->rchild); // 递归遍历右子树}return OK;
} // PreOrderTraverseStatus InOrderTraverse(BiTree T) {// 中序遍历二叉树T的递归算法if (T) {InOrderTraverse(T->lchild); // 递归遍历左子树printf("%c", T->data); // 访问根节点InOrderTraverse(T->rchild); // 递归遍历右子树}return OK;
} // InOrderTraverseStatus PostOrderTraverse(BiTree T) {// 后序遍历二叉树T的递归算法if (T) {PostOrderTraverse(T->lchild); // 递归遍历左子树PostOrderTraverse(T->rchild); // 递归遍历右子树printf("%c", T->data); // 访问根节点}return OK;
} // PostOrderTraverseint main() { // 主函数BiTree T;CreateBiTree(T); // 创建二叉树PreOrderTraverse(T); // 前序遍历printf("\n");InOrderTraverse(T); // 中序遍历printf("\n");PostOrderTraverse(T); // 后序遍历printf("\n");return 0;
} // main
