CE14.【C++ Cont】练习题组15(二叉树专题)

#include <iostream>
using namespace std;
const int N = 1000;
char _left[N], _right[N], root, node;
int n;
void preorder(char root)
{
	if (root == '*')
		return;
	cout << root;
	preorder(_left[root]);
	preorder(_right[root]);
}

int main()
{
	cin >> n;
	cin >> root; 
    cin>>_left[root] >> _right[root];//读根节点和其左右子树 
	n--;
	while (n--)
	{
		cin >> node;
        cin >> _left[node] >> _right[node];
	}
	preorder(root);
	return 0;
}

注:不建议写成cin >> root >>_left[root] >> _right[root];和cin >> node >> _left[node] >> _right[node];在Dev C++和VS上测试都有问题,分开读

提交结果

2.P4913 【深基16.例3】二叉树深度

题目

【深基16.例3】二叉树深度 - 洛谷

分析

二叉树的深度求解方法参见109.【C语言】数据结构之求二叉树的高度文章

公式:二叉树的高度 == 1 + max(左子树的高度，右子树的高度)

代码

#include <iostream>
#include <algorithm>//max函数 
using namespace std;
const int N=1e6+10;
int _left[N],_right[N],n;
int i=1;//根节点编号为1
int treeheight(int root)
{
	if (root==0)//停止递归的条件 
		return 0;
	
	//root!=0
	int _left_height=treeheight(_left[root]);//左子树高度 
	int _right_height=treeheight(_right[root]);//右子树高度 
	return max(_left_height,_right_height)+1;//返回左右子树高度较大的那个,且根节点高度为1也要加上 
}

int main()
{
	cin>>n;
    while(n--)
	{
		cin>>_left[i]>>_right[i];
		i++;
	}
	cout<<treeheight(1);
    return 0;
}

提交结果

3.★[NOIP 2001 普及组] 求先序排列

题目

[NOIP 2001 普及组] 求先序排列 - 洛谷

分析

本题和下面这些题是同类题型,且做法固定

给出一棵二叉树的先序与中序排列。求出它的后序排列(本文第4题)

注:给出一棵二叉树的先序与后序排列无法还原二叉树,必须知道中序排列!!!

统一做法

★重复此步骤:先确定根节点,再按根节点划分左右子树★

以测试用例BADC BDCA为例分析

先确定根节点:

因为中序排列为BADC,后序排列为BDCA,那么根节点一定为A(后序排列最后访问的一定是根!!),打印A

再按根节点划分左右子树:

因为中序排列按左子树->根-->右子树遍历,所以划分为B | A | DC,显然 B为左子树部分(打印B),DC为右子树部分,则后序排列为B | DC | A

处理左子树B:

先确定根节点:B,再按根节点划分左右子树:为空,不用划分

处理右子树DC:先确定根节点:由于中序排列和后序排列都是同一个顺序DC,那么C为根节点(后序排列最后访问的一定是根!!),打印C,再按根节点划分左右子树:D | C | 空,则D为C的左子树,打印D,C的右子树不存在.

则打印的前序排列为ABCD

算法

先确定根节点:利用循环来找,设在中序排列找到的下标为pos(可以调用find函数或者写循环来手动查找)

再按根节点划分左右子树:中序排列划分:[left1,pos-1],pos,[pos+1,right1],左区间长度为pos-1-left1+1==pos-left,右区间长度为right1-pos-1+1==right1-pos,则可以推出后序排列的划分[left2,left2+(pos-left1)-1],[left2+(pos-left1),right2-1],right2

再分别对左子树递归: [left1,pos-1]和[left2,left2+(pos-left1)-1],传四个参数

右子树递归:[pos+1,right1]和[left2+(pos-left1),right2-1],传四个参数

示意图

?处下标的算法:绿色部分长度相同,因此(pos-1)-(left1)==(?)-left2

注:left1,right1,left2,right2不一定就在边界处,这里仅示意

递归函数的模版

void print_preorder(int left1,int right1,int left2,int right2)
{
	//先写递归结束条件
	if (......) 
		return; 
	//再确定根节点
	cout<<......;
	int pos=......;
	
	//最后按根节点划分左右子树,对左右子树递归
	//中序排列划分:[left1,pos-1],pos,[pos+1,right1]
	//后序排列的划分:[left2,left2+(pos-left1)-1],[left2+(pos-left1),right2-1],right2
	//左子树:[left1,pos-1]和[left2,left2+(pos-left1)-1]
    //右子树:[pos+1,right1]和[left2+(pos-left1),right2-1]

	//递归处理左子树
	print_preorder(?,?,?,?);
	
	//递归处理右子树
	print_preorder(?,?,?,?);
}

代码

利用递归算法

#include <iostream>
#include <string>
using namespace std;
string inorder_str,postorder_str;

void print_preorder(int left1,int right1,int left2,int right2)
{
	//递归结束条件
	if (right1<left1||right2<left2) 
		return; 
	//先确定根节点
	cout<<postorder_str[right2];
	int pos=inorder_str.find(postorder_str[right2]);
	
	//再按根节点划分左右子树
	//中序排列划分:[left1,pos-1],pos,[pos+1,right1]成立前提:left1<=pos-1<=right1 
	//后序排列的划分:[left2,left2+(pos-left1)-1],[left2+(pos-left1),right2-1],right2成立前提:left2<=left2+(pos-left1)-1<right2-1
	
	//递归处理左子树
	print_preorder(left1,pos-1,left2,left2+(pos-left1)-1);
	
	//递归处理右子树
	print_preorder(pos+1,right1,left2+(pos-left1),right2-1);
}

int main()
{
	cin>>inorder_str>>postorder_str;
	print_preorder(0,inorder_str.size()-1,0,postorder_str.size()-1);
    return 0;
}

注意前序遍历的顺序: (打印)根-->(递归)左-->(递归)右

提交结果

4. P1827 [USACO3.4] 美国血统 American Heritage

题目

[USACO3.4] 美国血统 American Heritage - 洛谷

分析

给中序遍历和前序遍历,打印后序遍历,和第3题思路相同,不再赘述

代码

#include <iostream>
#include <string>
using namespace std;
string inorder_str,preorder_str;

void print_postorder(int left1,int right1,int left2,int right2)
{
	//结束条件
	if (left1>right1||left2>right2) 
		return;
	
	//找根,划分左右子树 
	int pos=inorder_str.find(preorder_str[left2]);
	
	//递归左子树 
	print_postorder(left1,pos-1,left2+1,right2+pos-right1);
	
	//递归右子树
	print_postorder(pos+1,right1,right2+pos-right1+1,right2);
	
	//打印根节点 
	cout<<preorder_str[left2];
}

int main()
{
	cin>>inorder_str>>preorder_str;
	print_postorder(0,inorder_str.size()-1,0,preorder_str.size()-1);
    return 0;
}

注意后序遍历的顺序:(递归)左-->(递归)右-->(打印)根