6-1 后缀式 分数 30 作者 YJ 单位 西南石油大学 本题要求实现一个函数，输出二叉树表示的表达式的后缀式。输入一个表达式的前缀形式（该表达式二叉树的扩展的先序序列），构造该二叉树，并输出其后序序列即为该表达式的后缀形式。 函数接口定义： void creat(BiTree &Tree)//构建二叉树 void PostOrder(BiTree Tree)//输出后缀表达式 其中 Tree 为用户传入的参数，指向根节点的指针。 裁判测试程序样例： #include<stdio.h> #include<malloc.h> #define len sizeof(struct BiTNode ) typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree; void creat(BiTree &Tree);//构建二叉树 void PostOrder(BiTree Tree);//后序输出二叉树 int main() { BiTree Tree; creat(Tree);//创建二叉树 printf("后缀表达式为："); PostOrder(Tree);//后序变量 return 0; } /* 请在这里填写答案 */

下面是creat和PostOrder函数的实现：

void creat(BiTree &Tree)
{
char c;
scanf("%c", &c);
if(c == '#')//如果读入的是#，说明该节点为空
{
Tree = NULL;
}
else
{
Tree = (BiTree)malloc(len);//创建新节点
Tree->data = c;//存储节点数据
creat(Tree->lchild);//递归创建左子树
creat(Tree->rchild);//递归创建右子树
}
}

void PostOrder(BiTree Tree)
{
if(Tree)//如果该节点不为空
{
PostOrder(Tree->lchild);//后序遍历左子树
PostOrder(Tree->rchild);//后序遍历右子树
printf("%c", Tree->data);//输出节点数据
}
}

相关问题

实现一个函数，输出二叉树表示的表达式的后缀式。

好的，我可以为您编写一个函数来输出二叉树表示的表达式的后缀式。以下是示例代码：

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def get_postfix(node):
    if not node:
        return ''
    left = get_postfix(node.left)
    right = get_postfix(node.right)
    return left + right + node.val + ' '

# 测试代码
root = Node('*')
root.left = Node('+')
root.left.left = Node('5')
root.left.right = Node('4')
root.right = Node('-')
root.right.left = Node('100')
root.right.right = Node('20')

print(get_postfix(root))  # 5 4 + 100 20 - *

这个函数接受一个指向根节点的二叉树节点作为输入，输出该表达式的后缀式。函数递归地遍历树的左右子节点，并通过后序遍历的方式将节点的值添加到后缀式中。最后返回后缀式字符串。

值得注意的是，该函数只能处理二叉树表示的表达式，如果是一般的表达式需要对表达式进行解析，将其转换为对应的二叉树再进行处理。

用C语言实现一个函数，输出二叉树表示的表达式的后缀式。

以下是用C语言实现输出二叉树表示的表达式的后缀式的函数：

#include<stdio.h>
#include<stdlib.h>
  
// 定义二叉树节点的数据结构
typedef struct node
{
    char data;
    struct node *left;
    struct node *right;
} BTree;
 
// 创建二叉树节点的函数
BTree *createNode(char ch)
{
    BTree *newNode = (BTree*)malloc(sizeof(BTree));
    newNode->data = ch;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
// 输出二叉树表示的表达式的后缀式的函数
void postOrder(BTree *root)
{
    if(root == NULL)
    {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}
 
int main()
{
    // 构建以下二叉树
    //      a
    //     / \
    //    b   c
    //   / \
    //  d   e
    BTree *root = createNode('a');
    root->left = createNode('b');
    root->right = createNode('c');
    root->left->left = createNode('d');
    root->left->right = createNode('e');
    printf("后缀式为：");
    postOrder(root);
 
    return 0;
}

输出：

后缀式为：d e b c a 

这里我们采用了二叉树的后序遍历（左子树、右子树、根节点），即先输出左子树的后缀式，再输出右子树的后缀式，最后输出根节点。这样就能得到二叉树表示的表达式的后缀式。