二叉树
这是建表达式的二叉树 总是最后输出一个?号,也不知道问题出哪了!
我知道代码看着烦,如果有空的话帮忙看下问题出哪了,谢谢了!
#include "stdafx.h"#include <stdlib.h>typedef struct bitree /*树的结构体*/{ struct bitree *lchild; struct bitree *rchild; char data;}trees;typedef trees *tree;typedef struct lists /*数据链表*/{ struct lists *next; char data;}list;int bijiao(char k) /*比较符号*/{ switch(k) { case '(': return 1; case ')': return 1; case '*': return 8; case '/': return 8; case '+': return 7; case '-': return 7; case '#': return 0; } return 0;}list *data(char *a) /*创建数据链表*/{ list *head,*node,*hand; int i=0; head=(list*)malloc(sizeof(list)); head->data=a[i]; head->next=NULL; hand=head; if(head==NULL) { return 0; } i=1; while(i<11) { node=(list*)malloc(sizeof(list)); if(!node) { return 0; } node->data=a[i]; node->next=NULL; hand->next=node; hand=hand->next; ++i; } return head;}void pushtree(tree *stack,tree *k) /*结点进栈*/{ tree node; if(stack==NULL) { (*stack)=(trees*)malloc(sizeof(trees)); /*建立空结点栈*/ node=(trees*)malloc(sizeof(trees)); node->lchild=*k; node->rchild=NULL; *stack=node; } else { node=(trees*)malloc(sizeof(trees)); /*结点进栈*/ node->lchild=*k; node->rchild=*stack; *stack=node; }}void push(tree *stack,char k) /*符号进栈*/{ tree node,hand=NULL; if(k=='('||k==')'||k=='*'||k=='/'||k=='+'||k=='-') /*字母包装成结点*/ { node=(trees*)malloc(sizeof(trees)); node->data=k; node->rchild=(*stack); (*stack)=node; } else { node=(trees*)malloc(sizeof(trees)); /*运算符号进栈*/ node->data=k; node->lchild=NULL; node->rchild=NULL; (*stack)=node; } }void init(tree *head) /*创建运算符栈头*/{ (*head)=(trees*)malloc(sizeof(trees)); (*head)->data='#'; (*head)->lchild=NULL; (*head)->rchild=NULL;}void subtree(tree *zimu,tree *fuhao,tree *node) /*建立子树*/{ (*node)=(*fuhao); (*fuhao)=(*fuhao)->rchild; (*node)->rchild=(*zimu)->lchild; (*zimu)=(*zimu)->rchild; (*node)->lchild=(*zimu)->lchild; (*zimu)=(*zimu)->rchild;}void output1(list *head) /*输出单链表*/{ while(head!=NULL) { printf("%c",head->data); head=head->next; }}void output(tree zimu) /*后序输出*/{ if(zimu!=NULL) { output(zimu->lchild); output(zimu->rchild); printf("%c ",zimu->data); }}int main(){ list *head=NULL; tree zimu=NULL,zimu1=NULL,fuhao=NULL,node=NULL; int x,y; char k, a[11]={'a','*','b','/','c','*','d','-','e','+','f'}; head=data(a); /*创建数据链表*/ output1(head); /*输出数据链表*/; printf("\n"); init(&fuhao); /*创建符号栈头*/ while(head!=NULL) { k=head->data; if(!(k=='('||k==')'||k=='*'||k=='/'||k=='+'||k=='-')) /*操作字母进栈*/ { push(&zimu1,k); /*操作字母进栈生成结点*/ pushtree(&zimu,&zimu1); /*结点进字母栈*/ head=head->next; /*数据链表位移*/ } if(k=='('||k==')'||k=='*'||k=='/'||k=='+'||k=='-') /*运算符号进栈*/ { x=bijiao(k); /*返回运算符号的值*/ y=bijiao(fuhao->data); /*返回运算符号的值*/ if(x>y) { push(&fuhao,k); /*运算符号进栈*/ head=head->next; } else { if(k=='(') /*左括号进栈*/ { push(&fuhao,k); head=head->next; } if(k==')') /*如果当前符号是')'，退出栈中'('至')'中的所有符号*/ { while(fuhao->data!='(') { subtree(&zimu,&fuhao,&node); /*运算符号与字母生成子树*/ pushtree(&zimu,&node); /*子树进字母栈*/ } fuhao=fuhao->rchild; /*符号栈位移*/ head=head->next; } else { subtree(&zimu,&fuhao,&node); /*运算符号与字母生成子树*/ pushtree(&zimu,&node); /*子树进字母栈*/ } } } } while(fuhao->data!='#') /*最后推出符号栈内的所有符号，给字母链*/ { subtree(&zimu,&fuhao,&node); /*运算符号与字母生成子树*/ pushtree(&zimu,&node); /*子树进字母栈*/ }output(zimu); /*遍历输出*/}