将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点
先序遍历则得到前缀式
中序遍历则得到中缀式
后序遍历则得到后缀式
//以(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");
} |