如何将将算术表达式转化成二叉树

发布网友发布时间：2022-08-14 14:21

共1个回答

热心网友时间：2024-10-26 11:30

将操作数作为二叉树的叶子结点，操作符作为二叉树的非叶子结点

先序遍历则得到前缀式

中序遍历则得到中缀式

后序遍历则得到后缀式

//以(a+b)/c-d+e*f进行演示

+
(- *)
(/ d) (e f)
(+ c)
(a b)

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

typedef char Elem;

typedef struct Node
{
Elem data;
struct Node *pLchild;
struct Node *pRchild;
}BTreeNode, *BTree;

BTree CreateBTree(BTree T, Elem *str)//创建二叉树
{
static int i = 0;

if ('0' == str[i])
{
T = NULL;
}
else
{
T = (BTree) malloc (sizeof(BTreeNode));
T->data = str[i++];

T->pLchild = CreateBTree(T->pLchild, str);
i++;
T->pRchild = CreateBTree(T->pRchild, str);
}

return T;
}

void PostTraverseBTree(BTree T)//后序
{
if (NULL != T)
{
PostTraverseBTree(T->pLchild);
PostTraverseBTree(T->pRchild);
printf("%c ", T->data);
}
}

void InTraverseBTree(BTree T)//中序
{
if (NULL != T)
{
InTraverseBTree(T->pLchild);
printf("%c ", T->data);
InTraverseBTree(T->pRchild);
}
}

void PreTraverseBTree(BTree T)//前序
{
if (NULL != T)
{
printf("%c ", T->data);
PreTraverseBTree(T->pLchild);
PreTraverseBTree(T->pRchild);
}
}

int main(void)
{
BTree T = NULL;

Elem str[] = "+-/+a00b00c00d00*e00f00";

T = CreateBTree(T, str);
printf("\n\n");

printf("先序遍历(前缀式):\n");
PreTraverseBTree(T);
printf("\n\n");

printf("中序遍历(中缀式):\n");
InTraverseBTree(T);
printf("\n\n");

printf("后序遍历(后缀式):\n");
PostTraverseBTree(T);
printf("\n\n");
}