根据二叉树的扩展序列构造二叉树，并对其进行前序、中序、后序遍历
描述：
要求：
1.采用二叉链表的方式进行存储
2.构造一个二叉树类
实现以下算法：
1.创建二叉树
2.对二叉树进行前序、中序、后序遍历
输入
扩展的前序序列.在一棵树处理结束后，根据响应判断是否处理下一棵树
输出
前序、中序、后序
样例输入
ab##c##
Y
abc####
N
样例输出
abc
bac
bca
abc
cba
cba
代码实现：
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef struct Node{
char data;
struct Node* leftchild;
struct Node* rightchild;
}Node,*BiTree;
void CreateBiTree(BiTree *T){
//遍历方式可以分为前中后序，我们在建立一棵二叉树时可以分别根据遍历方式的不同进行创建
//以前序遍历为例
char ch;
cin>>ch;
if(ch=='#'){
*T=NULL;
}
else{
//cout<<"!"<<endl;
*T = (BiTree)malloc(sizeof(Node)); //不知道为什么加上该行就对反之则错
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data=ch;
CreateBiTree(&((*T)->leftchild)); //CreateBiTree(T->leftchild);
CreateBiTree(&((*T)->rightchild)); //CreateBiTree(T->rightchild);
}
}
void PreOrderTraverse(BiTree T,int level){
//cout<<"第"<<level<<"层"<<endl; //空的时候不输出，但可以检验树的遍历过程
if(T==NULL){
return;
}
else{
//cout<<"第"<<level<<"层"<<endl;
//cout<<(T->data)<<endl;
cout<<(T->data);
PreOrderTraverse(T->leftchild,level+1);
PreOrderTraverse(T->rightchild,level+1);
}
}
void Zhongxu(BiTree T,int level){
//中序遍历
if(T==NULL){
return;
}
else{
Zhongxu(T->leftchild,level+1);
//cout<<"第"<<level<<"层"<<endl;
//cout<<(T->data)<<endl;
cout<<(T->data);
Zhongxu(T->rightchild,level+1);
}
}
void Houxu(BiTree T,int level){
//后序遍历
if(T==NULL){
return;
}
else{
Houxu(T->leftchild,level+1);
Houxu(T->rightchild,level+1);
//cout<<"第"<<level<<"层"<<endl;
//cout<<(T->data)<<endl;
cout<<(T->data);
}
}
void testshu(){
int level = 1; //表示层数
BiTree T = NULL;
//cout << "请以前序遍历的方式输入扩展二叉树："; //类似输入AB#D##C##
CreateBiTree(&T);// 建立二叉树，没有树，怎么遍历
//cout << "递归前序遍历输出为：" << endl;
PreOrderTraverse(T, level);//进行前序遍历，其中operation1()和operation2()函数表示对遍历的结点数据进行的处理操作
cout << endl;
//cout << "递归中序遍历输出为：" << endl;
Zhongxu(T,level);
cout << endl;
//cout << "递归后序遍历输出为：" << endl;
Houxu(T,level);
cout << endl;
}
int main(){
testshu();
string s;
while(cin>>s){
if(s=="Y")
testshu();
else if(s=="N")
break;
}
}
二叉树的其他算法（统计结点个数、叶子结点个数、树的高度、左右子树的交换等）
描述：
要求：
1.采用二叉链表的方式进行存储
2.构造一个二叉树类
实现以下算法：
1.统计树中节点个数
2.统计树中叶子节点个数
3.统计树的高度
4.二叉树左右子树的交换
输入
扩展的前序序列.在一棵树处理结束后，根据响应判断是否处理下一棵树
输出
按要求输出信息（节点个数，叶子节点个数，二叉树的高度，交换之后的前序遍历）
样例输入
abc####
Y
ab##c##
N
样例输出
3
1
3
abc
3
2
2
acb
代码实现：
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int countdeep=0; //设树深为0,在遍历过程中计数
int jiedian=0;
int yejiedian=0;
typedef struct Node{
char data;
struct Node* leftchild;
struct Node* rightchild;
}Node,*BiTree;
void CreateBiTree(BiTree *T){
//遍历方式可以分为前中后序，我们在建立一棵二叉树时可以分别根据遍历方式的不同进行创建
//以前序遍历为例
char ch;
cin>>ch;
if(ch=='#'){
*T=NULL;
}
else{
//cout<<"!"<<endl;
*T = (BiTree)malloc(sizeof(Node)); //不知道为什么加上该行就对反之则错
//if (!*T)
//exit(OVERFLOW); //内存分配失败则退出。
(*T)->data=ch;
CreateBiTree(&((*T)->leftchild)); //CreateBiTree(T->leftchild);
CreateBiTree(&((*T)->rightchild)); //CreateBiTree(T->rightchild);
}
}
void PreOrderTraverse(BiTree T,int level){
//cout<<"第"<<level<<"层"<<endl; //空的时候不输出，但可以检验树的遍历过程
if(T==NULL){
return;
}
else{
jiedian++;
if(T->leftchild==NULL&&T->rightchild==NULL){
//不用放在递归调用下面,因为递归到其子节点为空时早已经返回了
yejiedian++;
}
//cout<<"第"<<level<<"层"<<endl;
//cout<<(T->data)<<endl;
//cout<<(T->data);
//PreOrderTraverse(T->leftchild,level+1);
PreOrderTraverse(T->rightchild,level+1);
PreOrderTraverse(T->leftchild,level+1); //树枝交换
}
if(level>countdeep){
countdeep=level; //层数最大值赋给countdeep,countdeep得到树的深度
}
}
void PreOrderTraverseprint(BiTree T,int level){
//cout<<"第"<<level<<"层"<<endl; //空的时候不输出，但可以检验树的遍历过程
if(T==NULL){
return;
}
else{
jiedian++;
if(T->leftchild==NULL&&T->rightchild==NULL){
//不用放在递归调用下面,因为递归到其子节点为空时早已经返回了
yejiedian++;
}
//cout<<"第"<<level<<"层"<<endl;
//cout<<(T->data)<<endl;
cout<<(T->data);
//PreOrderTraverse(T->leftchild,level+1);
PreOrderTraverseprint(T->rightchild,level+1);
PreOrderTraverseprint(T->leftchild,level+1); //树枝交换
}
if(level>countdeep){
countdeep=level; //层数最大值赋给countdeep,countdeep得到树的深度
}
}
void jiaohuanshu(){
int level = 1; //表示层数
BiTree T = NULL;
CreateBiTree(&T);
PreOrderTraverse(T, level);
cout<<jiedian<<endl;
cout<<yejiedian<<endl;
cout<<countdeep<<endl;
PreOrderTraverseprint(T, level);
cout<<endl;
jiedian=0;
yejiedian=0;
countdeep=0;
}
int main(){
//testshu();
jiaohuanshu();
string s;
while(cin>>s){
if(s=="Y")
jiaohuanshu();
//testshu();
else if(s=="N")
break;
}
}
利用二叉树的性质解决问题：
一、
描述：
如上图所示，由正整数1，2，3……组成了一颗二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。
比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树***有4个结点。
输入
输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。
输出
对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
样例输入
3 12
0 0
样例输出
4
根据题目给出的数据量我们可以得知建树遍历的方法是行不通的（很明显会超时），只能根据二叉树的一些特殊性质去解决。
代码实现：
#include <iostream>
#include <cmath>
using namespace std;
int getRlt(int n, int m)
{
int rlt;
int k = int(log(n*1.0/m)/log(2.0)) + 1;
int temp = n - m*pow(2, k-1) + 1;
if(temp > pow(2, k-1)) {
rlt = pow(2, k) - 1;
} else {
rlt = pow(2, k-1) -1 + temp;
}
return rlt;
}
int main()
{
int m, n;
while(cin >> m >> n) {
if(m==0 && n==0) break;
cout << getRlt(n, m) << endl;
}
return 0;
}
二、
描述：
如上图所示，由正整数1, 2, 3, …组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是(10, 5, 2, 1)，从4到根结点的路径是(4, 2, 1)，从根结点1到根结点的路径上只包含一个结点1，因此路径就是(1)。对于两个结点x和y，假设他们到根结点的路径分别是(x1, x2, … ,1)和(y1, y2, … ,1)（这里显然有x = x1，y = y1），那么必然存在两个正整数i和j，使得从xi 和 yj开始，有xi = yj , xi + 1 = yj + 1, xi + 2 = yj + 2,… 现在的问题就是，给定x和y，要求xi（也就是yj）。
输入
输入只有一行，包括两个正整数x和y，这两个正整数都不大于1000。
输出
输出只有一个正整数xi。
样例输入
10 4
样例输出
2
代码实现：
#include<stdio.h>
#include<stdlib.h>
int com(int x,int y){
if(x==y)return x;
else if(x>y)return com(x/2,y);
else return com(x,y/2);}
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",com(a,b));
return 0;
}
京公网安备 11010502036488号