树形数据结构总结

2021-01-12

前序,中序,后序知二推一

求先序序列

题目描述
给出一棵二叉树的中序与后序排列,求出它的先序排列，(约定树结点用不同的大写字母表示,长度≤8)。

输入格式
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式
1行，表示一棵二叉树的先序。

输入

BADC
BDCA

输出

ABCD

#include<iostream>
#include<string>
using namespace std;

string in;
string post;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* Tree[10000];

TreeNode* CreatTree(int s1,int t1,int s2,int t2){
    char c=post[t1];//后序的最后一个
    if(s1==t1){//叶子结点
        Tree[c-'A']=new TreeNode(c);
        return Tree[c-'A'];
    }
    Tree[c-'A']=new TreeNode(c);
    int pos=in.find(c);//在中序中找到对应的顶点以及左右长度
    int llen=pos-s2;
    int rlen=t2-pos;
    //别忘了判左右长度
    if(llen) Tree[c-'A']->left=CreatTree(s1,s1+llen-1,s2,s2+llen-1);
    if(rlen) Tree[c-'A']->right=CreatTree(s1+llen,t1-1,s2+llen+1,t2);
    return Tree[c-'A'];
}

void PreOrder(TreeNode* root){
    if(root==NULL) return ;
    cout<<root->data;
    PreOrder(root->left);
    PreOrder(root->right);
}

int main(){
    cin>>in>>post;
    TreeNode* root=CreatTree(0,post.size()-1,0,in.size()-1);
    PreOrder(root);
}

求可能中序序列

题目描述
已知前序和后序遍历的结果求出一种可能得中序遍历的结果,二叉树的结点名以大写字母(A,B,C…)表示，最多26个结点
输入格式
第一行为前序遍历结果
第二行为后序遍历结果
输出格式
一个字符串，表示一个可能的中序遍历
输入

ABDCE
DBECA

输出

DBAEC

#include<iostream>
#include<string>

using namespace std;

string pre,post;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* PrePostCreat(string pre,string post){
    TreeNode* root=new TreeNode(pre[0]);
    if(pre.size()==0) return NULL;//返回
    int pos=post.find(pre[1]);//先序顶点在后序的位置
//    cout<<pre.substr(1,pos+1)<<"   "<<post.substr(0,pos+1)<<endl;
//    cout<<pre.substr(pos+2)<<"   "<<post.substr(pos+1,post.size()-pos-2)<<endl;
    root->left=PrePostCreat(pre.substr(1,pos+1),post.substr(0,pos+1));
    root->right=PrePostCreat(pre.substr(pos+2),post.substr(pos+1,post.size()-pos-2));
    return root;
}

void InOrder(TreeNode* T){
    if(T==NULL) return ;
    InOrder(T->left);
    cout<<T->data;
    InOrder(T->right);
}

int main(){
    cin>>pre>>post;
    TreeNode* root=PrePostCreat(pre,post);
    InOrder(root);
}

二叉排序树

构造二叉排序树

题目描述
已知二叉排序树用二叉链表存储，结点的关键字为 1正整数。从键盘输入结点的关键字（以 0表示结束）建立一棵二叉排序树，并输出其后序遍历序列

#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data):data(data),left(NULL),right(NULL){}
};
//x插入到以root为根结点的排序树中，从根结点不断的向下比
TreeNode* Insert(TreeNode* root,int n){
    if(root==NULL) root=new TreeNode(n);
    else if(n<root->data) root->left=Insert(root->left,n);
    else if(n>root->data) root->right=Insert(root->right,n);
    return root;
}
void PostOrder(TreeNode* root){
    if(root==NULL) return  ;
    PostOrder(root->left);
    PostOrder(root->right);
    cout<<root->data<<" ";
}
int main(){
    int n;
    TreeNode* root=NULL;
    while(cin>>n){
        if(n==0) break;
        else root=Insert(root,n);
    }
    PostOrder(root);
}

二叉搜索树

题目描述
判断两序列是否为同一二叉搜索树序列

输入描述:
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出描述:
如果序列相同则输出YES，否则输出NO

输入

2
567432
543267
576342`
0

输出

YES
NO

#include<iostream>
#include<cstdio>
#include<string>
//前序遍历和中序遍历可以唯一确定一棵二叉树，
//而对二叉排序树而言，相同元素的二叉排序树中
//序遍历一定相同，而不同元素二叉排序树使用前
//序遍历就可以发现不相同，所以只需要前序遍历
//两个二叉树，比较一下就可以判断
using namespace std;
string pre,in;
struct TreeNode{
    char data;
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode(char c):data(c),leftchild(NULL),rightchild(NULL){}
};
TreeNode* Insert(TreeNode* root,char x){
    if(root==NULL){
        root=new TreeNode(x);
    }
    else if(x<root->data){
        root->leftchild=Insert(root->leftchild,x);
    }
    else if(x>root->data){
        root->rightchild=Insert(root->rightchild,x);
    }
    return root;
}
string preorder(TreeNode* root){
    if(root==NULL) return "#";
    return root->data+preorder(root->leftchild)+preorder(root->rightchild);
}
int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        string s; TreeNode* root=NULL;
        cin>>s;
        //构建初始的排序树
        for(int i=0;i<s.size();i++){
            root=Insert(root,s[i]);
        }
        string pre=preorder(root);
        //构建用来比较的排序树
        for(int i=0;i<n;i++){
            string str; TreeNode* T=NULL;
            cin>>str;
            for(int j=0;j<str.size();j++){
                T=Insert(T,str[j]);
            }
            string pre1=preorder(T);
        //进行比较
            if(pre1==pre) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

二叉排序树最大路径

题目描述
求二叉排序树中的最大路径

输入

16
30 45 2 69 36 14 52 23 31 90 57 32 33 34 91 92

输出

11

#include<bits/stdc++.h>

using namespace std;

struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data):data(data),left(NULL),right(NULL){}
};
int Max=0;
int a[100];
//测试数据
//30 45 2 69 36 14 52 23 31 90 57 32 33 34 91 92
TreeNode* CreatTree(TreeNode* root,int data){
    if(root==NULL){
        TreeNode* T=new TreeNode(data);
        return T;
    }
    if(data<root->data) root->left=CreatTree(root->left,data);
    else if(data>root->data) root->right=CreatTree(root->right,data);
    return root;
}

int MaxPath(TreeNode* root){
    if(root==NULL) return 0;
    int lh,rh,sum;
    //包括自己在内的长度
    lh=MaxPath(root->left)+1;
    rh=MaxPath(root->right)+1;
    //cout<<root->data<<" "<<lh<<" "<<rh<<endl;
    sum=lh+rh-1;
    Max=max(Max,sum);
    return lh>rh?lh:rh;
}

void PreOrder(TreeNode* T){
    if(T==NULL) return ;
    cout<<T->data;
    PreOrder(T->left);
    PreOrder(T->right);
}

int main(){
    int n;
    cin>>n;
    TreeNode* root=NULL;
    for(int i=0;i<n;i++){
        cin>>a[i];
        root=CreatTree(root,a[i]);
    }
    MaxPath(root);
    cout<<endl;
    cout<<Max;
}

huffman树

huffman编码

题目描述
哈弗曼树问题：在”7.in”中
有几个数，和为1，进行哈弗曼编码，并把编码结果输出到”7.out”中。

输入

0.1 0.15 0.2 0.25 0.3

输出

000
001
01
10
11

PS:这道题我写了特别久，主要是优先队列存指针的问题，西八，太难了。

#include<bits/stdc++.h>
using namespace std;

const int eps=1e-6;

struct HfNode{
    double weight;
    HfNode* left;
    HfNode* right;
    string code;
    HfNode(double weight):weight(weight),left(NULL),right(NULL),code(""){}
    bool operator >(const HfNode& e)const{
        return weight>e.weight;
    }
};

HfNode* Tree[10000];

void Huffman(HfNode* T){//遍历huffman树设编码
    //cout<<T.code<<endl;
    if(T->left!=NULL) {T->left->code=T->code+"1";  Huffman(T->left);}
    if(T->right!=NULL) {T->right->code=T->code+"0";  Huffman(T->right);}
    if(T->left==NULL&&T->right==NULL) cout<<T->weight<<" "<<T->code<<endl;//叶子结点
    return ;
}

//重要：std::priority_queue 存放的是自定义类型的指针时,解决方法是使用Compare
//类似于sort中定义的cmp
class Compare{
public:
    bool operator () (HfNode* &a,HfNode* &b) const{
        return a->weight>b->weight;
    }
};

int main(){
    priority_queue <HfNode*,vector<HfNode*>,Compare > q;
    ifstream infile("in.txt");
    double n; string s;
    getline(infile,s);
    stringstream in(s);//这个在double会出现问题

    while(in>>n){
        HfNode* node=new HfNode(n);//在前面加new返回指针，不加new就是node的类型
        q.push(node);
    }

    int point;
    while(q.size()>1){//建huffman树
        //分配空间
        HfNode* a=(HfNode*)malloc(sizeof(HfNode));
        HfNode* b=(HfNode*)malloc(sizeof(HfNode));
        HfNode* c=(HfNode*)malloc(sizeof(HfNode));
        a=q.top(); q.pop();
        b=q.top(); q.pop();
        double x=a->weight+b->weight;
        c=new HfNode(x);
        c->left=a; c->right=b;
        //cout<<c->left->weight<<" "<<c->right->weight<<endl;
        q.push(c);
    }
    Huffman(q.top());
}

其余题型

层次遍历

题目描述
输出树的层次遍历的奇数层的所有结点。
输入

A B C
B E
C F G

输出

第 1 层结点：A
第 3 层结点：E,F,G

#include<iostream>
#include<fstream>
#include<vector>
#include<sstream>
#include<queue>
using namespace std;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    int deep;
    TreeNode(char data,int deep):data(data),deep(deep),left(NULL),right(NULL){}
};
const int MAXN=100;
TreeNode* Tree[MAXN];//建树时一定要用这个，方便用内容去找到结点;

vector<char> v;

void Level_Order(TreeNode* T){
    queue<TreeNode*> q;
    q.push(T);
    while(!q.empty()){
        TreeNode* p=q.front();
        q.pop();
        if(p->deep%2==1) cout<<"第"<<p->deep<<"层:"<<p->data<<" "<<endl;
        if(p->left){
            q.push(p->left);
        }
        if(p->right){
            q.push(p->right);
        }

    }
}

int main(){
    ifstream infile("in.txt");
    string s;
    int i=1;
    while(getline(infile,s)){
        v.clear();
        char c;
        stringstream in(s);
        while(in>>c){
            v.push_back(c);
        }
        if(!Tree[v[0]-'A']) Tree[v[0]-'A']=new TreeNode(v[0],1);
        int deep=Tree[v[0]-'A']->deep;
        for(int i=0;i<v.size();i++) cout<<v[i]-'A'<<" "<<endl;
        if(v.size()==3){//参照这样的方法建树
            if(!Tree[v[1]-'A']){//可以这样判断数组该处有没有值
                Tree[v[1]-'A']=new TreeNode(v[1],deep+1);
            }
            if(!Tree[v[2]-'A']){
                Tree[v[2]-'A']=new TreeNode(v[2],deep+1);
            }
            Tree[v[0]-'A']->left=Tree[v[1]-'A'];
            Tree[v[0]-'A']->right=Tree[v[2]-'A'];
        }
        else if(v.size()==2){
            if(!Tree[v[1]-'A']){
                Tree[v[1]-'A']=new TreeNode(v[1],deep+1);
            }
            Tree[v[0]-'A']->left=Tree[v[1]-'A'];
        }
        i++;
    }
    Level_Order(Tree[0]);
    //cout<<Tree[0]->left->left->data<<endl;//用这种方法来测试树是否建立成功


}

FBI树

题目描述
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括FF结点，BB结点和I结点三种。由一个长度为 2 ^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

T的根结点为R，其类型与串S的类型相同；
若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2^N 的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。

输入格式
第一行是一个整数N(0≤N≤10)，

第二行是一个长度为2^N的“01”串。

输出格式
一个字符串，即FBI树的后序遍历序列。

输入

3
10001011

输出

IBFBBBFIBFIIIFF

#include<iostream>
#include<math.h>
#include<cstdio>
#include<cstdlib>
using namespace std;

int n;
string str;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* Tree[100000];
int p=0;
TreeNode* CreatTree(int Start,int End){
    string s=str.substr(Start,End-Start+1);
    //cout<<s<<endl;
    TreeNode* T=(TreeNode*)malloc(sizeof(TreeNode*));//为了防止指针被覆盖
    if(s.find("0")!=string::npos&&s.find("1")!=string::npos){
        //cout<<"P:"<<p<<" "<<"F"<<endl;
        Tree[p]=new TreeNode('F');
        T=Tree[p];
    }
    else if(s.find("0")!=string::npos&&s.find("1")==string::npos){
        //cout<<"P:"<<p<<"B"<<endl;
        Tree[p]=new TreeNode('B');
        T=Tree[p];
    }
    else if(s.find("0")==string::npos&&s.find("1")!=string::npos){
        //cout<<"P:"<<p<<"I"<<endl;
        Tree[p]=new TreeNode('I');
        T=Tree[p];
    }
    p++;
    if(s.size()==1){
        return T;
    }
    else{
        T->left=CreatTree(Start,Start+(End-Start)/2);
        T->right=CreatTree(End-(End-Start)/2,End);
    }
    return T;
}

void PostOrder(TreeNode* root){
    if(root==NULL) return ;
    PostOrder(root->left);
    PostOrder(root->right);
    cout<<root->data;
}

int main(){
    cin>>n;
    for(int i=1;i<=pow(2,n);i++){
        char c;
        cin>>c;
        str=str+c;
    }
    //cout<<str<<endl;
    TreeNode* root=CreatTree(0,str.size()-1);
    PostOrder(Tree[0]);
}

新二叉树

题目描述
输入一串二叉树，输出其前序遍历。

输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。空节点用 * 表示

输出格式
二叉树的前序遍历。

输入

6
abc
bdi
cj*
d**
i**
j**

输出

abdicj

#include<iostream>

using namespace std;
int n;
struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){};
};

TreeNode* Tree[10000];

void PreOrder(TreeNode* root){
    if(root==NULL) return ;
    cout<<root->data;
    PreOrder(root->left);
    PreOrder(root->right);
}

int main(){
    cin>>n;
    string s;
    char T=0; int i=n;//因为Tree[0]不一定是根结点!!!!
    while(n--){
        cin>>s;
        if(i==n+1) T=s[0];//记录根结点
        //别忘了每一个结点都要判断是否已经存在
        if(!Tree[s[0]-'a']) Tree[s[0]-'a']=new TreeNode(s[0]);
        if(s[1]!='*'){
            if(!Tree[s[1]-'a']) Tree[s[1]-'a']=new TreeNode(s[1]);
            Tree[s[0]-'a']->left=Tree[s[1]-'a'];
        }
        if(s[2]!='*'){
            if(!Tree[s[2]-'a']) Tree[s[2]-'a']=new TreeNode(s[2]);
            Tree[s[0]-'a']->right=Tree[s[2]-'a'];
        }
    }
    PreOrder(Tree[T-'a']);
}