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

论坛 期权论坛 期权     
manman花花   2018-4-26 13:55   3429   1
分享到 :
0 人收藏

1 个回复

倒序浏览
2#
鷹弈  1级新秀 | 2018-4-30 01:58:17 发帖IP地址来自
将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点

先序遍历则得到前缀式

中序遍历则得到中缀式

后序遍历则得到后缀式

//以(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");
}
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP