网页制作要学什么课程_建筑工程网络计划技术_子域名网址查询_优化大师tv版

目录

1.P1305 新二叉树

题目

分析

代码

提交结果

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

题目

分析

代码

提交结果

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

题目

分析

统一做法

算法

示意图

递归函数的模版

代码

提交结果

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

题目

分析

代码

提交结果

---

1.P1305 新二叉树

题目

新二叉树 - 洛谷

分析

把字母当成对应的ASCII码编号的节点处理,例如a节点,'a'的ASCII码为97,其编号为97号,向往常一样使用前序遍历

代码

#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!=0int _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;
}

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

提交结果