编程论坛 » 数据结构与算法 » 用 递归算法统计二叉树的叶子数目。

petronella 发表于 2008-5-11 15:41

用 递归算法统计二叉树的叶子数目。

算法我会，可是程序就搞不清楚了。请帮忙。国际

[[it] 本帖最后由 petronella 于 2008-5-12 22:23 编辑 [/it]]

zjl138 发表于 2008-5-11 18:39

晕，算法都会了，还能有什么大问题。

petronella 发表于 2008-5-12 22:19

是这样的，总也该不对啊，犯愁哦。

#include "stdio.h"
#include"stdlib.h"
typedef char DataType;
typedef struct BiTNode
{
        DataType data;
        struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreatBiTree(BiTree *T)
{
        char ch;
        ch=getchar();
        if(ch==' ')T=NULL;
        else
        {
                if(!(T=(BiTNOde*)malloc(sizeof(BiTNode)))exit(OVERFLOW)
                T->data=ch;
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
        }
}
        void Node(BiTree T)
        {
                int static nodes=0;
                if(T)
                {
                        Node(T->lchild);
                        nodes++;
                        Node(T->rchild);
                        nodes++
                }
                return nodes;
        }
        void Leaf(BiTree T)
        {
                int static leaves=0;
                if(T)
                {
                        leaf(T->lchild);
                        if(!(T->lchild||T->rchild))
                        leaves++;
                        Leaf(T->rchild);
                }
                return leaves;
        }
void main()
{
    int nodes,leaves,root;
    nodes=0,leaves=0;
    int BiTree root;
    CreatBiTree(&root);
    nodes=Node(root);
    leaves=Leaf(root);
    printf("\n nodes=%d leaves=%d",nodes,leaves);
   
}

diaoxue 发表于 2008-5-14 13:07

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define FALSE 0
//定义结构体
typedef struct BiTNode
{
        //int data;
        char data;
        struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//创建二叉树
int CreateBiTree(BiTree &T)
{
        printf("\n==========Create BiTree!===========\n");
        char ch;
//        ch=getchar();
        printf("Input the Node/# is stand for none:\n");
        scanf("%c",&ch);
        if(ch=='#')T=NULL;
        else
        {
                if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
                {
                        exit(1);
                }
                T->data=ch;
                CreateBiTree(T->lchild);
                CreateBiTree(T->rchild);
        }
        return OK;
}
//访问函数
int Visit(char e)
{
        printf("%c",e);
        return OK;
}
//先序遍历
int PreOrderTraverse(BiTree T)
{
        if(T)
        {
                if(Visit(T->data))
                {
                        if(PreOrderTraverse(T->lchild))
                        {
                                if(PreOrderTraverse(T->rchild))
                                {
                                        return OK;
                                }
                        }
                        return FALSE;
                }
                return FALSE;
        }
        else
        {
                return OK;
        }
}
//中序遍历
int InOrderTraverse(BiTree T)
{
        if(T)
        {
                if(InOrderTraverse(T->lchild))
                {
                        if(Visit(T->data))
                        {
                                if(InOrderTraverse(T->rchild))
                                {
                                        return OK;
                                }
                        }
                        return FALSE;
                }
                return FALSE;
        }
        else
        {
                return OK;
        }
}
//后序遍历
int PostOrderTraverse(BiTree T)
{
        if(T)
        {
                if(PostOrderTraverse(T->lchild))
                {
                        if(PostOrderTraverse(T->rchild))
                        {
                                if(Visit(T->data))
                                {
                                        return OK;
                                }
                        }
                        return FALSE;
                }
                return FALSE;
        }
        else
        {
                return OK;
        }
}

//求树的高度
int getTreeHight(BiTree T)
{
    int lhight=0,
        rhight=0,
        hight=0;
    if(!T)
       return 0;
    else
    {
        lhight=getTreeHight(T->lchild);
        rhight=getTreeHight(T->rchild);
        hight=((lhight>rhight)?lhight:rhight) + 1;
       // hight=(lhight>rhight)?lhight:rhight + 1;
      //  printf("%d",hight);
        return hight;
    }     
}

//求树的节点数
int getTreeNodeNumber(BiTree T)
{
    int lnum=0,
        rnum=0,
        num=0;
    if(!T)
       return 0;
    else
    {
       lnum=getTreeNodeNumber(T->lchild);
       rnum=getTreeNodeNumber(T->rchild);
       num=lnum+rnum+1;
     //  printf("%d",num);
       return num;  
    }   
}
//求叶子节点数
int getTreeLeaveNumber(BiTree T)
{
    int lnum=0,
        rnum=0,
        num=0;
    if(!T)
       return 0;
    else if((!T->lchild)&&(!T->rchild))
       return 1;
    else
    {
       lnum=getTreeLeaveNumber(T->lchild);
       rnum=getTreeLeaveNumber(T->rchild);
       num=lnum+rnum;
     //  printf("%d",num);
       return num;
    }
}

//判断是否存在子孙关系
bool Locate(BiTree T,BiTree &R,char v)
{
        if(!T)
                return false;
        else if(T->data==v)
        {
                R=T;
                return true;
        }
        else
        {
                Locate(T->lchild,R,v);
                Locate(T->rchild,R,v);
        }
}
bool isInherit(BiTree T,BiTree R,char m,char n)
{
        //BiTree R;
        BiTree M;
        if(!Locate(T,R,m))
        {
                printf(" not Inerit!");
                return false;
        }
        else
        {
                if(!Locate(R,M,n))
                {
                        printf(" not Inerit!");
                        return false;
                }
                else
                {
                        printf("Inerit!");
                        return true;
                }
        }
}

int main()
{
        BiTree T;
        CreateBiTree(T);
        BiTree R;
        R=(BiTree )malloc(sizeof(BiTNode));
        printf("\n==========PreOrderTraverse============\n");
        PreOrderTraverse(T);
        printf("\n==========InOrderTraverse=============\n");
        InOrderTraverse(T);
        printf("\n==========PostOrderTraverse===========\n");
        PostOrderTraverse(T);
        printf("\n==========TreeHight===================\n");
        printf("%d",getTreeHight(T));
        printf("\n==========TreeNodeNumber==============\n");
        printf("%d",getTreeNodeNumber(T));
        printf("\n==========TreeLeaveNumber=============\n");
        printf("%d",getTreeLeaveNumber(T));
        printf("\n==========inherit==================\n");
        //==========
/*        char v=0;
        printf("input v:\n");
        scanf("%s",&v);
        Locate(T,R,v);*/
        //==========
        char m=0,
                 n=0;
        printf("input m:\n");
        scanf("%s",&m);
        printf("input n:\n");
        scanf("%s",&n);
        bool result=isInherit(T,R,m,n);
//        printf("%d",result);
        system("pause");
        return 0;
}
//测试用例：abd###cmn####

查看完整版本: 用 递归算法统计二叉树的叶子数目。