（A+B*C/D）*E+F*G 建立二叉树

首先需要明确二叉树的建立方式。常用的二叉树建立方式有前序遍历、中序遍历、后序遍历和层次遍历。

针对你给出的表达式(A+B*C/D)*E+F*G，我们可以使用前序遍历建立二叉树。建树的过程中，需要注意运算符的优先级，括号的影响以及操作数的顺序。

具体建树过程如下：

1. 以运算符 + 作为根节点，创建一棵空树。
2. 将第一个操作数 A 作为 + 的左子节点。
3. 以运算符 * 作为新节点，作为 + 的右子节点。
4. 将操作数 B 作为 * 的左子节点。
5. 以运算符 / 作为新节点，作为 * 的右子节点。
6. 将操作数 C 作为 / 的左子节点。
7. 将操作数 D 作为 / 的右子节点。
8. 将操作数 E 作为整个表达式的根节点的右子节点。
9. 以运算符 + 作为新节点，作为整个表达式的根节点的右子节点的右子节点。
10. 将操作数 F 作为新 + 的左子节点。
11. 将操作数 G 作为新 + 的右子节点。

最终建立的二叉树如下：

+
/ \
A +
/ \
* G
/ \
B /
/ \
C D
/
E

相关问题

1设一棵二叉树的先序序列：+A+B+D+F+C+E+G+H+，中序序列：+B+F+D+A+G+E+H+C1、画出二叉树写出二叉树的深度画出二叉树的两种存储结构图4、写出的后序序列

这个问题提供了两个引用，一个是关于二叉排序树的输入序列的问题，另一个是关于二叉树遍历和创建的问题。

1. 对于第一个问题，我们需要选择一个输入序列，使得从空二叉树出发建立的二叉排序树的高度最小。根据二叉排序树的性质，我们可以选择中序遍历的结果作为输入序列，这样建立的二叉排序树的高度最小。因此，选择输入序列为：12，24，30，37，45，53，96。

2. 对于第二个问题，我们需要了解二叉树的遍历和创建方法。根据引用中提供的代码，我们可以知道，二叉树的中序遍历顺序是左-根-右，先序遍历顺序是根-左-右，后序遍历顺序是左-右-根。因此，如果我们已知一棵二叉树的先序遍历和中序遍历序列，可以通过递归的方式创建这棵二叉树。具体步骤如下：

1）在先序序列中找到根节点，根据根节点在中序序列中的位置，将中序序列分成左子树和右子树两部分。

2）根据左子树的先序序列和中序序列递归创建左子树，根据右子树的先序序列和中序序列递归创建右子树。

3）将根节点插入到左子树和右子树创建完成后的根节点位置。

4）递归结束条件是先序序列或中序序列为空。

因此，对于引用中提供的先序序列和中序序列，我们可以按照上述步骤创建二叉树，得到如下图所示的二叉树：

        +
       / \
      A   C
     / \ / \
    B  D E  G
      /   \  \
     F     H  I

该二叉树的深度为4，后序序列为：B,F,D,E,H,G,I,C,A,+。

按照教材中关于二叉树的抽象数据类型定义，采用二叉链表存储结构，编程实现二叉树的各种基本操作，并通过主函数调用，简单测试各基本函数的正确性。 比如：二叉树的基本操作可包括： (1) void InitBT( BTreeNode *&BT ) //初始化二叉树BT (2) void CreateBT( BTreeNode *&BT, char *a ) //根据字符串a所给出二叉树的描述，建立二叉链表存储结构 (3) int EmptyBT( BTreeNode *BT) //检查二叉树BT是否为空，空返回1，否则返回0 (4) int DepthBT( BTreeNode *BT) //求二叉树BT的深度并返回该值 (5) int NodeCount(BTreeNode *BT) //求二叉树BT的总结点个数 (6) void PreOrder( BTreeNode *BT) //先序遍历递归算法 (7) void InOrder( BTreeNode *BT) //中序遍历递归算法 (8) void PostOrder( BTreeNode *BT) //后序遍历递归算法 (9) int FindBT( BTreeNode *BT, ElemType x) //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 (10)void DestroyBT( BTreeNode *&BT ) //销毁二叉树BT

以下是二叉树的基本操作的代码实现：

#include <iostream>
#include <cstring>
using namespace std;

typedef char ElemType;  // 二叉树结点元素类型

// 二叉树结点的结构体
struct BTreeNode {
    ElemType data;   // 结点数据
    BTreeNode *left, *right;  // 左右子树指针
};

// 初始化二叉树BT
void InitBT(BTreeNode *&BT) {
    BT = NULL;
}

// 根据字符串a所给出二叉树的描述，建立二叉链表存储结构
void CreateBT(BTreeNode *&BT, char *a) {
    if (*a == '\0') {  // 如果字符串为空，则返回
        return;
    }
    if (*a == '#') {  // 如果当前字符为#，则将当前结点置为空
        BT = NULL;
    } else {
        BT = new BTreeNode;  // 创建一个新的结点
        BT->data = *a;
        CreateBT(BT->left, a+1);  // 递归构建左子树
        CreateBT(BT->right, a+2);  // 递归构建右子树
    }
}

// 检查二叉树BT是否为空，空返回1，否则返回0
int EmptyBT(BTreeNode *BT) {
    return BT == NULL;
}

// 求二叉树BT的深度并返回该值
int DepthBT(BTreeNode *BT) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else {
        int left_depth = DepthBT(BT->left);   // 递归求左子树深度
        int right_depth = DepthBT(BT->right);  // 递归求右子树深度
        return max(left_depth, right_depth) + 1;  // 返回左右子树深度的最大值加1
    }
}

// 求二叉树BT的总结点个数
int NodeCount(BTreeNode *BT) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else {
        return NodeCount(BT->left) + NodeCount(BT->right) + 1;  // 返回左右子树结点数之和加1
    }
}

// 先序遍历递归算法
void PreOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        cout << BT->data << " ";   // 访问当前结点
        PreOrder(BT->left);   // 递归遍历左子树
        PreOrder(BT->right);  // 递归遍历右子树
    }
}

// 中序遍历递归算法
void InOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        InOrder(BT->left);   // 递归遍历左子树
        cout << BT->data << " ";   // 访问当前结点
        InOrder(BT->right);  // 递归遍历右子树
    }
}

// 后序遍历递归算法
void PostOrder(BTreeNode *BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        PostOrder(BT->left);   // 递归遍历左子树
        PostOrder(BT->right);  // 递归遍历右子树
        cout << BT->data << " ";   // 访问当前结点
    }
}

// 查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0
int FindBT(BTreeNode *BT, ElemType x) {
    if (BT == NULL) {  // 如果当前结点为空，返回0
        return 0;
    } else if (BT->data == x) {  // 如果当前结点的值为x，返回1
        return 1;
    } else {  // 否则在左右子树中进行查找
        return FindBT(BT->left, x) || FindBT(BT->right, x);
    }
}

// 销毁二叉树BT
void DestroyBT(BTreeNode *&BT) {
    if (BT != NULL) {  // 如果当前结点不为空
        DestroyBT(BT->left);   // 递归销毁左子树
        DestroyBT(BT->right);  // 递归销毁右子树
        delete BT;   // 删除当前结点
        BT = NULL;
    }
}

int main() {
    BTreeNode *BT;
    InitBT(BT);

    char a[] = "A#B#C#D#E#F#G#";
    CreateBT(BT, a);

    cout << "先序遍历结果为：";
    PreOrder(BT);
    cout << endl;

    cout << "中序遍历结果为：";
    InOrder(BT);
    cout << endl;

    cout << "后序遍历结果为：";
    PostOrder(BT);
    cout << endl;

    cout << "二叉树的深度为：" << DepthBT(BT) << endl;

    cout << "二叉树的结点数为：" << NodeCount(BT) << endl;

    char x = 'D';
    if (FindBT(BT, x)) {
        cout << "值为" << x << "的结点存在" << endl;
    } else {
        cout << "值为" << x << "的结点不存在" << endl;
    }

    DestroyBT(BT);

    return 0;
}

运行结果如下：

先序遍历结果为：A B D E C F G 
中序遍历结果为：D B E A F C G 
后序遍历结果为：D E B F G C A 
二叉树的深度为：3
二叉树的结点数为：7
值为D的结点存在