C++数据结构——二叉树

C++数据结构——二叉树问题 1: 满二叉树的先、中、后序遍历题目描述

给你一个满二叉树的层次遍历序列，请编程输出该二叉树的前序遍历序列。

输入

第一行是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 temp;
for(int i=0;i
		char temp;
		cin>>temp;
		list.push(temp);
	}

利用队列和层次遍历给满二叉树赋值

void levels(queue&list,node *subnode)
{//层次遍历,利用队列实现 
	if(subnode == NULL )
		return;
	queue 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<data;
		preOrder(subTree->liftchild);
		preOrder(subTree->rightchild);
	}
}

中序遍历

void inOrder(node *subTree)
{
	if(subTree!=NULL)
	{
		
		inOrder(subTree->liftchild);
		cout<data;
		inOrder(subTree->rightchild);
	}
}

后序遍历

void postOrder(node *subTree)
{
	if(subTree!=NULL)
	{
		
		postOrder(subTree->liftchild);
		
		postOrder(subTree->rightchild);
		
		cout<data;
	}
}

完整代码

#include
#include 
using namespace std;
struct node
{
    node*liftchild=NULL,
         *rightchild=NULL;
    char data;
} root;
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;
}
 
 
void levels(queue&list,node *subnode){
    if(subnode == NULL )
        return;
     
    queue 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 );
        } 
    }
         
}
 
 
 
void preOrder(node *subTree)//先序
{
     
    if(subTree!=NULL)
    {
        cout<data;
        preOrder(subTree->liftchild);
        preOrder(subTree->rightchild);
    }
}

void inOrder(node *subTree)//中序
{
	if(subTree!=NULL)
	{
		
		inOrder(subTree->liftchild);
		cout<data;
		inOrder(subTree->rightchild);
	}
}
 
 void postOrder(node *subTree)//后序
{
	if(subTree!=NULL)
	{
		
		postOrder(subTree->liftchild);
		
		postOrder(subTree->rightchild);
		
		cout<data;
	}
}
 
int main()
{
    queue list,temp;
    int num;
    cin>>num;
    for(int i=0;i
        char temp;
        cin>>temp;
        list.push(temp);
    }
     
    num=deep(num);
    set(&root,num);
    levels(list,&root);
     
    preOrder(&root);
    cout< 
 
 
问题 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
		if(sub[i].data==num)
		return i;
	}
	return -1;
}
 
2.寻根函数（由数据找到根结点的静态地址） 
int findRoot(node sub[],int n)
{
	
	int a[n];
	for(int i=0;i
		a[i]=0;
	}
	for(int i=0;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
		if(a[i]==0)
		{
			return i+1;
		}
	}
} 
 
先序遍历 
void preOrder(node sub[],int root)
{
     
    if(root!=-1)
    {
        cout< 
中序遍历 
void inOrder(node sub[],int root)
{
     
    if(root!=-1)
    {
        
        inOrder(sub,sub[root].liftchild);
        cout< 
后序遍历 
 void postOrder(node sub[],int root)
{
     
    if(root!=-1)
    {
        
        postOrder(sub,sub[root].liftchild);
        postOrder(sub,sub[root].rightchild);
        cout< 
完整代码 
#include
#include 
using namespace std;
struct nod
{
    int _1=0;
    int _2=0;
    int _0=0;
};
struct node
{
    int data=0;
    int liftchild=0;
    int rightchild=0; 
};
 
 
int findlast(nod sub[],int n,int num)
{
    int i=0;
    for(;i
        if(sub[i]._0==num)
        return i;
         
    }
    return -1;
}
 
int findRoot(nod sub[],int n)
{
     
    int a[n];
    for(int i=0;i
        a[i]=0;
    }
    for(int i=0;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
        if(a[i]==0)
        {
            return findlast(sub,n,i+1);
        }
    }
}
 
void preOrder(node sub[],int root)
{
     
    if(root!=-1)
    {
        cout<
     
    if(root!=-1)
    {
        
        inOrder(sub,sub[root].liftchild);
        cout<
     
    if(root!=-1)
    {
        
        postOrder(sub,sub[root].liftchild);
        postOrder(sub,sub[root].rightchild);
        cout<
    int n;
    cin>>n;
    nod a[n];
    node b[n];
     
    for(int i=0;i
 
        cin>>a[i]._0;
     
        cin>>a[i]._1;
         
        cin>>a[i]._2;
    }
     
     
     
     
    for(int i=0;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< 
 
 
问题 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 que;
	int n=pow(2,num);
	for(int i=0;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 &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<data;
	}
}
 
完整代码 
#include
#include
#include
using namespace std;
struct node
{
	node*liftchild=NULL,
		*rightchild=NULL;
	char data;
};

bool set(queue &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<data;
	}
}


int main()
{
	int num;
	cin>>num;
	queue que;
	int n=pow(2,num);
	for(int i=0;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);
	}
	set(que);
	node *root=que.front();
	postOrder(root);
	return 0;
	
}

C++数据结构——二叉树

C/C++/C#相关栏目本月热门文章