返回顶部

收藏

二叉树遍历算法

更多

建立 遍历 二叉树的的深度 叶子个数

[C/C++]代码

include "stdio.h"
#include "stdlib.h"
#define OVERFLOW -1
//定义二叉树的结构
typedef struct tree{
    char data;
    struct tree *lchild;
    struct tree *rchild;
}*Ptree,Dtree;

//先序创建二叉树
Ptree createTree()
{
    char ch;
    Ptree t;
    ch=getchar();
    printf("\n输入二叉树的元素:\n");    /*输入二叉树的元素*/
    scanf("%c",&ch);
    if(ch=='#') t=NULL;
        else{
    if(!(t=(Ptree*)malloc(sizeof(Ptree)))) exit(OVERFLOW);
        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 intOrder(Ptree t)
{
    if(t)
    {
        intOrder(t->lchild);
        printf("%c",t->data);
        intOrder(t->rchild);
    }
}
//求叶子数
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;
    int j;

    Ptree t;
while(j){
         printf("请输入你要的功能\n");
         printf("----------------\n");
         printf("1:先序创建二叉树\n");
         printf("2:中序遍历二叉树\n");
         printf("3:层次遍历二叉树\n");
         printf("4:二叉树的高度\n");
         printf("5:每层节点数\n");
         printf("6:叶子数\n");
         printf("0:退出程序\n");
         printf("----------------\n");
         scanf("%d",&j);
         switch(j){
         case 1:t=createTree();break;//先序创建二叉树
         case 2:intOrder(t);
                 printf("\n");break;//中序遍历
         case 3:levelOrder(t);
                printf("\n");break;//层次遍历
         case 4:height=heightTree(t);
                printf("深度:%d\n",height);break;//数的深度
         case 5:levelCount(t,1,num);
                for(i=1;i<=height;i++)
                printf("第%d层个数:%d\n",i,num[i]);break;//每层节点数
         case 6:printf("叶子总数:%d\n",leafCount(t));break;//叶子数
         case 0:exit(1);
        }
}
    return 0;
}

标签:c++,二叉树,算法,数据结构

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  2. Liyun 发表 2016-02-04 00:40:50 抄抄笔记——格雷码
  3. chendong.dong 发表 2014-02-25 03:11:07 图的内存结构及在数据结构之上实现聚类算法
  4. dianlujitao 发表 2014-10-17 13:52:22 POJ 2388 Who’s in the Middle
  5. 马天游 发表 2013-03-28 04:02:29 关于“事件驱动”设计的思考
  6. cijianzy 发表 2015-05-01 14:20:33 修复了中文维基百科基数排序C++代码的一个bug
  7. dianlujitao 发表 2013-10-31 01:04:46 搬运树苗 二分+贪心
  8. 博主 发表 2016-04-18 05:38:57 关于《Swift 算法与数据结构》
  9. fox64194167 发表 2018-05-27 00:12:22 python 搜索插入位置
  10. fox64194167 发表 2018-06-24 01:17:31 Leetcode 有效的括号字符串 python
  11. leaver 发表 2013-05-31 07:05:29 邻接表实现无向图(C++)
  12. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects

发表评论