根据二叉树的扩展序列构造二叉树,并对其进行前序、中序、后序遍历

描述:

要求:

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;
}