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

鷹弈 · 2018-4-30 01:58:17

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

先序遍历则得到前缀式

中序遍历则得到中缀式

后序遍历则得到后缀式

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

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

#include
#include

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)
{
  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");
}

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

1 个回复