|
|
#2
hzh5122010-05-12 18:59
你建树逻辑有问题
pseudo-code as followed: push root into stack; while(!emptyStack) { input ch; if(ch!=' '&& Right == false) { assign the node of tree; push this node into stack; } if (ch ==' ') { pop the stack; Right = true;// turn right; } if (ch!=' '&& Right == true) { assign the node of tree; push this node into stack; Right = false; // turn left; } } 程序代码:#define STACK_INIT_SIZE 100//测试值:abc@@de@g@@f@@@ #define STACKINCREMENT 10 #include <stdio.h> #include <stdlib.h> typedef char TElemType; //////////////////////////////////////////////栈定义 typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild;// }BiTNode,*BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; }SqStack; /////////////////////////////////////////////栈的基本操作 void initialStack(SqStack *s) { s->base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree)); if(!s->base) exit(0); s->top=s->base; s->stacksize=STACK_INIT_SIZE; } void Push(SqStack *s,BiTNode *e) { if(s->top-s->base>=s->stacksize) { s->base=(BiTree *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BiTree)); if(!s->base) exit(0); s->top=s->base+s->stacksize; s->stacksize+=STACKINCREMENT; } *(s->top)++=e; } void Pop(SqStack *s,BiTree *e)////////////////// { if(s->top==s->base) exit(0); *e=*--(s->top);// } int GetTop(SqStack *s,BiTree *e)/////////////////// { if(s->top==s->base) return(0); *e=*(s->top-1);// return(1); } int StackEmpty(SqStack *s) { if(s->base==s->top) return(1); else return(0); } void ClearStack(SqStack *s) { s->top=s->base; s->stacksize=0; } void DestoryStack(SqStack *s) { free(s->base); s->stacksize=0; } BiTree CreatBiTree()//非递归算法先序建立二叉链表 { bool Right = false; //flag TElemType ch; BiTree T,p,root; SqStack S; initialStack(&S); scanf("%c",&ch); if(ch==' ') root=T=NULL; else { root=T=(BiTree)malloc(sizeof(BiTNode)); T->data=ch; T->lchild=T->rchild=NULL; Push(&S,T); } while(!StackEmpty(&S)) { scanf("%c",&ch); if(ch!=' '&& Right == false)//生成左儿子 { p=(BiTree)malloc(sizeof(BiTNode)); p->data=ch; p->lchild=p->rchild=NULL; T->lchild=p; T=p; Push(&S,T); } if (ch ==' ') { Pop(&S,&T); Right = true; } if (ch!=' '&& Right == true) { p=(BiTree)malloc(sizeof(BiTNode)); p->data=ch; p->lchild=p->rchild=NULL; T->rchild=p; T=p; Push(&S,T); Right = false; } } return root; } void Visit(TElemType e)//对数据元素进行操作的Visit函数 { printf("%c",e); } void PreOrderTraverse(BiTree T)//先序遍历 { if(T) { Visit(T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } ///////////////////////////////// void main() { BiTree t; printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n"); printf("<参考数据:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n"); t=CreatBiTree(); printf("[先序遍历]:\n"); PreOrderTraverse(t); printf("\n"); } [ 本帖最后由 hzh512 于 2010-5-12 19:01 编辑 ] |
#define STACK_INIT_SIZE 100//测试值:abc@@de@g@@f@@@
#define STACKINCREMENT 10
#include <stdio.h>
#include <stdlib.h>
typedef char TElemType;
//////////////////////////////////////////////栈定义
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;//
}BiTNode,*BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
/////////////////////////////////////////////栈的基本操作
void initialStack(SqStack *s)
{
s->base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree));
if(!s->base) exit(0);
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,BiTNode *e)
{
if(s->top-s->base>=s->stacksize)
{
s->base=(BiTree *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BiTree));
if(!s->base) exit(0);
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*(s->top)++=e;
}
void Pop(SqStack *s,BiTree *e)//////////////////
{
if(s->top==s->base) exit(0);
*e=*--(s->top);//
}
int GetTop(SqStack *s,BiTree *e)///////////////////
{
if(s->top==s->base) return(0);
*e=*(s->top-1);//
return(1);
}
int StackEmpty(SqStack *s)
{
if(s->base==s->top)
return(1);
else
return(0);
}
void ClearStack(SqStack *s)
{
s->top=s->base;
s->stacksize=0;
}
void DestoryStack(SqStack *s)
{
free(s->base);
s->stacksize=0;
}
BiTree CreatBiTree()//非递归算法先序建立二叉链表
{
TElemType ch;
BiTree T,p;
SqStack S;
initialStack(&S);
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=ch;
T->lchild=T->rchild=NULL;
Push(&S,T);
}
while(!StackEmpty(&S))
{
scanf("%c",&ch);
if(ch!=' ')//生成左儿子,直到左儿子为空时退出循环
{
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->lchild=p;
T=p;
Push(&S,T);
scanf("%c",&ch);
}
else
Pop(&S,&T);//弹出最后一个左儿子(栈顶元素)
T->lchild=NULL;
scanf("%c",&ch);
if(ch==' ')//右儿子为空的情况
{
while((ch==' ')&&(!StackEmpty(&S)))//弹出栈顶元素,逆向返回,直到右儿子不为空
{
T->rchild=NULL;
Pop(&S,&T);//弹出根结点,进入右子树
scanf("%c",&ch);
}
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->rchild=p;//右儿子的根结点p的父亲为T
T=p;
Push(&S,T);
}
else//右儿子不为空的情况
{
p=(BiTree)malloc(sizeof(BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
T->rchild=p;//右儿子的根结点p的父亲为T
T=p;
Push(&S,T);
}
}
return T;
}
void Visit(TElemType e)//对数据元素进行操作的Visit函数
{
printf("%c",e);
}
void PreOrderTraverse(BiTree T)//先序遍历
{
if(T)
{
Visit(T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
/////////////////////////////////
void main()
{
BiTree t;
printf("请按先序遍历序列输入二叉树中各个结点的值(字符),若为空树时输入空格键:\n");
printf("<参考数据:abc@@de@g@@f@@@,则用空格键表示@,输完后再输入一个回车键.>\n");
t=CreatBiTree();
printf("[先序遍历]:\n");
PreOrderTraverse(t);
printf("\n");
}
程序代码: