给你一个满二叉树的层次遍历序列，请编程输出该二叉树的前序遍历序列。
输入第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出输出该满二叉数的先、中、后序遍历序列。
样例输入3
B A C
BAC
ABC
ACB
创建满二叉树
int deep(int num)//通过结点个数来计算满二叉树深度
{
num+=1;
int n=0;
while(num!=1)
{
n++;
num/=2;
}
return n;
}
bool set(node* root,int deep)//利用二叉树深度在给定的根节点建立满二叉树
{
if(deep==0)return true;
deep--;
if(deep==0)return true;
root->liftchild=new node;
root->rightchild=new node;
set(root->liftchild,deep);
set(root->rightchild,deep);
return true;
}
将给定的字母压入队列
queue<char> temp;
for(int i=0;i<num;i++)
{
char temp;
cin>>temp;
list.push(temp);
}
利用队列和层次遍历给满二叉树赋值
void levels(queue<char>&list,node *subnode)
{//层次遍历,利用队列实现
if(subnode == NULL )
return;
queue<node *> que;//构造一个树结点指针的队列
que.push(subnode);
while(!que.empty())
{
node *q = que.front();
q->data=list.front();
list.pop();
que.pop();
if( q->liftchild != NULL)//que.front()拿到最前结点
{
que.push( q->liftchild );
}
if( q->rightchild != NULL)
{
que.push( q->rightchild );
}
}
}
先序遍历
void preOrder(node *subTree)
{
if(subTree!=NULL)
{
cout<<subTree->data;
preOrder(subTree->liftchild);
preOrder(subTree->rightchild);
}
}
中序遍历
void inOrder(node *subTree)
{
if(subTree!=NULL)
{
inOrder(subTree->liftchild);
cout<<subTree->data;
inOrder(subTree->rightchild);
}
}
后序遍历
void postOrder(node *subTree)
{
if(subTree!=NULL)
{
postOrder(subTree->liftchild);
postOrder(subTree->rightchild);
cout<<subTree->data;
}
}
完整代码
#include问题 2: 任意二叉树的先、中、后序遍历 题目描述
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的前序遍历序列。
输入第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。
输出输出该二叉数的先、中、后序遍历序列。
样例输入4
1 2 4
3 1 -1
2 -1 -1
4 -1 -1
3 1 2 4
2 1 4 3
2 4 1 3
首先将输入数据转变为常规静态二叉树（左右孩子表示地址）
1.寻址函数的实现（由结点编号找到对应静态地址）
int findlast(node sub[],int n,int num)
{
int i=0;
for(;i<n;i++)
{
if(sub[i].data==num)
return i;
}
return -1;
}
2.寻根函数（由数据找到根结点的静态地址）
int findRoot(node sub[],int n)
{
int a[n];
for(int i=0;i<n;i++)
{
a[i]=0;
}
for(int i=0;i<n;i++)
{
if(sub[i].liftchild!=-1)
{
int temp=sub[i].liftchild-1;
a[temp]++;
}
if(sub[i].rightchild!=-1)
{
int temp=sub[i].rightchild-1;
a[temp]++;
}
}
for(int i=0;i<n;i++)
{
if(a[i]==0)
{
return i+1;
}
}
}
先序遍历
void preOrder(node sub[],int root)
{
if(root!=-1)
{
cout<<sub[root].data<<" ";
preOrder(sub,sub[root].liftchild);
preOrder(sub,sub[root].rightchild);
}
}
中序遍历
void inOrder(node sub[],int root)
{
if(root!=-1)
{
inOrder(sub,sub[root].liftchild);
cout<<sub[root].data<<" ";
inOrder(sub,sub[root].rightchild);
}
}
后序遍历
void postOrder(node sub[],int root)
{
if(root!=-1)
{
postOrder(sub,sub[root].liftchild);
postOrder(sub,sub[root].rightchild);
cout<<sub[root].data<<" ";
}
}
完整代码
#include问题 3: FBI树 题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为 B 串，全“1”串称为 I 串，既含“0”又含“1”的串则称为 F 串。
FBI 树是一棵二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：
(1) T 的根结点为 R，其类型与串 S 的类型相同；
(2) 若串 S 的长度大于 1，可将串 S 从中间分开，分为等长的左右子串 S1 和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。
现在给定一个长度为 2N 的“01”串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。
输入第一行是一个整数 N（0≤N≤10），第二行是一个长度为 2N 的“01”串。
输出包括一行，这一行只包含一个字符串，即 FBI 树的后序遍历序列。
样例输入3
10001011
IBFBBBFIBFIIIFF
代码实现1.将二叉树结点初始化并且放在队列中
int num;
cin>>num;
queue<node*> que;
int n=pow(2,num);
for(int i=0;i<n;i++)
{
char temp;
cin>>temp;
node*p=new node;
switch(temp)
{
case '1':p->data='I';break;
case '0':p->data='B';break;
}
que.push(p);
}
利用队列创建满二叉树
bool set(queue<node*> &que)
{
if(que.size()==1)
return true;
node*temp;
node*p;
node*q;
p=que.front();
que.pop();
q=que.front();
que.pop();
temp=new node;
temp->liftchild=p;
temp->rightchild=q;
if(p->data=='I'&&q->data=='I')
temp->data='I';
else if(p->data=='B'&&q->data=='B')
temp->data='B';
else
temp->data='F';
que.push(temp);
set(que);
}
后续遍历输出结果
void postOrder(node *subTree)
{
if(subTree!=NULL)
{
postOrder(subTree->liftchild);
postOrder(subTree->rightchild);
cout<<subTree->data;
}
}
完整代码
#include欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）