C语言二叉树的遍历示例介绍
程序员文章站
2022-06-16 13:05:54
在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,...
在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率。
#include<stdio.h> #include<stdlib.h> #define ok 1 #define error 0 #define overflow 3 typedef int status; typedef int boolean; typedef char telemtype; typedef struct bitnode{ telemtype data; struct bitnode *lchild, *rchild; }bitnode, *bitree; //创建二叉树函数 status createbitree(bitree &t){ telemtype ch; scanf("%c", &ch); getchar(); if(ch == ' '){ t = null;} else { if( !(t=(bitree)malloc(sizeof(bitnode))))(exit(overflow)); t->data = ch; printf("%c的左子树:", ch); createbitree(t->lchild); printf("%c的右子树:", ch); createbitree(t->rchild); } return ok; } //先序遍历函数 status preordertraverse(bitree t, status (* visit)(telemtype e)){ if(t){ if(visit(t->data)){ if(preordertraverse(t->lchild, visit)){ if(preordertraverse(t->rchild, visit)){ return ok; } } } return error; } else {return ok;} } //中序遍历函数 status inordertraverse(bitree t, status (* visit)(telemtype e)){ if(t){ if(preordertraverse(t->lchild, visit) ){ if(visit(t->data)){ if(preordertraverse(t->rchild, visit) ){ return ok; } } } return error; } else { return ok; } } //后序遍历函数 status posordertraverse(bitree t, status (* visit)(telemtype e)){ if(t){ if(preordertraverse(t->lchild, visit) ){ if(preordertraverse(t->rchild, visit) ){ if(visit(t->data)){return ok; } } } return error;} else {return ok; } } //输出二叉树函数 status printelement(telemtype e){ printf("%c",e); return ok; } //主函数 int main(){ bitree t; printf("输入根结点:"); createbitree(t); printf("先序遍历:\n"); preordertraverse(t, printelement); printf("\n"); printf("中序遍历:\n"); inordertraverse(t, printelement); printf("\n"); printf("后序遍历:\n"); posordertraverse(t, printelement); return 0; }
遍历操作有四种,其不同在于对根结点的访问顺序不同。在先序遍历中,首先访问根结点,然后递归地做左子树的先序遍历,然后是右子树的递归先序遍历。 在中序遍历中,递归地对左子树进行中序遍历,访问根结点,最后递归中序遍历右子树。在后序遍历中,递归地对左子树和右子树进行后序遍历,然后访问根结点。先序,中序,后序遍历就是对于根节点的访问顺序。
但无论哪种遍历方式,递归的方法是最简便,最直接,最简单的算法。
运行截图:
到此这篇关于c语言二叉树的遍历示例介绍的文章就介绍到这了,更多相关c语言二叉树内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
上一篇: Linux系统配置网络详细介绍
下一篇: Java十道入门易踩坑题分析前篇