用c语言编写一个程序,用链式存储方式构造二叉树,实现二叉树的基本操作(假设树的元素类型为char),并在此基础上设计一个主程序完成如下功能: (1)编写CreatBiTree函数,创建二叉树T; (2)编写PreOrder函数,先序遍历二叉树 (3)编写InOrder函数,中序遍历二叉树; (4)编写PostOrder函数,后序遍历二叉树; (5)编写PostTreeDepth函数,求二叉树的深度
时间: 2023-11-27 11:49:04 浏览: 190
C语言编写的二叉树基本操作
以下是用链式存储方式构造二叉树的C语言程序,实现二叉树的基本操作:
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
char data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode, *BiTree;
//创建二叉树
void CreateBiTree(BiTree *T)
{
char ch;
scanf("%c", &ch);
if(ch == '#'){
*T = NULL;
}
else{
*T = (TreeNode*)malloc(sizeof(TreeNode));
(*T)->data = ch;
CreateBiTree(&((*T)->left));
CreateBiTree(&((*T)->right));
}
}
//先序遍历二叉树
void PreOrder(BiTree T)
{
if(T){
printf("%c ", T->data);
PreOrder(T->left);
PreOrder(T->right);
}
}
//中序遍历二叉树
void InOrder(BiTree T)
{
if(T){
InOrder(T->left);
printf("%c ", T->data);
InOrder(T->right);
}
}
//后序遍历二叉树
void PostOrder(BiTree T)
{
if(T){
PostOrder(T->left);
PostOrder(T->right);
printf("%c ", T->data);
}
}
//求二叉树的深度
int PostTreeDepth(BiTree T)
{
int left_depth, right_depth;
if(T == NULL){
return 0;
}
left_depth = PostTreeDepth(T->left);
right_depth = PostTreeDepth(T->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
int main()
{
BiTree T;
printf("请输入一棵二叉树(用#表示空节点):");
CreateBiTree(&T);
printf("先序遍历结果:");
PreOrder(T);
printf("\n中序遍历结果:");
InOrder(T);
printf("\n后序遍历结果:");
PostOrder(T);
printf("\n二叉树的深度为:%d\n", PostTreeDepth(T));
return 0;
}
```
在主程序中,首先输入一棵二叉树,然后分别进行先序、中序、后序遍历,并输出二叉树的深度。
阅读全文