【程序填空】二叉树三种遍历

叶茂林

发布于 2023-07-30 11:48:00

2470

发布于 2023-07-30 11:48:00

文章被收录于专栏：叶子的开发者社区

题目描述

给定一颗二叉树的特定先序遍历结果，空树用字符‘0’表示，例如AB0C00D00表示如下图

请完成以下程序填空，建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的特定先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每个二叉树输出三行，对应先序遍历、中序遍历和后序遍历结果

输入样例1

2 AB0C00D00 AB00C00

输出样例1

ABCD BCAD CBDA ABC BAC BCA

思路分析

需要我们做的是实现树的建立和三种遍历方式。

给的是特定先序遍历的结果，递归建立树节点，递归结束的条件是字符串已经到了结尾或者碰到了字符0。

三种遍历方式只是输出数据的时候不同，先序遍历是先输出数据，再遍历左右子树，中序遍历是先遍历左子树，再输出数据，然后遍历右子树，后序遍历是先遍历左右子树，再输出数据，但它们都是先遍历左子树，再遍历右子树，递归结束条件是节点为空。

AC代码

//请完成上述类内部的私有函数实现
BiTreeNode* BiTree::CreateTree() {
    if(pos==sTree.size()||sTree[pos]=='0'){
        pos++;
        return NULL;
    }

    BiTreeNode*T=new BiTreeNode();
    T->data=sTree[pos++];
    T->leftChild=CreateTree();
    T->rightChild=CreateTree();
    return T;
}
void BiTree::PreOrder(BiTreeNode*T) {
    if(T==NULL)
        return;
    cout<<T->data;
    PreOrder(T->leftChild);
    PreOrder(T->rightChild);
}
void BiTree::InOrder(BiTreeNode *T) {
    if(T==NULL)
        return;
    InOrder(T->leftChild);
    cout<<T->data;
    InOrder(T->rightChild);
}
void BiTree::PostOrder(BiTreeNode *T) {
    if(T==NULL)
        return;
    PostOrder(T->leftChild);
    PostOrder(T->rightChild);
    cout<<T->data;
}
//主函数

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-25，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树