C语言创建二叉链树,完成二叉树的先序、中序遍历
时间: 2023-08-17 07:04:12 浏览: 85
c代码-递归创建二叉树,先序、中序、后序递归遍历二叉树
好的,我可以帮您解答这个问题。
首先,我们需要定义二叉树的节点结构体:
```c
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
```
其中,`data` 表示节点存储的数据,`lchild` 和 `rchild` 分别表示左子树和右子树指针。
接下来,我们可以编写创建二叉树的函数:
```c
BTNode *createBT(){
char c;
scanf("%c", &c);
if(c == '#'){
return NULL;
}
BTNode *root = (BTNode*)malloc(sizeof(BTNode));
root->data = c;
root->lchild = createBT();
root->rchild = createBT();
return root;
}
```
这个函数通过递归方式,先输入一个字符,如果是 `#` 表示该节点为空,返回 `NULL`,否则新建一个节点,并递归调用 `createBT()` 函数分别构建左右子树。
接下来,我们可以分别实现二叉树的先序遍历和中序遍历:
```c
// 先序遍历
void preOrder(BTNode *root){
if(root == NULL){
return;
}
printf("%c ", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
// 中序遍历
void inOrder(BTNode *root){
if(root == NULL){
return;
}
inOrder(root->lchild);
printf("%c ", root->data);
inOrder(root->rchild);
}
```
先序遍历先输出根节点,然后递归输出左子树和右子树;中序遍历先递归输出左子树,然后输出根节点,最后递归输出右子树。
最后,我们可以在 `main()` 函数中调用以上函数,完成二叉树的创建和遍历:
```c
int main(){
BTNode *root = createBT();
printf("先序遍历:");
preOrder(root);
printf("\n中序遍历:");
inOrder(root);
return 0;
}
```
希望能对您有所帮助!
阅读全文