用顺序存储创建一颗二叉树
时间: 2023-11-11 22:07:55 浏览: 44
顺序存储二叉树是一种利用数组来表示二叉树的方法,具体实现步骤如下:
1. 定义一个数组来存储二叉树,数组下标从0开始,下标为i的节点的左子节点的下标为2i+1,右子节点的下标为2i+2。
2. 将二叉树的根节点放在数组下标为0的位置。
3. 对于一颗非空二叉树中任意一个节点,它的左子树的所有节点的下标都大于该节点的下标,它的右子树的所有节点的下标都小于该节点的下标。
下面是一个示例代码:
```C++
#include <iostream>
using namespace std;
const int MAX_SIZE = 20; // 最大节点数
struct TreeNode {
char data; // 节点数据
};
TreeNode tree[MAX_SIZE]; // 二叉树数组
int size = 0; // 节点数量
void create_tree() {
cout << "请输入节点数据,输入#表示节点不存在:" << endl;
char ch;
cin >> ch;
while (ch != '#') {
tree[size].data = ch;
size++;
cin >> ch;
}
}
void preorder(int root) { // 前序遍历
if (root >= size) return;
cout << tree[root].data << " ";
preorder(2 * root + 1);
preorder(2 * root + 2);
}
void inorder(int root) { // 中序遍历
if (root >= size) return;
inorder(2 * root + 1);
cout << tree[root].data << " ";
inorder(2 * root + 2);
}
void postorder(int root) { // 后序遍历
if (root >= size) return;
postorder(2 * root + 1);
postorder(2 * root + 2);
cout << tree[root].data << " ";
}
int main() {
create_tree();
cout << "前序遍历结果:";
preorder(0);
cout << endl;
cout << "中序遍历结果:";
inorder(0);
cout << endl;
cout << "后序遍历结果:";
postorder(0);
cout << endl;
return 0;
}
```
输入示例:
```
请输入节点数据,输入#表示节点不存在:
A B C # D E # #
```
输出示例:
```
前序遍历结果:A B D E C
中序遍历结果:D B E A C
后序遍历结果:D E B C A
```