首页 > 代码库 > SDUT-2136 数据结构实验之二叉树的建立与遍历
SDUT-2136 数据结构实验之二叉树的建立与遍历
题目描述
已知一个按先序序列输入的字符序列，如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树，最后求出叶子节点个数和二叉树深度。
输入
输入一个长度小于50个字符的字符串。
输出
输出共有4行：
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。
第1行输出中序遍历序列；
第2行输出后序遍历序列；
第3行输出叶子节点个数；
第4行输出二叉树深度。
示例输入
abc,,de,g,,f,,,
示例输出
cbegdfacgefdba35
#include<stdio.h>#include<stdlib.h>struct Tree{ char data; struct Tree *lchild, *rchild;}*t;int cnt=0;//用于统计叶子的数目struct Tree *creat(struct Tree *t)//根据先序建立二叉树{ char ch; ch = getchar(); if(ch==‘,‘) t = NULL; else { t = (struct Tree *)malloc(sizeof(struct Tree)); t->data =http://www.mamicode.com/ ch; t->lchild= creat(t->lchild); t->rchild= creat(t->rchild); } return t;}void Inorder(struct Tree *t)//中序遍历{ if(t!=NULL) { Inorder(t->lchild); printf("%c", t->data); Inorder(t->rchild); }}void Postorder(struct Tree *t)//后续遍历{ if(t!=NULL) { Postorder(t->lchild); Postorder(t->rchild); printf("%c", t->data); }}void leaf(struct Tree *t)//求叶子节点数目{ if(t) { if((t->lchild==NULL) && (t->rchild==NULL)) cnt++; leaf(t->lchild); leaf(t->rchild); }}int deep(struct Tree *t)// 求二叉树深度{ int l, r; if(!t) return 0; l = deep(t->lchild); r = deep(t->rchild); return l>r?l+1:r+1;}int main(){ struct Tree *root; root = creat(root); Inorder(root); printf("\n"); Postorder(root); printf("\n"); leaf(root); printf("%d\n", cnt); printf("%d\n", deep(root)); return 0;}
SDUT-2136 数据结构实验之二叉树的建立与遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。