当前位置：首页 > news >正文

【C语言】二叉树创建（结构体，先序遍历，中序遍历，后续遍历）

news 2025/7/28 21:53:12

二叉树的创建：首先先定义一个结构体，里面包含数据（data），指向左子树的指针（L），指向右子树的指针（R）三个部分
在创建树的函数中，首先先输入一个数，且当输入'#'的时候，表示这个位置没有值输入，返回NULL；成功输入值后，用malloc申请一个结点，B->data = data；然后再次调用创建函数（函数本身），但是是这个结点的左子树B->L = tree_create()；以此类推就能成功创建一颗树了。
3种遍历方法结构基本差不多，无非是输出的时机不一样，先序是根左右，中序是左根右，后序是左右根。遍历即可输出值

//bitree.h
#ifndef BITREE_H
#define BITREE_H#include<myhead.h>typedef char datatype;typedef struct Node
{datatype data;struct Node *L;struct Node *R;
}Node,*BiTreePtr;//创建树
BiTreePtr tree_create();//先序遍历树
void prio_order(BiTreePtr B);//中序遍历树
void in_order(BiTreePtr B);//后序遍历树
void post_order(BiTreePtr B);#endif

//bitree.c
#include"bitree.h"//创建树
BiTreePtr tree_create()
{//输入一个数char data = '0';scanf("%c",&data);getchar();//如果输入#代表这个位置没有数放入,返回NULLif(data == '#'){return NULL;}//申请树的空间,如果不是NULL,就要申请结点BiTreePtr B = (BiTreePtr)malloc(sizeof(Node));if(NULL == B)     //判断是否成功创建{printf("创建失败");return NULL;}//执行到这里说明树申请成功B->data = data;    //赋值给节点B->L = tree_create(); //创建左子树B->R = tree_create(); //创建右子树return B;
}//先序遍历树
void prio_order(BiTreePtr B)
{//判断逻辑if(NULL == B){return;     //递归出口}printf("%c\t",B->data);  //先打印出根节点prio_order(B->L);     //遍历左子树prio_order(B->R);     //遍历右子树
}//中序遍历树
void in_order(BiTreePtr B)
{//判断逻辑if(NULL == B){return;     //递归出口}in_order(B->L);     //遍历左子树printf("%c\t",B->data);  //先打印出根节点in_order(B->R);     //遍历右子树}//后序遍历树
void post_order(BiTreePtr B)
{//判断逻辑if(NULL == B){return;     //递归出口}post_order(B->L);     //遍历左子树post_order(B->R);     //遍历右子树printf("%c\t",B->data);  //先打印出根节点}

//main.c
#include"bitree.h"#include <myhead.h>int main(int argc, 	const char *argv[])
{BiTreePtr B = tree_create();if(NULL == B){printf("创建失败\n");return -1;}else{printf("创建成功\n");}printf("先序遍历为:");prio_order(B);printf("\n");printf("中序遍历为:");in_order(B);printf("\n");printf("后序遍历为:");post_order(B);printf("\n");return 0;
}