用c语言代码生成二叉链表来实现二叉树的存储,编写以下算法: (1)二叉树的创建 (2)二叉树的前序、中序、后序、层次遍历 (3)完善main()函数的编写,调用以上算法,验证算法的正确性
时间: 2024-06-13 19:03:58 浏览: 10
二叉链表是一种二叉树的链式存储结构,每个结点包含三个域:数据域、左孩子指针域和右孩子指针域。下面是用C语言代码生成二叉链表来实现二叉树的存储的算法:
(1)二叉树的创建
```
typedef struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void CreateBiTree(BiTree *T){
char ch;
scanf("%c", &ch);
if(ch == '#'){
*T = NULL;
}
else{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
```
(2)二叉树的前序、中序、后序、层次遍历
```
//前序遍历
void PreOrderTraverse(BiTree T){
if(T){
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
//层次遍历
void LevelOrderTraverse(BiTree T){
if(!T){
return;
}
BiTree queue[1000];
int front = 0, rear = 0;
queue[rear++] = T;
while(front < rear){
BiTree p = queue[front++];
printf("%c ", p->data);
if(p->lchild){
queue[rear++] = p->lchild;
}
if(p->rchild){
queue[rear++] = p->rchild;
}
}
}
```
(3)完善main()函数的编写,调用以上算法,验证算法的正确性
```
int main(){
BiTree T;
printf("请输入二叉树的前序遍历序列,其中#表示空结点:\n");
CreateBiTree(&T);
printf("前序遍历结果为:");
PreOrderTraverse(T);
printf("\n中序遍历结果为:");
InOrderTraverse(T);
printf("\n后序遍历结果为:");
PostOrderTraverse(T);
printf("\n层次遍历结果为:");
LevelOrderTraverse(T);
printf("\n");
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)