基于二叉链表的存储格式，输入二叉树的先序序列，用*代表空节点，如ABD**CE***F**建立二叉树，然后中序遍历二叉树，输出节点的值

基于二叉链表的存储格式，输入二叉树的先序序列，用*代表空节点，如ABD**CE***F**建立二叉树的步骤如下：
1. 创建一个结构体TreeNode，包含Data、Left和Right三个成员变量。
2. 定义一个函数Creat()，用于创建二叉树。在函数中，先输入一个字符，如果该字符为#，则代表该结点为空，返回NULL；否则，创建一个结点，并将该字符存入结点的Data中。接着，递归调用Creat()函数，将返回的结点存入当前结点的左子树中，再次递归调用Creat()函数，将返回的结点存入当前结点的右子树中。最后，返回插入内容后的树。
3. 调用Creat()函数，输入先序序列ABD**CE***F**，建立二叉树。
4. 对建立好的二叉树进行中序遍历，输出节点的值。中序遍历的步骤如下：
1）如果当前结点为空，则返回。
2）递归遍历当前结点的左子树。
3）输出当前结点的值。
4）递归遍历当前结点的右子树。

因此，中序遍历二叉树ABD**CE***F**的结果为：DBAECF。

相关问题

【问题描述】判断两棵二叉树是否结构相同。结构相同意味着对应的左子树和对应的右子树都 结构相同，不考虑数据内容。若已知两棵二叉树 B1 和 B2 皆为空, 或者皆不空且 B1 的左、右子 树和 B2 的左、右子树分别结构相同, 则称二叉树 B1 和 B2 结构相同。 【实验要求】 二叉树采用二叉链表存储，二叉链表定义如下： typedef char ElemType; typedef struct bitnode{ //定义二叉树节点结构 ElemType data; //数据域 struct bitnode *lchild,*rchild; //左右孩子指针域 }BiTNode,*BiTree; 【测试界面】 请输入（在空子树处添加*）二叉树 A 的先序序列： ABD*F***CE*** 请输入（在空子树处添加*）二叉树 B 的先序序列： MNA*B***FD*** [输出] 结构相同

以下是判断两棵二叉树是否结构相同的C++代码实现：

#include<iostream>
using namespace std;

typedef char ElemType;
typedef struct bitnode{
    ElemType data;
    struct bitnode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T){ //先序遍历创建二叉树
    ElemType ch;
    cin>>ch;
    if(ch == '*')
        T = NULL;
    else{
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

bool isSame(BiTree T1, BiTree T2){ //判断两棵二叉树是否结构相同
    if(T1 == NULL && T2 == NULL)
        return true;
    else if(T1 == NULL || T2 == NULL)
        return false;
    else{
        bool left = isSame(T1->lchild, T2->lchild);
        bool right = isSame(T1->rchild, T2->rchild);
        return left && right;
    }
}

int main(){
    BiTree A, B;
    cout<<"请输入（在空子树处添加*）二叉树 A 的先序序列：";
    CreateBiTree(A);
    cout<<"请输入（在空子树处添加*）二叉树 B 的先序序列：";
    CreateBiTree(B);
    if(isSame(A, B))
        cout<<"结构相同"<<endl;
    else
        cout<<"结构不同"<<endl;
    return 0;
}

输入示例：

请输入（在空子树处添加*）二叉树 A 的先序序列：ABD*F***CE***
请输入（在空子树处添加*）二叉树 B 的先序序列：MNA*B***FD***

输出示例：

结构相同

7-2 交换二叉树中每个结点的左孩子和右孩子 分数 16 作者 陈晓梅 单位 广东外语外贸大学 以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。 输入格式: 输入二叉树的先序序列。 提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。 输出格式: 输出有两行： 第一行是原二叉树的中序遍历序列； 第二行是交换后的二叉树的中序遍历序列。 输入样例: ABC##DE#G##F### 输出样例: CBEGDFA AFDGEBC

#’，表示该处是空节点。例如，先序序列为ABC##DE#G##F###的二叉树如下图所示：

输出格式：输出交换左右孩子之后的二叉树的先序序列。

示例：

输入:

ABD###CE##F##

输出:

ACF###EB##D##

解释：

输入的二叉树如下图所示：

经过左右孩子的交换，得到交换后的二叉树如下图所示：

交换后的二叉树的先序序列为ACF###EB##D##。