前缀表达式（波兰式）转换成二叉树.txt

前缀表达式转换成二叉树的代码

简单啦其实你可以去看看lisp的实现，其实就是
（ X Y）
第一个符号看成第一个节点
然后x是左节点，y是右节点 如果x，或y又是符号，就在开枝插就行了 然后从底部遍历树的每一层并计算就行了。

______
| |
x *
-------
| |
u y 

lisp只不过添加了一些其他的元素就构成了一个预言。呵呵
foochow(恰似你的温柔) 于 2005-6-23 20:56:44
多翻翻算法书:P
boxban(冻酸梨) 于 2005-6-23 22:41:30
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


#define MAX_ELEM 100

typedef int bool;
static enum { false, true};

typedef int data_t;
enum NODE_TYPE {NODE_OPERATOR, NODE_DATA};
struct node{
struct node* left;
struct node* right;
enum NODE_TYPE type;
union{
data_t data;
char op;
};
};

/*******************************************
一个简单的stack实现
********************************************/
static struct node* _stackNode[MAX_ELEM];
static int _topNode = -1;

void push_node(struct node* node)
{
assert(_topNode < (MAX_ELEM-1));
_stackNode[ _topNode] = node;
}

struct node* pop_node(void)
{
assert(_topNode >= 0);
return _stackNode[_topNode--];
}

// 查看栈顶节点，不出栈
struct node* top_node(void)
{
return (_topNode < 0 ? NULL : _stackNode[_topNode]);
}

/*********************************************
几个用以创建新节点以及打印节点信息的辅助函数
**********************************************/
struct node* new_node()
{
return (struct node*)malloc(sizeof(struct node));
}

struct node* new_data_node(data_t data)
{
struct node* node = new_node();
node->type = NODE_DATA;
node->data = data;
node->left = node->right = NULL;

return node;
}

struct node* new_operator_node(char op)
{
struct node* node = new_node();
node->type = NODE_OPERATOR;
node->op = op;
node->left = node->right = NULL;

return node;
}

void print_node(const struct node* node)
{
if (node->type == NODE_DATA)
printf("%d ", node->data);
else printf("%c ", node->op);
}

/**********************************
销毁二叉树，释放系统资源
**********************************/
void free_tree(struct node* root)
{
if(root != NULL){
free_tree(root->left);
free_tree(root->right);
free(root);
}
}

/**********************************
二叉树的遍历
**********************************/
// 先序遍历
void prefix_travel(const struct node* root)
{
if (root != NULL){
print_node(root);
prefix_travel(root->left);
prefix_travel(root->right);
}
}

// 中序遍历
void infix_travel(const struct node* root, const struct node* parent)
{
if (root != NULL){
bool bBracket = false;
if (root->type == NODE_OPERATOR){
if ( (root->op == ' ' || root->op == '-') &&
(parent != NULL) &&
(parent->op == '*' || parent->op == '/')){
printf("(");
bBracket = true;
}
}

infix_travel(root->left, root);
print_node(root);
infix_travel(root->right, root);
if (bBracket) printf(") ");
}
}

// 后序遍历
void postfix_travel(const struct node* root)
{
if (root != NULL){
postfix_travel(root->left);
postfix_travel(root->right);
print_node(root);
}
}

/**********************************************************
解析前缀表达式。
目前仅识别 - * / 空格和数字，遇到其他字符视为非法输入。

解析成功返回true
**********************************************************/
bool parse_expression(const char* exp)
{
char digits[20];
char c;

while((c = *exp )){
if (isspace(c)) continue;
if (c == ' ' || c == '-' || c == '*' || c == '/'){
push_node(new_operator_node(c));
}else if (isdigit(c)){
int i = 0;
do{
digits[i ] = c;
}while((c = *exp ) && isdigit(c));

digits[i] = '\0';
push_node(new_data_node(atoi(digits)));
if (c == '\0') break;
if (!isspace(c)){
return false;
}
}else{
return false;
}
}
return true;
}

/*
从stack_node 生成二叉表达式树。
成功返回根节点指针；如果表达式错误返回NULL
*/
struct node* build_tree()
{
struct node* left;
struct node* right;
struct node* tmp;
struct node* stack[MAX_ELEM];
int top = -1;

while(top_node() != NULL){
while(top_node() != NULL && top_node()->type == NODE_DATA){
stack[ top] = pop_node();
}
if (top_node() == NULL || (top 1) < 2) return NULL;

// 栈顶节点为 操作符
left = stack[top--];
right = stack[top--];
tmp = pop_node();
tmp->left = left;
tmp->right = right;
stack[ top] = tmp;
}

if (top > 0){
free_tree(stack[top--]);
while(top >= 0) free(stack[top--]);
return NULL;
}

return (top == 0 ? stack[0] : NULL);
}

int main()
{
struct node* root;
char exp[200] = " 2 * 3 4 - 5 * - 6 7 8";
do{
if (parse_expression(exp) && (root = build_tree()) != NULL){
printf("prefix exp: ");
prefix_travel(root);
printf("\n");

printf("infix exp: ");
infix_travel(root, NULL);
printf("\n");

printf("postfix exp: ");
postfix_travel(root);
printf("\n");
}else{
printf("Bad expression\n");
}

// do clean-up
free_tree(root);
while((root = top_node())) free(pop_node());

printf("\nInput expression in prefix-mode:\n");
}while(fgets(exp, sizeof(exp), stdin));

return 0;
}

boxban(冻酸梨) 于 2005-6-23 22:45:29
下面是一些测试用例：
=====================================================
Input expression in prefix-mode:
- 1 * * - 2 3 4 5 6 7 8
prefix exp: - 1 * * - 2 3 4 5 6 7 8
infix exp: 1 ((2 - 3 ) * 4 5 ) * 6 - 7 8
postfix exp: 1 2 3 - 4 * 5 6 * 7 8 -

Input expression in prefix-mode:
- 2 / 3 4 - 5 6 * - 27 28 29
prefix exp: - 2 / 3 4 - 5 6 * - 27 28 29
infix exp: 2 3 / (4 5 - 6 ) - (27 - 28 ) * 29
postfix exp: 2 3 4 5 6 - / 27 28 - 29 * -

Input expression in prefix-mode:
- 2 / 3 4 - 5 6 * - 7 8 9 10
Bad expression

=====================================================================
boxban(冻酸梨) 于 2005-6-23 23:22:44
闲着无聊，画了对应于 “- 1 * * - 2 3 4 5 6 7 8”的表达式二叉树

-
/ / \ \ 
1 * / \ 6 / \ * 5 \ 
/ \ 
- 4 / / \ 7 8
2 3

yangfasheng(悟法:前面是绝路,希望在拐角) 于 2005-6-24 8:17:05

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define MaxNode25
#define FALSE0
#define OK1
#define Datatype char 
// 数据域的数据类型设为字符
char str[]="ABD##E##CF##G##";/*用于测试的字符串*/
int index =0;
typedef struct BTreeNode
{
Datatype data;
struct BTreeNode *LChild;
struct BTreeNode *RChild;
}BTree;

int InitBTree( BTree **bt )
{
(*bt) = (BTree *)malloc(sizeof(BTree));
if( (*bt) == NULL )return FALSE;
(*bt)->data = '\0';
(*bt)->LChild = NULL;
(*bt)->RChild = NULL;
return OK;
}
//按先根次序创建一棵二叉树。
int CreateBTree_PreOrder( BTree **bt)
{
char data = str[index ];

if( data == '#' || data=='\0')
(*bt) = NULL;
else
{
(*bt) = (BTree *)malloc(sizeof(BTree));
if( (*bt) == NULL )
exit(0);
(*bt)->data = data;
(*bt)->LChild = NULL;
(*bt)->RChild = NULL;

CreateBTree_PreOrder(&(*bt)->LChild);
CreateBTree_PreOrder(&(*bt)->RChild);
}
return OK;
}

// 层序遍历二叉树；
void LevelOrder( BTree *bt)
{
BTree *Queue[MaxNode];
int head,Rear;
int flag=1,i=0;
int Level=1;

if(bt==NULL)return;

head = -1;
Rear = 0;
Queue[Rear] = bt;
for( i=0; i<7; i )
printf(" ");
while( head != Rear )
{
head ;

printf("%c",Queue[head]->data );
if( flag != (pow(2,Level)-1))
{
for( i=0; i<30-6*Level; i )
printf(" ");
}
if( flag == (pow(2,Level)-1))
{
printf("\n\n\n");
for( i=0; i<20-Level*5; i )
printf(" ");
Level ;
}
flag ;

// 将队头结点的左孩子结点入队
if( Queue[head]->LChild != NULL )
{
Rear ;
Queue[Rear] = Queue[head]->LChild;
}

// 将队头结点的右孩子结点入队
if( Queue[head]->RChild != NULL )
{
Rear ;
Queue[Rear] = Queue[head]->RChild;
}
}
printf("\n");
}
/*
上面的函数可以自己写，以符合各自的显示要求

*/

// 左子树先入栈;
//非递归前序遍历二叉树。DLR
void NRPreOrder2(BTree *bt)
{
BTree *p;
BTree *stack[MaxNode];
int top = -1;
if( bt == NULL )return ;
p = bt;


while( !(top <0 && p == NULL) )
{
while( p!= NULL )
{
printf("%c ",p->data);
stack[ top] = p;
p = p->LChild;
}

if( top <0 )return ;
p = stack[top];stack[top--] = NULL;
p = p->RChild;
}
}

//前序遍历二叉树。DLR
void PreOrder(BTree *bt)
{
if( bt == NULL )
return ;//递归出口。
printf("%c ",bt->data);

if( bt->LChild != NULL )
PreOrder(bt->LChild);//前序递归遍历二叉树的左子树；
if( bt->RChild != NULL )
PreOrder(bt->RChild);//前序递归遍历二叉树的右子树；
}
int main(int argc, char* argv[])
{
BTree *bt;
if( FALSE == InitBTree(&bt) )
{
printf("The head node Creates is fail!\n");
exit(0);
}

CreateBTree_PreOrder(&bt->LChild);index=0;
printf("The Binary Tree:\n");
LevelOrder( bt->LChild );

//printBTree(bt,0);

printf("\n前序遍历二叉树!\n");
PreOrder(bt->LChild);
printf("\n");
NRPreOrder2(bt->LChild);
return 0;
}