| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 386 人关注过本帖
标题:[求助]关于确定唯一二叉树,代码检不出错误
只看楼主 加入收藏
gujunpu
Rank: 1
等 级:新手上路
帖 子:23
专家分:3
注 册:2012-2-25
结帖率:60%
收藏
已结贴  问题点数:10 回复次数:2 
[求助]关于确定唯一二叉树,代码检不出错误
[求助]关于确定唯一二叉树,代码检不出错误
#include <stdio.h>
#include <Stdlib.h>
#include <string.h>

typedef struct Node
{
char data;
struct Node *LeftChild;
struct Node *RightChild;
}BiTNode;
void Initiate(BiTNode **root)
{
*root=(BiTNode *)malloc(sizeof(BiTNode));
(*root)->LeftChild=NULL;
(*root)->RightChild=NULL;
}
void Visit(char item)
{
printf("%c",item);
}
void PreOrder(BiTNode *T,void Visit(char item))
{
if(T!=NULL)
{
Visit(T->data);
PreOrder(T->LeftChild,Visit);
PreOrder(T->RightChild,Visit);
}
}
void InOrder(BiTNode *T,void Visit(char item))
{
if(T!=NULL)
{
InOrder(T->LeftChild,Visit);
Visit(T->data);
InOrder(T->RightChild,Visit);
}
}
void PostOrder(BiTNode *T,void Visit(char item))
{
if(T!=NULL)
{
PostOrder(T->LeftChild,Visit);
PostOrder(T->RightChild,Visit);
Visit(T->data);
}
}
void PrintBiTree(BiTNode *T,int n)
{
int i;
if(T==NULL) return;
PrintBiTree(T->RightChild,n+1);
for(i=0;i<n;i++) printf("      ");
if(n>=0)
{
printf("--------");
printf("%c\n",T->data);
}
PrintBiTree(T->LeftChild,n+1);
}

BiTNode* CreatTree(char *pre,char *in,int len)
{
char *p,*i;
int j=0; //j表示根节点在中序中的位置
BiTNode  *T;
Initiate(&T);
T->data=pre[0];
if(len==0)return NULL;
               
while(j<len)
{
  if(in[j]==pre[0])break;
  j++;
}
p = pre+1;             //确定左子树的先序序列指针
i= in;               //确定左子树的中序序列指针
T->LeftChild=CreatTree(p,i,j);  //递归生成左子树
p = pre+j+1;               //确定右子树的先序序列指针
i = in+j+1;           //确定右子树的中序序列指针
T->RightChild=CreatTree (p,i,len-j-1);//递归生成右子树
   return T;
}

void main()
{
BiTNode *T;
int len;
char *Pre;//前序序列
char *In;//中序序列

printf("请输入前序序列:");
scanf("%s",&Pre);
printf("请输入中序序列:");
scanf("%s",&In);
len=strlen(In);
Initiate(&T);
T=CreatTree(Pre,In,len);
printf("二叉树构造成功!\n");
printf("逆时针旋转90度的二叉树如下所示:\n");
PrintBiTree(T,0);
printf("前序序列:");
PreOrder(T,Visit);
printf("\n中序序列:");
InOrder(T,Visit);
printf("\n后序序列:");
PostOrder(T,Visit);
printf("\n");
}

我想问题出现在后两个函数,可以编译出来,但是输入之后无法运行。
搜索更多相关主题的帖子: void 唯一 include 二叉树 
2012-12-10 10:42
zhu224039
Rank: 8Rank: 8
等 级:贵宾
威 望:17
帖 子:862
专家分:792
注 册:2012-7-29
收藏
得分:10 
#include"stdio.h"
#include <stdlib.h>
#include"string.h"
typedef struct tree  /*树结构*/
{
    int i;     /*数据区*/
    int treehigh;  /*存放节点深度*/
    struct tree *lift;  
    struct tree *right;
}tree;

tree *creatjiedian()  /*创建节点*/
{
    tree *p;
    p=(tree*)malloc(sizeof(tree));
    if(p==NULL)
        printf("地址申请失败");
    else
    {
        p->lift=p->right=NULL;
        p->treehigh=0;
    }
    return p;
}

int ax(int a,int b)  /*比较数的大小*/
{
    if(a>b)
        return a;
    else
        return b;
}


        
tree *charujiedian(tree *p,int x)   /*将节点插入到AVL树里*/
{
    if(p==NULL)
    {
        p=creatjiedian();
        p->i=x;
    }
    else if(p->i>x)  
    {
        p->lift=charujiedian(p->lift,x);
        p->lift->treehigh=p->treehigh+1;  /*计算节点的深度*/
    }
    else if(p->i<x)
    {
        p->right=charujiedian(p->right,x);
        
        p->right->treehigh=p->treehigh+1; /*计算节点的深度*/
    }
    return p;
}

tree *zuodanxuan(tree *p)   /*在P的左儿子的左子树的插入 左旋转*/
{
    tree *p1;
    p1=p->lift;
    p->lift=p1->right;
    p1->right=p;
    return p1;
}

tree *youdanxuan(tree *p) /*在p的右儿子的右子树上的插入 右旋转*/
{
    tree *p1;
    p1=p->right;
    p->right=p1->lift;
    p1->lift=p;
    return p1;
}

tree *zuoshuangxuan(tree *p)  /*在P的左儿子的右子树上的插入 右单旋+左单旋转*/
{
    tree *p1;
    p1=p->lift;
    p->lift=youdanxuan(p1);
    return zuodanxuan(p);
}

tree *youshuangxuan(tree *p)  /*在P的右儿子的左子树上的插入*/
{
    tree *p1;
    p1=p->right;
    p->right=zuodanxuan(p1);
    return youdanxuan (p);
}

void zenggengxin(tree *p)   /*将P的所有子树深度加1*/
{
    if(p!=NULL)
    {
        p->treehigh++;
        zenggengxin(p->lift);
        zenggengxin(p->right);
    }   
}

void jiangengxin(tree *p)  /*将P的所有子树深度减1*/
{
    if(p!=NULL)
    {
    p->treehigh--;
    jiangengxin(p->lift);
    jiangengxin(p->right);
    }
}


void dayin(tree *p)          /*先序遍历*/
{   
    if(p!=NULL)
    {
        printf("%d %d\n",p->i,p->treehigh);
        
      dayin(p->lift);
      dayin(p->right);
    }
}

int high(tree *p)   /*计算P的树高*/
{
    int n;
    if(p==NULL)
        n=-1;
    else
    {
    if(p->lift==NULL&&p->right==NULL)
        n=0;
    else if(p->lift!=NULL&&p->right==NULL)
        n=1+high(p->lift);
    else if(p->lift==NULL&&p->right!=NULL)
        n=1+high(p->right);
    else
        n=1+ax(high(p->right),high(p->lift));
    }
   return n;
}

tree *avlpingheng(tree *p2,int x)   /*AVL树的自我平衡*/
{
    tree *p;
    if(x<p2->i&&x<p2->lift->i)
        {
        
            p=zuodanxuan(p2);
            if(p->lift!=NULL)          /*经过平衡后,重新更新子树的深度*/
            jiangengxin(p->lift);
            p->right->treehigh++;
            if(p->right->right!=NULL)
            zenggengxin(p->right->right);
        }
    else if(x<p2->i&&x>p2->lift->i)
        {
            p=zuoshuangxuan(p2);
            if(p->lift->right!=NULL)         /*经过平衡后,重新更新子树的深度*/
            jiangengxin(p->lift->right);
            if(p->right->lift!=NULL)
            jiangengxin(p->right->lift);
            if(p->right->right!=NULL)
            zenggengxin(p->right->right);
            p->right->treehigh++;
        }
    else if(x>p2->i&&x>p2->right->i)
    {      
            p=youdanxuan(p2);
            if(p->right!=NULL)
            jiangengxin(p->right);         /*经过平衡后,重新更新子树的深度*/
            p->lift->treehigh++;
            if(p->lift->lift!=NULL)
            zenggengxin(p->lift->lift);
    }
    else
    {
            p=youshuangxuan(p2);
            if(p->right->lift!=NULL)               /*经过平衡后,重新更新子树的深度*/
            jiangengxin(p->right->lift);      
            if(p->lift->right!=NULL)
            jiangengxin(p->lift->right);
            if(p->lift->lift!=NULL)
            zenggengxin(p->lift->lift);
            p->lift->treehigh++;
    }

     return p;   
}


void main()
{
    tree *p,*p1,*p2,*root,*p3,*p4;  /*root记录当前树根,P1用来查找从根到插入点的路径,p2记录每次查找的子树的父亲 p3记录失衡点的父亲,p4记录失衡点*/
    int i,j;                       /*i用来标记是否有失衡点(1个或者多个)j用来记录树结构体数据的*/
    p=creatjiedian();
    root=p;
    printf("请输入根节点数据:\n");
    scanf("%d",&j);
    p->i=j;
    i=0;
    printf("请输入节点数据:\n");
    scanf("%d",&j);
    charujiedian(root,j);
    p1=root;
    while(j!=0)                                /*创建AVL树约定输入0为结束*/
    {
        charujiedian(root,j);
        while(p1->i!=j)             /*遍历从根到插入数据的路径*/
        {   
            if(high(p1->lift)-high(p1->right)==2||high(p1->lift)-high(p1->right)==-2)    /*判定是否为失衡点,并找出最接近插入点的失衡点*/
            {
                i++;
                p3=p2;
                p4=p1;
                if(j>p1->i)
                {
                    p2=p1;
                    p1=p1->right;
                }
                else
                {
                    p2=p1;
                    p1=p1->lift;
                }
            }
            else
            {
                if(j>p1->i)
                {
                p2=p1;
                p1=p1->right;
                }
                else
                {  
                    p2=p1;
                    p1=p1->lift;
                }
            }
            
        }
        
        if(i==1)   /*i=1 代表根是不平衡点*/
        {
            root=avlpingheng(p4,j);
            root->treehigh--;
        }
        else if(i>1)   /*代表子树是不平衡点*/
        {
            p4=avlpingheng(p4,j);
            if(p4->i<p3->i)
            p3->lift=p4;
            else
                p3->right=p4;
            p4->treehigh=p3->treehigh+1;
        }
        p1=root;                       /*p1也必须重置,因为只两个是循环和判断的起始*/
        i=0;                           /*i值必须重置*/
        printf("请输入节点数据:\n");
        scanf("%d",&j);
    }
dayin(root);                          /*打印*/

}

我要成为嘿嘿的黑客,替天行道
2012-12-10 10:53
zhu224039
Rank: 8Rank: 8
等 级:贵宾
威 望:17
帖 子:862
专家分:792
注 册:2012-7-29
收藏
得分:0 
送给你参考   自动平衡二叉树

我要成为嘿嘿的黑客,替天行道
2012-12-10 10:53
快速回复:[求助]关于确定唯一二叉树,代码检不出错误
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019170 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved