用C语言以二叉链表作为存储结构,建立一棵二叉树; 分别按先序、中序、后序和层次顺序遍历二叉树。
时间: 2023-06-06 15:05:52 浏览: 169
二叉树的基本运算 数据结构
好的,这是一道关于数据结构的问题,我可以尽力为您解答。首先,我们可以先定义二叉树的结构体:
```
typedef struct Node{
struct Node *lchild, *rchild;
int value;
} Node, *Tree;
```
其表示了二叉树的每个节点包含左右子树指针和值。接下来,我们可以使用递归的方式实现先序遍历、中序遍历、后序遍历:
```
// 先序遍历
void preorder(Tree root) {
if(root) {
printf("%d ", root->value);
preorder(root->lchild);
preorder(root->rchild);
}
}
// 中序遍历
void inorder(Tree root) {
if(root) {
inorder(root->lchild);
printf("%d ", root->value);
inorder(root->rchild);
}
}
// 后序遍历
void postorder(Tree root) {
if(root) {
postorder(root->lchild);
postorder(root->rchild);
printf("%d ", root->value);
}
}
```
对于层次遍历,可以使用队列来实现:
```
void levelorder(Tree root) {
if(!root) return;
Queue q = createQueue();
EnQueue(q, root);
while(!isEmpty(q)) {
Tree node = DeQueue(q);
printf("%d ", node->value);
if(node->lchild) EnQueue(q, node->lchild);
if(node->rchild) EnQueue(q, node->rchild);
}
}
```
其中,createQueue() 和 EnQueue()、DeQueue() 是队列的创建和基本操作,这里不再详细解释。希望这些代码能够帮助您解决问题。
阅读全文