C语言数据结构二叉树简单应用
C语言数据结构二叉树简单应用
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree），接下来我就在这里给大家介绍一下二叉树在算法中的简单使用：
我们要完成总共有
（1）二叉树的创建
（2）二叉树的先中后序递归遍历
（3）统计叶子结点的总数
（4）求树的高度
（5）反转二叉树
（6）输出每个叶子结点到根节点的路径
（7）输出根结点到每个叶子结点的路径。
定义二叉树结点类型的结构体
typedefstructnode{
chardata;
structnode*Lchild;
structnode*Rchild;
}BiTNode,*BiTree;
intcnt=0;//统计叶子节点个数
二叉树的创建
BiTNode*Create(){//二叉树的先序建立
charch;
BiTNode*s;
ch=getchar();
if(ch=='#')erchashu
returnNULL;
s=(BiTNode*)malloc(sizeof(BiTNode));
s->data=ch;
s->Lchild=Create();
s->Rchild=Create();
returns;
}
二叉树的先序、中序、后序递归遍历
voidPreOrder(BiTreeroot){//前序遍历
if(root){
printf("%c",root->data);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
voidInOrder(BiTreeroot){//中序遍历
if(root){
InOrder(root->Lchild);
printf("%c",root->data);
InOrder(root->Rchild);
}
}
voidPostOrder(BiTreeroot){//后序遍历
if(root){
PostOrder(root->Lchild);
PostOrder(root->Rchild);
printf("%c",root->data);
}
}
统计叶子结点个数：
voidLeafCountNode(BiTreeroot){//统计叶子结点个数
if(root){
if(!root->Lchild&&!root->Rchild)
cnt++;
LeafCountNode(root->Lchild);
LeafCountNode(root->Rchild);
}
}
输出各个叶子结点值：
voidIInOrder(BiTreeroot){//输出各个叶子结点值
if(root){
IInOrder(root->Lchild);
if(!root->Lchild&&!root->Rchild)
printf("%c",root->data);
IInOrder(root->Rchild);
}
}
求树的高度：
intPostTreeDepth(BiTreeroot){//求树的高度
inth1,h2,h;
if(root==NULL){
return0;
}
else{
h1=PostTreeDepth(root->Lchild);
h2=PostTreeDepth(root->Rchild);
h=(h1>h2?h1:h2)+1;
returnh;
}
}
反转二叉树：
voidMirrorTree(BiTreeroot){//二叉树镜像树
BiTreet;
if(root==NULL)
return;
else{
t=root->Lchild;
root->Lchild=root->Rchild;
root->Rchild=t;
MirrorTree(root->Lchild);
MirrorTree(root->Rchild);
}
}
输出每个叶子结点到根节点的路径：
voidOutPutPath(BiTreeroot,charpath[],intlen){//输出每个叶子结点到根节点的路径
if(root){
if(!root->Lchild&&!root->Rchild){
printf("%c",root->data);
for(inti=len-1;i>=0;i--)
printf("%c",path[i]);
printf("\n");
}
path[len]=root->data;
OutPutPath(root->Lchild,path,len+1);
OutPutPath(root->Rchild,path,len+1);
}
}
输出根到每个叶子结点的路径：
voidPrintPath(BiTreeroot,charpath[],intl){//输出根到每个叶子结点的路径
intlen=l-1;
if(root){
if(root->Lchild==NULL&&root->Rchild==NULL){
path[len]=root->data;
for(inti=9;i>=len;i--)
printf("%c",path[i]);
printf("\n");
}
path[len]=root->data;
PrintPath(root->Lchild,path,len);
PrintPath(root->Rchild,path,len);
}
}
测试代码：
intmain(void){
inth,len;
charpath[20];
BiTreeroot;
root=Create();
//PreOrder(root);
//printf("\n");
//InOrder(root);
//printf("\n");
//PostOrder(root);
//printf("\n");
//LeafCountNode(root);
//printf("叶子结点个数为:%d\n",cnt);
//IInOrder(root);
h=PostTreeDepth(root);
printf("树的高度为:High=%d\n",h);
//PrintTree(root,0);
//MirrorTree(root);
//PrintTree(root,0);
//OutPutPath(root,path,0);
//PrintPath(root,path,10);
return0;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！