数据结构-递归练习-二叉树专题
|
C++,作业

第1关：基于二叉链表的树结构相等的判断与递归先序建立二叉树

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，按此方法创建两棵二叉树，然后编写递归算法判断这两棵树是否相等。

编程要求
输入
多组数据，每组数据有两行。每行为一个二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出一行。若两个二叉树相等输出“YES”，否则输出“NO”。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abcd00e00f00ig00h00
abd00e00cf00g00
abd00e00cf00h00
0

预期输出：
YES
NO

#include<iostream>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{////先序建立二叉树
/**************begin************/
    if(S[i]=='0')
        T=NULL;
    else{
        T=new BiTNode;
        T->data=S[i];
        CreateBiTree(T->lchild,S,++i);    
        CreateBiTree(T->rchild,S,++i);
    }
    /**************end************/
}
int Compare(BiTree T1,BiTree T2)
{//判断两棵二叉树是否相等，不相等返回0，相等返回1
/**************begin************/
    if(T1==NULL&&T2==NULL){
		return 1;
	}else if(T1!=NULL&&T2!=NULL){
		if(T1->data==T2->data){
			return(Compare(T1->lchild,T2->lchild)&&Compare(T1->rchild,T2->rchild));
		}else{
		return 0;
		}
	}else{
		return 0;
	}
    /**************end************/
}
int main()
{
	char S1[100],S2[100];
	while(cin>>S1&&S1[0]!='0')
	{
		cin>>S2;
		int i=-1,j=-1;
	  	BiTree T1,T2;
		CreateBiTree(T1,S1,++i);
		CreateBiTree(T2,S2,++j);
		if(!Compare(T1,T2))
			cout<<"NO"<<endl;
		else
			cout<<"YES"<<endl;
	}
	return 0;
}

主要除了实现函数的核心代码还要学习主函数中的写法。

第2关：基于二叉链表的二叉树左右孩子的交换（翻转二叉树）

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法交换该二叉树的左右孩子。

编程要求
输入
多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出一行。为交换左右孩子后的二叉树的先序序列。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abd00e00cf00g00
0

预期输出：
aihgbfced
acgfbed

#include<iostream>
#include<cstring>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void ChangeRL(BiTree &T)
{//二叉树左右孩子的交换
/**************begin************/
	if(T==NULL){
		return;
	}
	else if(T->lchild==NULL&&T->rchild==NULL)
		return;
	else{
		BiTree temp=T->lchild;
		T->lchild=T->rchild;
		T->rchild=temp;
		ChangeRL(T->lchild);
		ChangeRL(T->rchild);
	}

    /**************end************/
}
void PreOrderTraverse(BiTree T)
{//先序遍历
	if(T)
	{
    	cout<<T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
int main()
{
	char S[100];
	while(cin>>S)
    {
        if(strcmp(S,"0")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		ChangeRL(T);
		PreOrderTraverse(T);
		cout<<endl;
	}
	return 0;
}

解释：

  1. 基本情况： 如果节点为空（即 T == NULL），递归终止，直接返回。这是递归的出口。
  2. 叶子节点处理： 如果当前节点是叶子节点（即左右孩子都为 NULL），也不需要进行交换，直接返回。
  3. 交换左右孩子： 如果当前节点有左右孩子，交换 lchild 和 rchild，然后递归地调用 ChangeRL，对左右子树进行相同的左右孩子交换操作。

拓展：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树_哔哩哔哩_bilibili

第3关：基于二叉链表的二叉树的双序遍历

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法实现该二叉树的双序遍历（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。

编程要求
输入
多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出一行，为双序遍历法得到的二叉树序列。

测试说明
平台会对你编写的代码进行测试：

测试输入：
ab000
ab00c00
0

预期输出：
abba
abbacc

#include<iostream>
#include <string.h>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void DoubleTraverse(BiTree T)
{//双序遍历二叉树T的递归算法
/**************begin************/
	if(T==NULL)
		return;
	else{
		cout<<T->data;
		DoubleTraverse(T->lchild);
		cout<<T->data;
		DoubleTraverse(T->rchild);
	}

    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
    {
        if(strcmp(S,"0")==0) break;
        int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		DoubleTraverse(T);
		cout<<endl;
	}
	return 0;
}

第4关：基于二叉链表的二叉树叶子结点到根结点的路径的求解

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写算法求出每个叶子结点到根结点的路径。

编程要求
输入
多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出n行（n为叶子结点的个数），每行为一个叶子结点到根节点的路径（按照叶子结点从左到右的顺序）。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abd00e00cf00g00
0

预期输出：
dcba
ecba
fba
gia
hia
dba
eba
fca
gca

#include<iostream>
using namespace std;
char path[100];  //路径数组，存储路径上每个结点的值
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void AllPath(BiTree T,char path[],int pathlen)
{//二叉树叶子结点到根结点的路径的求解
/**************begin************/
    if(T==NULL)
    	return;
    
    path[pathlen]=T->data;
    pathlen++;
    
    if(T->lchild == NULL && T->rchild == NULL){
    	for (int i = pathlen - 1; i >= 0; i--)
            cout << path[i];
        cout << endl;
	}else{
		AllPath(T->lchild,path,pathlen);
		AllPath(T->rchild,path,pathlen);
	}
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S&&S[0]!='0')
	{
		int i=-1;
		BiTree T;
		CreateBiTree(T,S,++i);
		int pathlen=0;         //初始化路径到根结点的长度为0
        AllPath(T,path,pathlen);
	}
	return 0;
}

解释：

  1. 空树处理：
    • 如果当前节点为空（T == NULL），直接返回，表示当前路径已经到达树的末端，递归结束。
  2. 路径记录：
    • 当前节点的值（T->data）存入路径数组 path[] 的当前位置 pathlen，并将路径长度 pathlen 加 1。
    • 该 path 数组用于记录从根节点到当前节点的路径。
  3. 叶子节点处理：
    • 如果当前节点是叶子节点（T->lchild == NULL && T->rchild == NULL），则输出存储在 path[] 中的路径。
    • 从 pathlen - 1 开始反向输出路径，即从叶子节点到根节点的路径。
  4. 递归遍历：
    • 如果当前节点不是叶子节点，则递归调用 AllPath 处理当前节点的左右子树，继续构建路径。

第5关：基于二叉链表的二叉树的遍历

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法分别实现二叉树的先序、中序和后序遍历。

编程要求
输入
多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出三行，为二叉树的先序、中序和后序序列。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abd00e00cf00g00
0

预期输出：
abcdefigh
dcebfagih
decfbghia
abdecfg
dbeafcg
debfgca

#include<iostream>
#include<string.h>
using namespace std;
int flag;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void PreOrderTraverse(BiTree T)
{//二叉树的先序遍历
/**************begin************/
	if(T==NULL)
		return;
	else{
		cout<<T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);	
	}
    /**************end************/
}
void InOrderTraverse(BiTree T)
{//二叉树的中序遍历
/**************begin************/
	if(T==NULL)
		return;
	else{
		InOrderTraverse(T->lchild);
		cout<<T->data;
		InOrderTraverse(T->rchild);	
	}
    /**************end************/
}
void PostOrderTraverse(BiTree T)
{//二叉树的后序遍历
/**************begin************/
	if(T==NULL)
		return;
	else{
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
                cout<<T->data;
	}
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
	{
		if(strcmp(S,"0")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		PreOrderTraverse(T);
		cout<<endl;
  	    InOrderTraverse(T);
		cout<<endl;
		PostOrderTraverse(T);
		cout<<endl;
	}
	return 0;
}

第6关：基于二叉链表的二叉树结点个数的统计

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法对二叉树的结点（度为0、1、2）个数进行统计。

编程要求
输入
多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据输出一行，每行三个数分别为二叉树的度为0、1、2的结点个数。每两个数用空格分隔。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abd00e00cf00g00
0

预期输出：
5 0 4
4 0 3

#include<iostream>
#include<string.h>
using namespace std;
int a,b,c;//a、b、c分别表示度为0、1、2的结点个数
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
void Count(BiTree T)
{//二叉树结点个数的统计
/**************begin************/
    if(T==NULL)
		return;
	else if(T->lchild==NULL&&T->rchild==NULL){
		a++;
		return;
	}else if(T->lchild==NULL&&T->rchild!=NULL){
		b++;
		Count(T->rchild);
	}else if(T->lchild!=NULL&&T->rchild==NULL){
		b++;
		Count(T->lchild);
	}else{
		c++;
		Count(T->lchild);
		Count(T->rchild);
	}
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
	{
	    if(strcmp(S,"0")==0) break;
		a=b=c=0;
      	int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		Count(T);
		cout<<a<<" "<<b<<" "<<c<<endl;
	}
	return 0;
}

第7关：基于二叉链表的二叉树高度的计算

任务描述
设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，，编写递归算法计算二叉树的高度。

编程要求
输入
多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出
每组数据分别输出一行，为二叉树的高度。

测试说明
平台会对你编写的代码进行测试：

测试输入：
abcd00e00f00ig00h00
abd00e00cf00g00
0

预期输出：
4
3

#include<iostream>
#include <string.h>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='0')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
int Depth(BiTree T)
{//二叉树高度的计算
/**************begin************/
	
    if(T==NULL)
		return 0;
	else{
		int ldepth=Depth(T->lchild);
		int rdepth=Depth(T->rchild);
		return ldepth>rdepth?ldepth+1:rdepth+1;
	} 
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
	{
	    if(strcmp(S,"0")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		cout<<Depth(T)<<endl;
	}
	return 0;
}

第8关：二叉树的WPL计算

任务描述
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T， 采用二叉链表存储，结点结构为：left weight right，其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法。

编程要求
输入
多组数据，每组数据一行，为一个二叉树的先序序列（序列中元素为0时，表示该结点为空，每两个元素之间用空格隔开）。当输入只有一个0时，输入结束。

输出
每组数据输出一行，为该二叉树的WPL。

测试说明
平台会对你编写的代码进行测试：

测试输入：
1 1 0 0 1 0 0
1 2 1 0 0 0 0
0

预期输出：
2
2

#include<iostream>
using namespace std;
typedef struct BiTNode
{
	int weight;
	struct BiTNode *left,*right;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T)
{//先序建立二叉树
	int x;
	cin>>x;
	if(x==0) T=NULL;
	else
    {
		T=new BiTNode;
		T->weight=x;
		CreateBiTree(T->left);
		CreateBiTree(T->right);
	}
}
int WPL(BiTree &T,int d)
{//求二叉树T的带权路径长度
/**************begin************/
    if(T==NULL)
		return 0;	
    else if(T->left==NULL&&T->right==NULL){
		return d*T->weight;
	}else{
		return WPL(T->left,d+1)+WPL(T->right,d+1);
    }
   
    /**************end************/
}
int main()
{
	while(1)
    {
		BiTree T;
		CreateBiTree(T);
		if(!T) break;
		int d=0;          //调用时T指向二叉树的根结点，d为0
		cout<<WPL(T,d)<<endl;
	}
	return 0;
}

C++作业数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
Java课内-实验2:方阵可视化遍历

							
							

							
Java课内-实验1:分数类(完全弹性碰撞)

							
							

							
-1大于4？