二叉树
二叉树采用二叉链表存储，要求根据给定的先序遍历序列和中序遍历序列建立二叉树，并输出后序遍历序列、结点总数、叶子数、度为1的结点数、度为2的结点数。
输入格式:
测试数据有多组，处理到文件尾。每组测试数据的第一行输入结点数n（1≤n≤10），第二、三行各输入n个整数，分别表示二叉树的先序遍历序列和中序遍历序列。
输出格式:
对于每组测试，在一行上分别输出该二叉树的后序遍历序列，结点总数，叶子数，度为1的结点数，度为2的结点数。每两个数据之间留一个空格。
输入样例:
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
10
1 2 4 7 8 9 3 5 6 10
7 4 9 8 2 1 5 6 10 3
输出样例:
7 4 2 8 9 5 6 3 1 9 4 2 3
7 9 8 4 2 10 6 5 3 1 10 3 5 2
代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB
解题代码
#include<bits/stdc++.h>
using namespace std;
struct treeNode{
int data;
treeNode *L_child,*R_child;
};
int n;
class Tree
{
public:
treeNode *root;
treeNode * createTree(int pre[],int mid[],int pre_j,int mid_be,int mid_en);
void LRN(treeNode *root);
int nodeCount(treeNode *root);
int leafCount(treeNode *root);
int nodeCount1(treeNode *root);
int nodeCount2(treeNode *root);
private:
};
//pre先序遍历顺序序列，mid中序遍历序列 pre_j当前在先序序列的位置，mid_be-mid_en,当前pre_j节点下，左右孩子及本身在中序遍历序列中所在的区间
treeNode * Tree::createTree(int pre[],int mid[],int pre_j,int mid_be,int mid_en)
{
if(pre_j>=n||pre_j<0) return NULL;
int root = pre[pre_j];
int i;
if(mid_be>mid_en) return NULL; //当这个序列起始位置大于结束位置，也就是遍历没了，代表没有孩子，结束。
for(i=mid_be;i<=mid_en;i++){
if(mid[i]==root) break; //找到当前的根节点位置
}
treeNode *node = new treeNode();
node->data=root;
node->L_child=createTree(pre,mid,pre_j+1,mid_be,i-1); //在中序遍历序列根节点的左边都是左孩子
node->R_child=createTree(pre,mid,pre_j+i-mid_be+1,i+1,mid_en);//在中序遍历序列根节点的右边都是右孩子
return node;
}
//后续遍历并输出
void Tree::LRN(treeNode *root)
{
if(root==NULL) return;
LRN(root->L_child);
LRN(root->R_child);
cout<<root->data<<" ";
}
//获取节点个数
int Tree::nodeCount(treeNode *root)
{
int sum=0;
if(root ==NULL) return sum;
sum=1;
sum+=nodeCount(root->L_child);
sum+=nodeCount(root->R_child);
return sum;
}
//统计叶子数
int Tree::leafCount(treeNode *root)
{
int sum=0;
if(root==NULL) return 0;
if(root->L_child==NULL&&root->R_child==NULL){
return 1;
}
return sum+leafCount(root->L_child)+leafCount(root->R_child);
}
//统计度为1节点的数
int Tree::nodeCount1(treeNode *root)
{
int sum=0;
if(root==NULL) return 0;
if((root->L_child==NULL&&root->R_child!=NULL)||(root->L_child!=NULL&&root->R_child==NULL)){
sum=1;
}
return sum+nodeCount1(root->L_child)+nodeCount1(root->R_child);
}
//统计度为2节点数量 节点的数
int Tree::nodeCount2(treeNode *root)
{
int sum=0;
if(root==NULL) return 0;
if(root->L_child!=NULL&&root->R_child!=NULL){
sum=1;
}
return sum+nodeCount2(root->L_child)+nodeCount2(root->R_child);
}
int main()
{
while(cin>>n)
{
int pre[n];
int mid[n];
for(int i=0;i<n;i++){
cin>>pre[i];
}
for(int i=0;i<n;i++){
cin>>mid[i];
}
Tree *tree = new Tree();
tree->root=tree->createTree(pre,mid,0,0,n-1);
tree->LRN(tree->root);
cout<<tree->nodeCount(tree->root)<<" ";
cout<<tree->leafCount(tree->root)<<" ";
cout<<tree->nodeCount1(tree->root)<<" ";
cout<<tree->nodeCount2(tree->root)<<endl;
}
}
解题思路
解题思路，就是通过先序遍历和中序遍历序列来确定二叉树，然后输出二叉树的后续遍历结果，我们要知道，先序遍历是先遍历根节点再遍历左子树最后遍历右子树，中序遍历是先遍历左子树再遍历根节点最后遍历右子树，知道这个规律，我们再已知先序遍历和中序遍历的情况下，得到整个二叉树
举例
先序 1 2 4 7 3 5 8 9 6
中序 4 7 2 1 8 5 9 3 6
那我们肯定知道，先序先遍历根节点，那么1肯定是根节点，我们在中序遍历序列中找到1的位置，因为中序遍历是先遍历左子树的，也就是说，中序遍历序列中1的左边4 7 2 这三个数一定在1的左边，1右边的序列在右边，那么继续递归遍历，我们就能得到最终的数，具体看代码吧，可以百度一下。
其他的没什么好讲的，就这样
