二叉树存储结构及遍历c语言实现
时间: 2023-11-25 07:08:36 浏览: 42
二叉树可以用链式存储结构或者数组存储结构来实现。下面是链式存储结构的实现:
```c
typedef struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
} Node;
// 前序遍历
void preOrder(Node *root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
// 中序遍历
void inOrder(Node *root) {
if (root != NULL) {
inOrder(root->leftChild);
printf("%d ", root->data);
inOrder(root->rightChild);
}
}
// 后序遍历
void postOrder(Node *root) {
if (root != NULL) {
postOrder(root->leftChild);
postOrder(root->rightChild);
printf("%d ", root->data);
}
}
```
其中,前序遍历先访问根节点,再访问左子树,最后访问右子树;中序遍历先访问左子树,再访问根节点,最后访问右子树;后序遍历先访问左子树,再访问右子树,最后访问根节点。
如果使用数组存储结构,可以按照如下方式实现:
```c
#define MAX_SIZE 100
int tree[MAX_SIZE];
// 前序遍历
void preOrder(int root, int size) {
if (root < size) {
printf("%d ", tree[root]);
preOrder(root * 2 + 1, size);
preOrder(root * 2 + 2, size);
}
}
// 中序遍历
void inOrder(int root, int size) {
if (root < size) {
inOrder(root * 2 + 1, size);
printf("%d ", tree[root]);
inOrder(root * 2 + 2, size);
}
}
// 后序遍历
void postOrder(int root, int size) {
if (root < size) {
postOrder(root * 2 + 1, size);
postOrder(root * 2 + 2, size);
printf("%d ", tree[root]);
}
}
```
数组实现中,左子节点的下标为 root * 2 + 1,右子节点的下标为 root * 2 + 2。下标从 0 开始,因此如果树的节点数为 n,数组的大小应该为 2^n - 1。