#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "string.h"
typedef char DataType;
//前序输入的测试数据 data ABC***DE*G**F**
//定义二叉树结构体类型
typedef struct btree
{
DataType data;
struct btree *lchild,*rchild;
}BTree,*PTree;
/*层次化初始二叉树 比较牛,PS:层次化输出参考图的广度优先遍历算法*/
void levelCreateBTree(PTree *t,char *v,int i,int l)
{
if(i>l)*t=NULL;
else{
*t = (PTree)malloc(sizeof(BTree));
(*t)->data=v[i];
levelCreateBTree(&(*t)->lchild,v,i*2+1,l);
levelCreateBTree(&(*t)->rchild,v,i*2+2,l);
}
}
//二叉树前序输入初始化
void preCreateBTree(PTree *t)
{
char c;
c=getchar();
if(c=='*')
{
*t=NULL;return;
}
*t=(PTree)malloc(sizeof(BTree));
(*t)->data=c;
preCreateBTree(&((*t)->lchild));
preCreateBTree(&((*t)->rchild));
}
//二叉树前序后序输入初始化 // 测试数据 abdg cefh dgba echf
//pre 前序输入字符串 pres 前序起始长度 pree 前序终止长度 in 中序输入字符串 ins 中序起始长度 ine 中序终止长度
void preInCreateBTree1(PTree *t,char *pre,int pres,int pree,char *in,int ins,int ine)
{
int i;
if(pres>pree||ins>ine)
{
*t=NULL;
}else
{
*t=(PTree)malloc(sizeof(BTree));
(*t)->data=pre[pres];
for(i=ins;i<=ine;i++)
{
if(in[i]==pre[pres])
{
preInCreateBTree1(&(*t)->lchild,pre,pres+1,pres+i-ins,in,ins,i-1);
preInCreateBTree1(&(*t)->rchild,pre,pres+i-ins+1,pree,in,i+1,ine);
break;
}
}
}
}
//二叉排序树初始化
void insertBST(PTree *t,int c)
{
PTree f,p;
p=(*t);
//判定输入值存在的同时,找到数据插入的位置
while(p!=NULL)
{
printf("p->data=%d\n",p->data);
printf("c=%d\n",c);
if(p->data==c)
{
printf("输入的值已经存在!\n");return;
}
f=p;
//递归到最后p是一空值 f为其父节点
p=(c<p->data)?p->lchild:p->rchild;
}
p=(PTree)malloc(sizeof(BTree));
p->data=c;
p->lchild=NULL;p->rchild=NULL;//比较关键
if(*t==NULL)
{
*t=p;
}else
{
if(c<f->data)
{
f->lchild=p;
}else
{
f->rchild=p;
}
}
}
void createBST(PTree *t)
{
int d;
scanf("%d",&d);
if(d==-9999)return;
do{
insertBST(t,d);
scanf("%d",&d);
}while(d!=-9999);
}
/*二叉排序树*/
void BST(PTree *t)
{
int c;
PTree f,p;
scanf("%d",&c);
if(c==-9999)return;//判定输入
do
{
//判定输入值存在的同时,找到数据插入的位置
p=(*t);//归位
while(p!=NULL)
{
if(p->data==c)
{
printf("输入的值已经存在!\n");return;
}
f=p;
//递归到最后p是一空值 f为其父节点
p=(c<p->data)?p->lchild:p->rchild;
}
p=(PTree)malloc(sizeof(BTree));
p->data=c;
p->lchild=NULL;p->rchild=NULL;
if(*t==NULL)
{
*t=p;
}else
{
if(c<f->data)
{
f->lchild=p;
}else
{
f->rchild=p;
}
}
scanf("%d",&c);
}while(c!=-9999);
}
//二叉树前序遍历
void preOrder(PTree t)
{
if(t==NULL)return;
printf("%c",t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
//二叉树中序遍历
void inOrder(PTree t)
{
if(t==NULL)return;
inOrder(t->lchild);
printf("%c",t->data);
inOrder(t->rchild);
}
//二叉树后序遍历
void postOrder(PTree t)
{
if(t==NULL)return;
postOrder(t->lchild);
postOrder(t->rchild);
printf("%c",t->data);
}
//求叶子节点数
int leafNum(PTree t)
{
int l,r;
if(!t)return 0;
else if(t->lchild==NULL&&t->rchild==NULL) return 1;//判定叶子
else
{
l=leafNum(t->lchild);
r=leafNum(t->rchild);
return l+r;
}
}
//求二叉树中叶子结点的个数
int nodeNum(PTree t)
{
int l,r;
if(t==NULL)return 0;//空树没有叶子节点
else if(t->lchild==NULL&&t->rchild==NULL) return 1;//判定叶子(只有一个根结点)
else
{
l=nodeNum(t->lchild);
r=nodeNum(t->rchild);
return l+r+1;
}
}
//求二叉树中度为2的结点数
int node2Num(PTree t)
{
if(t==NULL)return 0;
else
{
if(t->lchild&&t->rchild)return 1+node2Num(t->lchild)+node2Num(t->rchild);
else
{
if(t->lchild&&!t->rchild)return node2Num(t->lchild);
else return node2Num(t->rchild);
}
}
}
//度为1的结点数
int node1Num(PTree t)
{
if(t==NULL)return 0;
if((t->lchild!=NULL&&t->rchild==NULL)||(t->lchild==NULL&&t->rchild!=NULL))return 1;//判定度为1结点
return node1Num(t->lchild)+node1Num(t->rchild);
}
//求高度(深度)根节点深度为1
int height(PTree t)
{
int l,r;
if(t==NULL)return 0;
else if(t->lchild==NULL&&t->rchild==NULL) return 1;//判定叶子
else
{
l=height(t->lchild);
r=height(t->rchild);
return (l>r?l:r)+1;
}
}
//交换二叉树的左右子树
void exchangeBtree(PTree t)
{
PTree temp;
if(t)
{
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
exchangeBtree(t->lchild);
exchangeBtree(t->rchild);
}
}
void main()
{
PTree p=NULL;
int i,l;
char a[100],b[100];
// 前序中序输入测试
printf("前序输入:\n");
gets(a);
l=strlen(a);
levelCreateBTree(&p,a,0,l-1);
// printf("中序输入:\n");
// gets(b);
// preInCreateBTree1(&p,a,0,strlen(a)-1,b,0,strlen(b)-1);*/
// preCreateBTree(&p);
// createBST(&p);
// BST(&p);
printf("层次输出:\n");
levelOutputBtree(p,0);
/* printf("前序输出:\n");
preOrder(p);
printf("\n");
printf("中序输出:");
inOrder(p);
printf("\n");
printf("后续输出:");
postOrder(p);
printf("\n");
printf("树的高度为:%d\n",height(p));
printf("节点数为:%d\n",nodeNum(p));
printf("度为1结点数:%d\n",node1Num(p));
printf("度为2结点数:%d\n",node2Num(p));
printf("叶子节点数为:%d\n",leafNum(p));
exchangeBtree(p);
printf("交换后后续输出:");
postOrder(p);
*/
}
分享到:
相关推荐
数据结构C语言树二叉树详细举例介绍PPT学习教案.pptx
C语言二叉树PPT学习教案.pptx
C语言版数据结构中二叉树的查找算法,对学习数据结构的新手有帮助。
数据结构c语言描述二叉树应用习题及答案.docx
一个用c语言描述的数据结构哦中的二叉树,帮助读者很好的学习有关数据结构中的知识
数据结构的重要部分——二叉树,这里主要是完成二叉树的建立、前中后序遍历(其中中序和后序遍历以非递归的形式完成)、交换子树、计算树的高度等操作,学习二叉树的小伙伴可以来看看噢
C语言详细介绍二叉树,及其遍历方法。值得学习
一个经典的C语言二叉树结构源程序,非常适合学习数据结构的朋友们,也适合自学者。绝对无误,在VC++6.0上运行通过。
数据结构C语言树和二叉树PPT学习教案.pptx
C语言二叉树PPT课件.pptx
C语言二叉树程序,初学者可以学习一下,很有帮助的
算法拙劣,仅供初学者做练习,(本人也是初学者,自学数据结构,刚好学到这二叉树这一章,搞几个二叉的例题,却不知道其构造形状,想调用图形API做个美观点的,却有点偏离本章的学习目的,只好用字符打印, ...
线性链表和二叉树的c语言实现,对学习数据结构的同学来说可以好好参考
数据结构C语言版-二叉树的三叉链表存储表示.doc
递归方法建立二叉树,利用递归方法建立二叉树,简单快捷,作为递归学习再好不过,书上关于建立二叉树的方法介绍很少
数据结构C语言树和二叉树PPT课件.pptx
主要介绍了C语言二叉树的三种遍历方式的实现及原理,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
采用C语言对二叉树的前序、中序、后序、层序(使用队列)遍历方法进行了实现,含一个.c文件和一个.h文件,程序的结构比较清晰,对学习二叉树和队列的相关技术具有一定参考意义(有问题可留言交流)
学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习。等二叉树结构了解...
C语言建立二叉树,课程用模拟二叉树,非可视化操作,仅供交流与学习。