软件下载 | 资讯教程 | 最近更新 | 下载排行 | 一键转帖 | 发布投稿
您的位置:最火下载站 > 电脑教程 > 编程开发 > C/C++开发 > C/C++ 二叉树的建立,遍历等基本操作

C/C++ 二叉树的建立,遍历等基本操作

二叉树的建立,遍历等基本操作

[C/C++/Objective-C]代码片段:

/**********************************************************************
* Description:先序创建二叉树,遍历等操作
* Author:099074345
* Datetime:2011-4-21 21:54
* Compile Environment:windowsXP sp3+VC6.0
**********************************************************************/

#include "stdio.h"
#include "stdlib.h"

//*********************************************************************
//定义二叉树的结构
typedef struct tree{
char data;
struct tree *lchild;
struct tree *rchild;
}*Ptree,Dtree;

//*********************************************************************
//先序创建二叉树
Ptree createTree()
{
char ch;
Ptree t;
ch=getchar();
if(ch=='#')
t=NULL;
else
{
t=(Ptree)malloc(sizeof(Dtree));
t->data=ch;
t->lchild=createTree();
t->rchild=createTree();
}
return t;
}
//***********************************************************************
//定义队列
typedef struct queue_{
Ptree data[100];
int front,rear;
}Dqueue,*Pqueue;
//***********************************************************************
//初始化队列
Pqueue initQueue()
{
Pqueue p;
p=(Pqueue)malloc(sizeof(Dqueue));
if(p)
{
p->front=0;
p->rear=0;
}
return p;
}
//***********************************************************************
//判断队列是否为空
int emptyQueue(Pqueue p)
{
if(p->front==p->rear)
return 1;
else
return 0;
}
//***********************************************************************
//入队
void inQueue(Pqueue p,Ptree t)
{
p->rear=(p->rear+1)%100;
p->data[p->rear]=t;
}
//***********************************************************************
//出队
void outQueue(Pqueue p,Ptree* t)
{
p->front=(p->front+1)%100;
*t=p->data[p->front];
}
//***********************************************************************
//层次遍历
void levelOrder(Ptree t)
{
Ptree p=t;
Pqueue Q;
if(p)
{
Q=initQueue();//初始化队列
printf("%c",p->data);
inQueue(Q,p);
while(!emptyQueue(Q))//当队列不为空
{
outQueue(Q,&p);//出队
if(p->lchild)
{
printf("%c",p->lchild->data);
inQueue(Q,p->lchild);//进队
}
if(p->rchild)
{
printf("%c",p->rchild->data);
inQueue(Q,p->rchild);//进队
}
}
}
}
//*********************************************************************
//先序遍历
void preOrder(Ptree t)
{
if(t)
{
printf("%c",t->data);
preOrder(t->lchild);
preOrder(t->rchild);
}
}

//***********************************************************************
//中序遍历
void intOrder(Ptree t)
{
if(t)
{
intOrder(t->lchild);
printf("%c",t->data);
intOrder(t->rchild);
}
}

//***********************************************************************
//后序遍历
void postOrder(Ptree t)
{
if(t)
{
postOrder(t->lchild);
postOrder(t->rchild);
printf("%c",t->data);
}
}
//***********************************************************************
//求叶子数
int leafCount(Ptree t)
{
int count1,count2;
if(t==NULL)
return 0;
else
{
if(t->lchild==NULL&&t->rchild==NULL)
return 1;
else
{
count1=leafCount(t->lchild);
count2=leafCount(t->rchild);
return count1+count2;
}
}
}
//***********************************************************************
//求二叉树每层节点的个数,保存到数组num中
void levelCount(Ptree t,int l,int num[])
{
if(t)
{
num[l]++;
levelCount(t->lchild,l+1,num);
levelCount(t->rchild,l+1,num);
}
}
//***********************************************************************
//求二叉树的高度
int heightTree(Ptree t)
{
int h1,h2;
if(t==NULL)
return 0;
else
{
h1=heightTree(t->lchild);
h2=heightTree(t->rchild);
if(h1>h2)
return h1+1;
else
return h2+1;
}
}
//*********************************************************************
//主函数
int main()
{
int num[10]={0};
int height;
int i;
Ptree t;

t=createTree();//先序创建二叉树

printf("后序遍历");//后续遍历
postOrder(t);
printf("\n");

printf("层次遍历");//层次遍历
levelOrder(t);
printf("\n");

height=heightTree(t);//数的深度
printf("深度:%d\n",height);

levelCount(t,1,num);//每层节点数
for(i=1;i<=height;i++)
printf("第%d层个数:%d\n",i,num[i]);

printf("叶子总数:%d\n",leafCount(t));//叶子数
return 0;
}

    相关阅读
    栏目导航
    推荐软件