用c语言代码建立二叉树的二叉链表存储结构,要求编程实现如下功能:1假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树2对二叉树进行先序、中序和后序遍历操作,并输出遍历序列
时间: 2024-01-23 17:10:05 浏览: 107
好的,我知道了。下面是用 C 语言代码建立二叉树的二叉链表存储结构,并实现遍历操作的程序:
```c
#include<stdio.h>
#include<stdlib.h>
//定义二叉树结点结构体
typedef struct TreeNode{
char data; //结点数据
struct TreeNode *left; //左子树指针
struct TreeNode *right; //右子树指针
}TreeNode, *pTreeNode;
//用先序遍历序列建立二叉树
pTreeNode createTree(){
char ch;
scanf("%c", &ch); //读入一个字符
if(ch == '#') //如果是 #,表示该结点为空
return NULL;
pTreeNode p = (pTreeNode)malloc(sizeof(TreeNode)); //创建新结点
p->data = ch; //存储数据
p->left = createTree(); //递归创建左子树
p->right = createTree(); //递归创建右子树
return p; //返回当前结点的指针
}
//先序遍历二叉树
void preOrder(pTreeNode root){
if(root == NULL)
return;
printf("%c ", root->data); //访问当前结点
preOrder(root->left); //递归遍历左子树
preOrder(root->right); //递归遍历右子树
}
//中序遍历二叉树
void inOrder(pTreeNode root){
if(root == NULL)
return;
inOrder(root->left); //递归遍历左子树
printf("%c ", root->data); //访问当前结点
inOrder(root->right); //递归遍历右子树
}
//后序遍历二叉树
void postOrder(pTreeNode root){
if(root == NULL)
return;
postOrder(root->left); //递归遍历左子树
postOrder(root->right); //递归遍历右子树
printf("%c ", root->data); //访问当前结点
}
int main(){
printf("请输入一棵二叉树的完整先序遍历序列(以#表示空结点):\n");
pTreeNode root = createTree(); //根据输入建立二叉树
printf("先序遍历序列为:");
preOrder(root); //先序遍历二叉树
printf("\n中序遍历序列为:");
inOrder(root); //中序遍历二叉树
printf("\n后序遍历序列为:");
postOrder(root); //后序遍历二叉树
printf("\n");
return 0;
}
```
程序中,先定义了一个二叉树结点结构体 `TreeNode`,包含三个成员:`data` 表示结点数据,`left` 表示左子树指针,`right` 表示右子树指针。然后,用 `typedef` 定义了 `pTreeNode` 类型指针,方便后续使用。
接着,定义了一个 `createTree()` 函数,用于根据输入的先序遍历序列建立二叉树。程序遇到一个字符时,如果是 `#`,表示该结点为空,返回 `NULL`;否则,创建一个新结点,存储该字符,并递归调用 `createTree()` 函数创建左右子树,最后返回当前结点的指针。
然后,定义了三个遍历函数 `preOrder()`、`inOrder()`、`postOrder()`,分别用于先序、中序、后序遍历二叉树。遍历过程中,如果当前结点为空,直接返回;否则,先访问当前结点,然后递归遍历左右子树。
最后,在 `main()` 函数中,先提示用户输入一棵二叉树的完整先序遍历序列,然后调用 `createTree()` 函数建立二叉树。接着,先序、中序、后序遍历二叉树,并输出遍历序列。
注意,程序中用 `scanf("%c", &ch)` 读入字符时,需要注意缓冲区的问题。可以在读入字符后加一个空格,将回车符消耗掉,或者用 `fflush(stdin)` 清空缓冲区。否则,可能会出现读入空字符的情况,导致程序出错。
以上就是用 C 语言代码建立二叉树的二叉链表存储结构,并实现遍历操作的程序。
阅读全文