目录
#971 统计利用先序遍历创建的二叉树的深度
题目
思路
代码
#972 统计利用先序遍历创建的二叉树的宽度
题目
思路
代码
#971 统计利用先序遍历创建的二叉树的深度
题目
题目描述
利用先序递归遍历算法创建二叉树并计算该二叉树的深度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的深度（使用二叉树的后序遍历算法）。需要注意输入数据序列中的"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。
输入
输入为先序遍历二叉树结点序列。
输出
对应的二叉树的深度。
样例输入
A## ABC#### AB##C## ABCD###E#F##G## A##B##样例输出
1 3 2 4 1
思路
树的深度，也就是树的最大层次。
统计二叉树的最大层次，也就是求出左子树的层次，右子树的层次，比较他们的大小，大的加1就是原来树的最大值了(这里加1是因为根节点没被算进），那么，如何求左右子树的最大层次呢？请在读一遍这句话。
比较大小，可以写一个max()函数。在#include <algorithm> 算法头文件中。
max(a,b);//返回a和b的最大值,注意a,b必须是同种定义类型int Height(BinaryTree* &root) {if(root==NULL) return 0;//遇到空节点,返回,不再统计else return max(Height(root->left),Height(root->right))+1;//返回左子树或者右子树的最大值+1
}代码
二叉树模板，二叉树介绍
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
// 定义二叉树
typedef struct BTNode{char data;BTNode* left;BTNode* right;
}BinaryTree;
//创建二叉树
void Create(BinaryTree* &root) {BTNode *q;q=new BTNode;cin>>q->data;if(q->data=='#') {root=q=NULL;return;}root=q;Create(root->left);Create(root->right);return;
}
//遍历深度
int Height(BinaryTree* &root) {if(root==NULL) return 0;else return max(Height(root->left),Height(root->right))+1;
}
int main() {BinaryTree* root;Create(root);cout<<Height(root);return 0;
}#972 统计利用先序遍历创建的二叉树的宽度
题目
题目描述
利用先序递归遍历算法创建二叉树并计算该二叉树的宽度。先序递归遍历建立二叉树的方法为：按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的二叉链表存储结构。约定二叉树结点数据为单个大写英文字符。当接收的数据是字符"#"时表示该结点不需要创建，否则创建该结点。最后再统计创建完成的二叉树的宽度（是指二叉树每层节点数的最大值）。需要注意输入数据序列中"#"字符和非"#"字符的序列及个数关系，这会最终决定创建的二叉树的形态。
输入
输入为接受键盘输入的由大写英文字符和"#"字符构成的一个字符串（用于创建对应的二叉树）。
输出
输出该用例对应的二叉树的宽度。
样例输入
A## ABC#### AB##C## ABCD###EF##G### A##B##样例输出
1 1 2 3 1
思路
树的宽度，也就是每层最大的节点数。
可以遍历所有节点，然后打一个数组储存该层的节点数。最后输出最大就行
int a[10005];//数组a表示储存第key层有几个节点
//key表示第几层，刚开始key为1，也就是第一层
int ans=0;//ans表示最终答案
void Wide(BinaryTree* &root,int key) {if(root==NULL) return;else {a[key]++;ans=max(ans,a[key]);//更新最大值Wide(root->left,key+1);Wide(root->right,key+1);}
}代码
二叉树模板，二叉树介绍
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
// 定义二叉树
typedef struct BTNode{char data;BTNode* left;BTNode* right;
}BinaryTree;
//创建二叉树
void BTCreate(BinaryTree* &root) {BTNode *q;q=new BTNode;cin>>q->data;root=q;if(q->data=='#') {root=q=NULL;return;}BTCreate(root->left);BTCreate(root->right);return;
}
//返回二叉树宽度
int a[10005],ans=0;
void Wide(BinaryTree* &root,int key) {if(root==NULL) return;else {a[key]++;ans=max(ans,a[key]);Wide(root->left,key+1);Wide(root->right,key+1);}}
int main() {BinaryTree* root;BTCreate(root);Wide(root,1);cout<<ans;return 0;
}