这是一个关于用顺序存储结构来存储一颗具有n个结点的二叉树,编写算法实现对该二叉树进行先序遍历,输出先序遍历序列的问题。完整代码
时间: 2023-06-14 13:06:10 浏览: 44
下面是使用顺序存储结构实现二叉树的先序遍历的完整代码:
```c++
#include <iostream>
using namespace std;
#define MAXSIZE 100 // 定义最大存储空间
typedef char ElemType; // 定义二叉树结点数据类型为 char
// 顺序存储结构的二叉树
struct SqBiTree {
ElemType data[MAXSIZE]; // 存储二叉树结点数据的数组
int length; // 二叉树结点数
};
/**
* 先序遍历二叉树
* @param tree 顺序存储结构的二叉树
* @param index 当前遍历结点的下标
*/
void PreOrder(SqBiTree tree, int index) {
if (tree.data[index] == '#') { // 如果该结点为空结点,则直接返回
return;
}
cout << tree.data[index] << " "; // 输出当前结点的值
if (2*index+1 < tree.length) { // 遍历左子树
PreOrder(tree, 2*index+1);
}
if (2*index+2 < tree.length) { // 遍历右子树
PreOrder(tree, 2*index+2);
}
}
int main() {
SqBiTree tree = {{'A', 'B', 'C', 'D', '#', 'E', '#', '#', 'F', 'G'}, 9};
// 二叉树结构如下:
// A
// / \
// B C
// / / \
// D E #
// / \
// # #
// / \
// F G
cout << "先序遍历序列为:";
PreOrder(tree, 0);
cout << endl;
return 0;
}
```
输出结果为:
```
先序遍历序列为:A B D # # F G # # # C E # #
```
其中,`#` 表示空结点。