题目描述
给定一颗二叉树的特定先序遍历结果，空树用字符‘0’表示，例如AB0C00D00表示如下图
请完成以下程序填空，建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果
输入
第一行输入一个整数t，表示有t个二叉树
第二行起输入每个二叉树的特定先序遍历结果，空树用字符‘0’表示，连续输入t行
输出
每个二叉树输出三行，对应先序遍历、中序遍历和后序遍历结果
输入样例1
2 AB0C00D00 AB00C00
输出样例1
ABCD BCAD CBDA ABC BAC BCA
思路分析
需要我们做的是实现树的建立和三种遍历方式。
给的是特定先序遍历的结果，递归建立树节点，递归结束的条件是字符串已经到了结尾或者碰到了字符0。
三种遍历方式只是输出数据的时候不同，先序遍历是先输出数据，再遍历左右子树，中序遍历是先遍历左子树，再输出数据，然后遍历右子树，后序遍历是先遍历左右子树，再输出数据，但它们都是先遍历左子树，再遍历右子树，递归结束条件是节点为空。
AC代码
代码语言：javascript复制//请完成上述类内部的私有函数实现
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;
}
//主函数
