二叉树的链式存储结构创建(前序法) 二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历 主函数功能菜单创建
时间: 2023-12-01 12:41:06 浏览: 94
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
5星 · 资源好评率100%
二叉树的链式存储结构可以通过定义一个结构体来实现,结构体中包含一个数据域和两个指向左右子树的指针。具体实现如下:
```
typedef struct TreeNode{
int data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode, *Tree;
Tree createTree(){
int data;
scanf("%d", &data);
if(data == -1){ // -1表示空节点
return NULL;
}
Tree root = (Tree)malloc(sizeof(TreeNode));
root->data = data;
root->left = createTree();
root->right = createTree();
return root;
}
```
以上代码实现了二叉树的链式存储结构的创建,其中createTree()函数使用前序遍历的方式输入二叉树的节点数据,-1表示空节点。
接下来是二叉树的遍历,分别实现前序、中序和后序遍历:
```
void preOrder(Tree root){
if(root == NULL){
return;
}
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Tree root){
if(root == NULL){
return;
}
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
void postOrder(Tree root){
if(root == NULL){
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
```
以上代码分别实现了前序、中序和后序遍历,其中preOrder()函数实现了前序遍历,inOrder()函数实现了中序遍历,postOrder()函数实现了后序遍历。
最后是主函数功能菜单的创建,可以使用switch语句实现:
```
int main(){
Tree root = NULL;
int choice;
do{
printf("1. 创建二叉树\n");
printf("2. 前序遍历\n");
printf("3. 中序遍历\n");
printf("4. 后序遍历\n");
printf("0. 退出\n");
scanf("%d", &choice);
switch(choice){
case 1:
printf("请输入二叉树的节点数据,-1表示空节点:\n");
root = createTree();
break;
case 2:
printf("前序遍历结果为:");
preOrder(root);
printf("\n");
break;
case 3:
printf("中序遍历结果为:");
inOrder(root);
printf("\n");
break;
case 4:
printf("后序遍历结果为:");
postOrder(root);
printf("\n");
break;
case 0:
printf("程序已退出!\n");
break;
default:
printf("输入有误,请重新输入!\n");
break;
}
}while(choice != 0);
return 0;
}
```
以上代码实现了一个简单的二叉树遍历程序,用户可以通过菜单选择需要的功能。注意,在实际使用中,需要在程序结束时释放二叉树的内存空间。
阅读全文