注册 登录
编程论坛 C++教室

求助啊!!!!请大家来帮忙看看。。。。

狂一户 发布于 2010-11-27 11:27, 895 次点击
#include<iostream>
using namespace std;
typedef char ElemType;
#define MaxSize 100
typedef struct node         //定义二叉树
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&h,char *str)      //建造二叉树
{
    BTNode *zhan[MaxSize],*p=NULL;
    int top=-1,k,j=0;
    char c;
    c=str[j];
    while(c!='#')
    {
        switch(c)
        {
        case '(':top++;zhan[top]=p;k=1;break;
        case ')':top--;break;
        case ',':k=2;break;
        default:p=new BTNode;
            p->data=c;p->lchild=NULL;p->rchild=NULL;
            if(h==NULL)
                h=p;
            else
                switch(k)
                {
                case 1:zhan[top]->lchild=p;break;
                case 2:zhan[top]->rchild=p;break;
                }
        }
        j++;
        c=str[j];
    }
}
void display(BTNode *h)     //输出root的左右的孩子
{
    cout<<"左孩子结点值:"<<h->lchild->data<<endl;
    cout<<"右孩子结点值:"<<h->rchild->data<<endl;
}
int high(BTNode *h)       //求高度
{
    int i,lift,right;
    if(h==NULL)
        return 0;
    else
    {
        if(h->lchild!=NULL)
            i=1;
        else
            i=2;
        switch(i)
        {
        case 1:lift=high(h->lchild)+1;break;
        case 2:right=high(h->rchild)+1;break;
        }
        return (lift>right)? lift:right;
    }
}
void wide(BTNode *h)      //求宽度
{
    BTNode *std[MaxSize];
    int top=1,i=0,j,n,k=1,m,f=0,l=1,max;
    int a[MaxSize];
    std[top]=h;
    i++;
    a[f]=i;
    if(std[1]->lchild!=NULL)
            {
                i++;
                top++;
                std[top]=std[1]->lchild;
            }
            if(std[1]->rchild!=NULL)
            {
                i++;
                top;
                std[top]=std[1]->lchild;
            }
    while(l<=MaxSize)
    {
        i=0;
        m=i;
        n=top;
        for(j=k;j<=n;j++)
        {
            if(std[j]->lchild!=NULL)
            {
                i++;
                top++;
                std[top]=std[j]->lchild;
            }
            if(std[j]->rchild!=NULL)
            {
                i++;
                top;
                std[top]=std[j]->lchild;
            }
        }
        k=k+m;
        f++;
        a[f]=i;
        l++;
    }
    max=a[0];
    for(i=1;i<=f;i++)
        if(max<a[i])
            max=a[i];
    cout<<"宽度为:"<<max<<endl;
}
int main()
{
    BTNode *h;
    char str[MaxSize];
    int i=0;
    cin>>str[i];
    while(str[i]!='#')
    {
        i++;
        cin>>str[i];
    }
    CreateBTNode(h,str);
    display(h);
    wide(h);
}
输入是以括号表示法的二叉树    然后应该以#号结束
但是以#号结束时   程序就出错了   无法运行  
10 回复
#2
玩出来的代码2010-11-27 12:52
二叉树有点陌生了,你把题的要求说下看看我能帮不能,或者到数据结构板块去问,C板块比较热闹,也可以去。
#3
xanxus2010-11-27 13:51
LZ给个例子,我们好根据你的例子分析
#4
狂一户2010-11-27 15:17
回复 2楼 玩出来的代码
题目没什么要求,就是建立二叉树,输出H结点的左右孩子结点值,输出二叉树的深度,输出二叉树的宽度。
这是课本上的题目,是建立在课文的基础上的,是用括号表示法的二叉树进行输入和分析
我想可能是输入#号和上面的程序有冲突  但是看了半天,没发现为什么。
只有本站会员才能查看附件,请 登录
#5
狂一户2010-11-27 15:17
回复 3楼 xanxus
题目没什么要求,就是建立二叉树,输出H结点的左右孩子结点值,输出二叉树的深度,输出二叉树的宽度。
这是课本上的题目,是建立在课文的基础上的,是用括号表示法的二叉树进行输入和分析
我想可能是输入#号和上面的程序有冲突  但是看了半天,没发现为什么。
只有本站会员才能查看附件,请 登录
#6
xanxus2010-11-27 16:53
我想知道是你是如何输入的,你那个括号表示法具体给个例子
#7
寒风中的细雨2010-11-27 19:42
A(B(C(D,E),F),G(H))#
建树的函数不错
#8
xanxus2010-11-27 21:49
没有构造结点吧,我好象没看到
#9
狂一户2010-11-27 22:18
回复 6楼 xanxus
老师,如楼下的版主举得例子
#10
无名可用2010-11-28 10:13
程序代码:
#include<iostream>
using namespace std;
typedef char ElemType;
#define MaxSize 100
typedef struct node         //定义二叉树
{
    ElemType data;
    struct node *lchild;
    struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&h,char *str)      //建造二叉树
{
    BTNode *zhan[MaxSize],*p=NULL;
    int top=-1,k=0,j=0;
    char c;
    c=str[j];
    while(c!='#')
    {
        switch(c)
        {
        case '(':{top++;zhan[top]=p;k=1;}break;
        case ')':top--;break;
        case ',':k=2;break;
        default:
        {
            p=new BTNode;
            p->data=c;p->lchild=NULL;p->rchild=NULL;
            if(h==NULL)
                h=p;
            else
                switch(k)
                {
                case 1:zhan[top]->lchild=p;break;
                case 2:zhan[top]->rchild=p;break;
                }
        }//default
        }//switch
        j++;
        c=str[j];
    }
}
void display(BTNode *h)     //输出root的左右的孩子
{
    cout<<"h="<<h->data<<endl;
    cout<<"左孩子结点值:"<<h->lchild->data<<endl;
    cout<<"右孩子结点值:"<<h->rchild->data<<endl;
}
int main()
{
    BTNode *h=NULL;//要加上NULL,把NULL去掉你就明白了
   char str[MaxSize];
    int i=0;
    cin>>str[i];
    while(str[i]!='#')
    {
        i++;
        cin>>str[i];
    }
    CreateBTNode(h,str);
    display(h);
    wide(h);
    return 1;
}
至于求二叉树的宽度我们数据结构课没提到,不过我感觉层次遍历一下整个树就可以了。
你的程序中求宽度的函数有问题,而且楼主既然你用c++来编程,为什么还保留着C语言的习惯:把所有变量都定义在
函数头部,当变量一多,又没有注解,看的人有点晕。
#11
diddian2010-12-04 18:56
小胖胖,哥人肉到你了,嘎嘎

问题在于display(h)调用,你要输出h节点左右孩子,首先要找到data域为h的结点指针,通过这个指针来输出左右孩子

你可以调试一下,display函数的输出有bug
1