本文共 1841 字，大约阅读时间需要 6 分钟。

扩展二叉树的先序遍历序列处理方法及中序遍历结果输出

首先，理解扩展二叉树的结构及其遍历方式。扩展二叉树中，叶子结点用‘#’表示，其余节点为普通节点。先序遍历（Preorder Traversal）是指先访问左子树，接着根节点，最后右子树。

处理步骤如下：

代码实现关键点：

• 递归构建树时，根据节点是否为‘#’确定其是否为叶子节点，并设置ltag和rtag。
• 中序遍历时，处理左子树、当前节点、右子树，确保顺序正确。
• 处理输入字符串时，正确分割并处理特殊符号‘#’。

示例分析：输入序列“A B # # C D # E # F # # G H # I K # # # #”对应结构如图，输出结果为各节点的ltag、data和rtag。

代码实现：

#include 
   
    #include 
    
     using namespace std;struct Node {    int ltag, rtag;    char data;    Node* Lchild, *Rchild;};class Text {private:    Node* root;public:    Text() { root = Creat(); }    ~Text() { Release(root); }    void PreOrder() {        PreOrder(root);    }    void Judge(Node* Bt) {        if (Bt->Lchild == NULL) {            Bt->ltag = 1;        } else {            Bt->ltag = 0;        }        if (Bt->Rchild == NULL) {            Bt->rtag = 1;        } else {            Bt->rtag = 0;        }        cout << Bt->ltag << " " << Bt->data << " " << Bt->rtag << endl;    }    void PreOrder(Node* Bt) {        if (Bt == NULL) return;        PreOrder(Bt->Lchild);        Judge(Bt);        PreOrder(Bt->Rchild);    }    Node* Creat() {        char ch;        cin >> ch;        if (ch == '#') {            return NULL;        } else {            Node* Bt = new Node;            Bt->data = ch;            Bt->Lchild = Creat();            Bt->Rchild = Creat();            return Bt;        }    }    void Release(Node* Bt) {        if (Bt == NULL) return;        Release(Bt->Lchild);        Release(Bt->Rchild);        delete Bt;    }    static void main() {        Text T;        T.PreOrder();    }};int main() {    Text::main();    return 0;}
    
   

代码解释：

• 结构Node包含ltag、data、rtag和左右子树指针。
• Text类处理树的构建与遍历，使用递归方法。
• Creat函数解析输入字符，构建节点，处理叶子节点‘#’。
• PreOrder函数进行中序遍历，Judge函数输出节点信息。
• 主函数启动程序，执行前序遍历并输出结果。