概述:
二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对应位置即可。
代码如下:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//二叉树结点
typedef struct BTnode
{
int data;
struct BTnode *lchild,*rchild;
}BTnode;
BTnode* BuyNode(int x)
{
//创建树的结点空间,动态分配。
BTnode* node =(BTnode*)malloc(sizeof(BTnode));
//给结点赋值,指针域置空
node->data=x;
node->lchild=NULL;
node->rchild=NULL;
return node;
}
//创建二叉树
BTnode* CreatTree()
{
//创建树的结点
BTnode* node1 =BuyNode(1);//因为BuyNode是动态分配的空间,因此用指针接收
BTnode* node2 =BuyNode(2);
BTnode* node3 =BuyNode(3);
BTnode* node4 =BuyNode(4);
BTnode* node5 =BuyNode(5);
//手动链接起来。
node1->lchild=node2;
node1->rchild=node3;
node2->lchild=node4;
node2->rchild=node5;
//链接完毕,返回头指针,即根结点
return node1;
}
//打印树-前序遍历
void PreOrder(BTnode* root)
{
if(root == NULL)
{
printf("# ");
return;//返回调用的上一级
}
printf("%d ",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
void InOrder(BTnode* root)//中序遍历
{
if(root == NULL)
{
printf("# ");
return;//返回调用的上一级
}
InOrder(root->lchild); //左
printf("%d ",root->data);//根
InOrder(root->rchild);//右
}
void PostOrder(BTnode* root)//后序遍历
{
if(root == NULL)
{
printf("# ");
return;//返回调用的上一级
}
PostOrder(root->lchild);//左
PostOrder(root->rchild);// 右
printf("%d ",root->data);//根
}
//计算树的结点,分治思想,分工,最后汇总。
int BTtreeSize(BTnode* root)
{
if(root ==NULL)//树是空的,就返回0
return 0;
else//不是空的,就进行左右子树遍历再加1,因为要给本身加上。空根不加一,但这里非空,必定+1;
{
//递归到叶子节点时,叶子节点的左右子树都为空,返回0,0+0+1=1,因此叶子节点再往上一层返回即可。
return BTtreeSize(root->lchild)+BTtreeSize(root->rchild)+1;
}
}
//计算树的叶子节点
int LeafSizes(BTnode* root)
{
//是空根就返回0
if(root ==NULL)
return 0;
//符合叶子结点特征,即结点的左右子树均为空,则返回1,即记录上
if(root->lchild ==NULL && root->rchild==NULL )
return 1;
else
//都不符合,便进入左右子树,进行递归计算,最后汇总即可。
return LeafSizes(root->lchild)+LeafSizes(root->rchild);
//实在不明白,画个递归图,就明白了。
}
int main()
{
BTnode* root=CreatTree();
//遍历递归打印时,每个结点调用结束,销毁空间,返回上一级调用位置。
//直到所有结点遍历结束,临时空间逐个销毁。
printf("前序遍历:");
PreOrder(root);
printf("\n中序遍历:");
InOrder(root);
printf("\n后序遍历:");
PostOrder(root);
//计算树的结点
int count=BTtreeSize(root);
printf("\n树有%d个结点",count);
int leafcount=LeafSizes(root);
printf("\n树有%d个叶子结点",leafcount);
return 0;
}
结果:
文章来源:https://www.toymoban.com/news/detail-673674.html
文章来源地址https://www.toymoban.com/news/detail-673674.html
到了这里,关于14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!