C++数据结构——二叉树
问题 1: 满二叉树的先、中、后序遍历
题目描述
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的前序遍历序列。
输入
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。
输出
输出该满二叉数的先、中、后序遍历序列。
样例输入
3
B A C
样例输出
BAC
ABC
ACB
代码实现
创建满二叉树
intdeep(int num)//通过结点个数来计算满二叉树深度{
num+=1;int n=0;while(num!=1){
n++;
num/=2;}return n;}boolset(node* root,int deep)//利用二叉树深度在给定的根节点建立满二叉树{if(deep==0)returntrue;
deep--;if(deep==0)returntrue;
root->liftchild=new node;
root->rightchild=new node;set(root->liftchild,deep);set(root->rightchild,deep);returntrue;}将给定的字母压入队列
queue<char> temp;for(int i=0;i<num;i++){char temp;
cin>>temp;
list.push(temp);}利用队列和层次遍历给满二叉树赋值
voidlevels(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);}}}先序遍历
voidpreOrder(node*subTree){if(subTree!=NULL){
cout<<subTree->data;preOrder(subTree->liftchild);preOrder(subTree->rightchild);}}中序遍历
voidinOrder(node*subTree){if(subTree!=NULL){inOrder(subTree->liftchild);
cout<<subTree->data;inOrder(subTree->rightchild);}}后序遍历
voidpostOrder(node*subTree){if(subTree!=NULL){postOrder(subTree->liftchild);postOrder(subTree->rightchild);
cout<<subTree->data;}}完整代码
#include<iostream>#include<queue>usingnamespace std;structnode{
node*liftchild=NULL,*rightchild=NULL;char data;} root;intdeep(int num){
num+=1;int n=0;while(num!=1){
n++;
num/=2;}return n;}boolset(node* root,int deep){if(deep==0)returntrue;
deep--;if(deep==0)returntrue;
root->liftchild=new node;
root->rightchild=new node;set(root->liftchild,deep);set(root->rightchild,deep);returntrue;}voidlevels(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.push( q->liftchild);}if( q->rightchild!=NULL){
que.push( q->rightchild);}}}voidpreOrder(node*subTree)//先序{if(subTree!=NULL){
cout<<subTree->data;preOrder(subTree->liftchild);preOrder(subTree->rightchild);}}voidinOrder(node*subTree)//中序{if(subTree!=NULL){inOrder(subTree->liftchild);
cout<<subTree->data;inOrder(subTree->rightchild);}}voidpostOrder(node*subTree)//后序{if(subTree!=NULL){postOrder(subTree->liftchild);postOrder(subTree->rightchild);
cout<<subTree->data;}}intmain(){
queue<char> list,temp;int num;
cin>>num;for(int i=0;i<num;i++){char temp;
cin>>temp;
list.push(temp);}
num=deep(num);set(&root,num);levels(list,&root);preOrder(&root);
cout<<endl;inOrder(&root);
cout<<endl;postOrder(&root);return0;}问题 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.寻址函数的实现（由结点编号找到对应静态地址）
intfindlast(node sub[],int n,int num){int i=0;for(;i<n;i++){if(sub[i].data==num)return i;}return-1;}2.寻根函数（由数据找到根结点的静态地址）
intfindRoot(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;}}}先序遍历
voidpreOrder(node sub[],int root){if(root!=-1){
cout<<sub[root].data<<" ";preOrder(sub,sub[root].liftchild);preOrder(sub,sub[root].rightchild);}}中序遍历
voidinOrder(node sub[],int root){if(root!=-1){inOrder(sub,sub[root].liftchild);
cout<<sub[root].data<<" ";inOrder(sub,sub[root].rightchild);}}后序遍历
voidpostOrder(node sub[],int root){if(root!=-1){postOrder(sub,sub[root].liftchild);postOrder(sub,sub[root].rightchild);
cout<<sub[root].data<<" ";}}完整代码
#include<iostream>#include<queue>usingnamespace std;structnod{int _1=0;int _2=0;int _0=0;};structnode{int data=0;int liftchild=0;int rightchild=0;};intfindlast(nod sub[],int n,int num){int i=0;for(;i<n;i++){if(sub[i]._0==num)return i;}return-1;}intfindRoot(nod 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]._1!=-1){int temp=sub[i]._1-1;
a[temp]++;}if(sub[i]._2!=-1){int temp=sub[i]._2-1;
a[temp]++;}}for(int i=0;i<n;i++){if(a[i]==0){returnfindlast(sub,n,i+1);}}}voidpreOrder(node sub[],int root){if(root!=-1){
cout<<sub[root].data<<" ";preOrder(sub,sub[root].liftchild);preOrder(sub,sub[root].rightchild);}}voidinOrder(node sub[],int root){if(root!=-1){inOrder(sub,sub[root].liftchild);
cout<<sub[root].data<<" ";inOrder(sub,sub[root].rightchild);}}voidpostOrder(node sub[],int root){if(root!=-1){postOrder(sub,sub[root].liftchild);postOrder(sub,sub[root].rightchild);
cout<<sub[root].data<<" ";}}intmain(){int n;
cin>>n;
nod a[n];
node b[n];for(int i=0;i<n;i++){
cin>>a[i]._0;
cin>>a[i]._1;
cin>>a[i]._2;}for(int i=0;i<n;i++){
b[i].data=a[i]._0;
b[i].liftchild=findlast(a,n,a[i]._1);
b[i].rightchild=findlast(a,n,a[i]._2);}preOrder(b,findRoot(a,n));
cout<<endl;inOrder(b,findRoot(a,n));
cout<<endl;postOrder(b,findRoot(a,n));
cout<<endl;}问题 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);