Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

用c语言实现前序创建二叉树(递归),分别用前序,中序,后序遍历,以及分别输出节点个数和叶子节点个数

孤独丶姿态 2019-11-04 19:15:00 阅读数:93 评论数:0 点赞数:0 收藏数:0

本人c语言小白一枚,近期在学习数据结构(c语言版),特写此随笔,做一些总结和分享,如有不当之处,请各位技术大牛指点

首先我们用一个结构体来抽象树的结点,代码如下(这里我们存放的数据为char型,大家可以根据自己不同的数据来自己定义,也可以在一开始用typedef特别定义一个类型,接下来就是两个指针,

用来指向左儿子和右儿子)

struct tnode{
char data;
struct tnode *lchild,*rchild;
};

 

一,如何前序创建一颗二叉树

首先简述一下前序创建二叉树的算法:其实前序创建一颗二叉树的算法非常简单,这里我们要用到递归的思想,先给根节点赋值,然后再依次给左子树的根节点和右子树的根节点赋值,用递归的思想将整颗树赋值。(在这里我们用‘#’来表示某个结点为空),代码如下:

struct tnode * creatTree(struct tnode *head){
char e;
scanf("%c",&e);
fflush(stdin);
if(e != '#'){
head = (struct tnode *)malloc(sizeof(struct tnode));//先开辟空间
head ->data = e;//判断不是'#'后,给根节点赋值
head ->lchild = NULL;
head ->rchild = NULL;
//依次把左儿子和右儿子调用该方法进行赋值 head
->lchild = creatTree(head->lchild); head ->rchild = creatTree(head->rchild); } return head; }

这样我们就可以成功创建一颗二叉树

二,前序遍历二叉树

简述一下前序遍历二叉树的算法:(这里同样也要用到递归的思想),首先拜访头结点,然后拜访左子树,再拜访右子树,代码如下:

void preorderTree(struct tnode *head){
//先拜访头结点
printf("%c",head->data);
//再走左子树
if(head->lchild != NULL){//判断左子树是不是为空
preorderTree(head->lchild);
}
if(head ->rchild !=NULL){//判断右子树是不是为空
//再走右子树
preorderTree(head->rchild);
}
return;
}

三,后序遍历二叉树:

和前序遍历二叉树类似,只是我们要最后拜访根节点,同样用到了递归的思想,代码如下:

void postorderTree(struct tnode *head){
//先左子树
if(head->lchild != NULL){
postorderTree(head->lchild);
}
//再右子树
if(head->rchild != NULL){
postorderTree(head->rchild);
}
//最后根节点
printf("%c",head->data);
return;
}

四,中序遍历二叉树:

和前两种类似,我们先拜访左子树,再拜访根节点,最后拜访右子树,(同样用到了递归的思想)代码如下:

 

void inorderTree(struct tnode *head){
//先走左子树
if(head->lchild !=NULL){
inorderTree(head->lchild);
}
//再走头结点
printf("%c",head->data);
//再走右子树
if(head->rchild != NULL){
inorderTree(head->rchild);
}
return;
}

 

 

 

五,输出节点的个数

思路:我们先在main函数里面定义一个计数器,在遍历的过程中,只要节点不是null,我们就让这个计数器++,这样就可以实现记录节点个数的功能啦,(在这里我们同样又用到了递归的思想,递归真的好重要的,到处都是递归),代码如下:(这里特别要注意的地方就是我们在main函数里面定义的计数器,一定要把地址给我们的函数,所以我们函数里面的形参是个int型的指针)

int sumNode(struct tnode *head,int *count){
if(head == NULL){//判断根节点是否为空
return *count + ;
}else{
//在这里我们用的是前序遍历二叉树的思想,先走根节点,在走左右子树
*count += ;
sumNode(head->lchild,count);
sumNode(head->rchild,count);
}
return *count;
}

 

六,输出叶子节点的个数

int leaf(struct tnode * root)
{
if (root == NULL)//如果根节点为空,则返回空
return ;
else if (root->lchild == NULL&&root->rchild == NULL)//如果左孩子和右孩子同时为空,则叶子节点的数加+1
return ;
else
return leaf(root->lchild) + leaf(root->rchild);//一棵树的叶子节点由它的左孩子和右孩子的叶子节点决定的。

}

 

 

以上就是全部内容,如有疑问和您的宝贵建议,尽情可以在评论中留言

 

 

 

 

---恢复内容结束---

版权声明
本文为[孤独丶姿态]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/alone-wolf/p/11794089.html