作业帮 > 综合 > 作业

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

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/03/28 18:58:33
如何将将算术表达式转化成二叉树
将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点
先序遍历则得到前缀式
中序遍历则得到中缀式
后序遍历则得到后缀式
//以(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;
\x09struct Node *pRchild;
}BTreeNode, *BTree;
BTree CreateBTree(BTree T, Elem *str)//创建二叉树
{
\x09static int i = 0;
\x09if ('0' == str[i])
\x09{
\x09\x09T = NULL;
\x09}
\x09else
\x09{
\x09\x09T = (BTree) malloc (sizeof(BTreeNode));
\x09\x09T->data = str[i++];
\x09\x09T->pLchild = CreateBTree(T->pLchild, str);
\x09\x09i++;
\x09\x09T->pRchild = CreateBTree(T->pRchild, str);
\x09}
\x09return T;
}
void PostTraverseBTree(BTree T)//后序
{
\x09if (NULL != T)
\x09{
\x09\x09PostTraverseBTree(T->pLchild);
\x09\x09PostTraverseBTree(T->pRchild);
\x09\x09printf("%c ", T->data);
\x09}
}
void InTraverseBTree(BTree T)//中序
{
\x09if (NULL != T)
\x09{
\x09\x09InTraverseBTree(T->pLchild);
\x09\x09printf("%c ", T->data);
\x09\x09InTraverseBTree(T->pRchild);
\x09}
}
void PreTraverseBTree(BTree T)//前序
{
\x09if (NULL != T)
\x09{
\x09\x09printf("%c ", T->data);
\x09\x09PreTraverseBTree(T->pLchild);
\x09\x09PreTraverseBTree(T->pRchild);
\x09}
}
int main(void)
{
\x09BTree T = NULL;
\x09Elem str[] = "+-/+a00b00c00d00*e00f00";
\x09T = CreateBTree(T, str);
\x09printf("\n\n");
\x09printf("先序遍历(前缀式):\n");
\x09PreTraverseBTree(T);
\x09printf("\n\n");
\x09printf("中序遍历(中缀式):\n");
\x09InTraverseBTree(T);
\x09printf("\n\n");
\x09printf("后序遍历(后缀式):\n");
\x09PostTraverseBTree(T);
\x09printf("\n\n");
}