概述
题目描述
给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构,并输出该二叉树的先序遍历、中序遍历和后序遍历结果
输入 第一行输入一个整数t,表示有t个二叉树第二行起输入每个二叉树的先序遍历结果,空树用字符‘0’表示,连续输入t行
输出 输出每个二叉树的先序遍历、中序遍历和后序遍历结果
样例输入 2
AB0C00D00
AB00C00
样例输出
ABCD
BCAD
CBDA
ABC
BAC
BCA
思路
#include<iostream>
#include<string>
using namespace std;
class BiTreeNode{
public:
char data;
BiTreeNode *LeftChild;
BiTreeNode *RightChild;
BiTreeNode():LeftChild(NULL), RightChild(NULL){
}
~BiTreeNode(){
}
};
class BiTree{
private:
BiTreeNode *Root;
int pos;
string strTree;
BiTreeNode* CreateBiTree(){//递归建树
BiTreeNode *T;
char ch;
ch= strTree[pos++];
if(ch== '0')//如果是‘0’说明是空
T= NULL;
else{
T= new BiTreeNode();
T->data= ch;
T->LeftChild= CreateBiTree();
T->RightChild= CreateBiTree();
}
return T;
}
void PreOrder(BiTreeNode* t){//先序遍历
if(t){
cout<<t->data;
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}
}
void InOrder(BiTreeNode* t){//中序遍历
if(t){
InOrder(t->LeftChild);
cout<<t->data;
InOrder(t->RightChild);
}
}
void PostOrder(BiTreeNode* t){//后序遍历
if(t){
PostOrder(t->LeftChild);
PostOrder(t->RightChild);
cout<<t->data;
}
}
public:
BiTree(){
}
~BiTree(){
}
void CreateTree(string TreeArray){
pos= 0;
strTree.assign(TreeArray);
Root= CreateBiTree();
}
void PreOrder(){//公共接口调用私有函数
PreOrder(Root);
cout<<endl;
}
void InOrder(){
InOrder(Root);
cout<<endl;
}
void PostOrder(){
PostOrder(Root);
cout<<endl;
}
};
int main(){
int t;
cin>>t;
while(t--){
string str;
BiTree tree;
cin>>str;
tree.CreateTree(str);
tree.PreOrder();
tree.InOrder();
tree.PostOrder();
}
return 0;
}
最后
以上就是有魅力老鼠为你收集整理的DS二叉树--二叉树构建与遍历的全部内容,希望文章能够帮你解决DS二叉树--二叉树构建与遍历所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复