树的应用

线性结构：一对一

树结构：一对多

一个结点可以有多个子结点，每个结点有唯一的父结点（根结点例外）。

树的定义（递归）

树是由n (n >=0)个结点组成的有限集合。

如果n = 0，称为空树； 如果n > 0，则:

有唯一的一个结点称之为根(root)的结点，它只可以有后继，但没有前驱；

除根结点以外的其它结点划分为m (m >= 0)个互不相交的有限集合T0, T1, …, Tm-1，每个集合本身又是一棵树，并且称之为根的子树(subTree)。

每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。

基本概念：

结点：

父结点、子结点、兄弟结点、祖先结点、子孙结点、叶结点。

度：

结点的度：结点的子结点个数；

树的度：树中所有结点的度的最大值。

结点层次：

约定根结点在第一层，其他结点的层数=父结点的层数 + 1。

树的高度：

树中所有结点的最大层数。

有序树和无序树：

若结点的子树有次序排列，且先后次序不能互换，这样的树称为有序树，反之为无序树。

树的类型

二叉树

·前序中序后序遍历

·堆

·哈夫曼树

二叉查找树

各种平衡树

线段树

树套树

树

树的存储

树的遍历

树的直径

树的重心

树的最近公共祖先

树形dp

树链剖分

.....

二叉树

度为2的有序树，每个结点最多有两个子结点，分别称为左孩子、右孩子结点。两棵子树分别称为左子树、右子树。

二叉树的性质：

1. 在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。

证明：

（数学归纳法）
当i=1时，2^(i-1)=1显然成立；
现在假设第i-1层时命题成立，即第i-1层上最多有2^(i–2) 个结点。
由于二叉树的每个结点的度最多为2，故在第i层上的最大结点数为第i-1层的2倍，即：2*2^(i-2)=2^(i–1)。

2.深度为k的二叉树至多有2^k–1个结点（k>=1）。

证明：

每层的结点个数都取最大值时，二叉树中的结点个数最多。
由性质1，深度为k的二叉树的结点数至多为：
2^0+2^1+…+2^(k-1)
=2^k-1

两种特殊的二叉树：

一棵深度为k且有2^k–1个结点的二叉树称为满二叉树。

对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义，深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

3.对任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。

证明：

利用两种方式表示结点总数n。

(1)度为0的结点数n0、度为1的结点n1、度为2的结点数n2之和：

n=n0+n1+n2 ……(式子1)

(2)每个度为1的结点有1个子结点，每个度为2 的结点有两个子结点，故二叉树中孩子结点总数是：n1+2*n2。

再加上根结点就是结点总数：

n=n1+2*n2+1 ……(式子2)

由式子1和式子2得到：n0=n2+1

树的存储(二叉树):

因为每个结点最多有两个子结点，可以采用如下的方式存储：

struct btree{
    elemtype data;      //结点基本信息
    int fa;         //父结点
    int lc, rc;     //左右孩子结点
}bt[maxn];

树的存储(普通树):

结点的子结点个数不确定，如果以数组的方式记录每个结点的子结点，需要按照最大结点个数开数组，会造成空间的浪费。

struct tree{
    elemtype data;      //结点基本信息
    int fa;         //父结点
    int child[maxc];//vector<int>child; //子结点
}t[maxn];

vetctor child[maxn];//srting data[maxn]
 for(int j=0;j<child[i].size();j++)cout<<child[i][j]<<“ ”;
for(int i=0;i<t[i].child.size();i++)cout<<t[i].child[i]<<“ ”;
vector<int>a;
vector<int>tree[N];//二维数组  n  n-1 
//queue,stack string 
int main(){
    a.push_back(1);
    a.push_back(2); 
    a.push_back(10);
    a.push_back(13);
    a.push_back(20);
    cout<<a.size()<<endl;
    cout<<a[0]<<" "<<a[4]<<endl;
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<",";
    cout<<endl;
    for(auto x:a)cout<<x<<"  ";

    //u v
    tree[u].push_back(v1);
    tree[u].push_back(v2);
    //方法1： 
    for(int i=0;i<tree[u].size();i++)
        cout<<tree[u][i]<<",";
    //方法2：
    for(auto v:tree[u])
        cout<<"*";

树的存储(普通树):

以链表的方式记录子结点信息

struct tree{
    elemtype data;      //结点基本信息
    int fa;         //父结点
    int first, next;    //链表
}t[maxn];

多叉树转二叉树

用二叉树表示一棵树要比多叉树简单些，而且多叉树都可以转换成唯一的二叉树。

对于多叉树中的每个结点，可以用两个指针分别指向它的第一个子结点和下一个相邻结点。

1.在树中各兄弟（堂兄弟除外）之间加一根连线。

2.对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。

树的遍历（二叉树）：

在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。

所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。

先（根）序遍历、中（根）序遍历、后（根）序遍历；

按层次遍历。

先序遍历

若二叉树为空，结束，否则：

1.访问根结点

2.先序遍历左子树

3.先序遍历右子树

void pre(int k){
    if(k != -1){
        visit(k);   //访问子树根结点
        pre(bt[k].lc);
        pre(bt[k].rc);
    }
}

中序遍历

若二叉树为空，结束，否则：

1.中序遍历左子树

2.访问根结点

3.中序遍历右子树

void mid(int k){
    if(k != -1){
        mid(bt[k].lc);
        visit(k);   //访问子树根结点       mid(bt[k].rc);
    }
}

后序遍历

若二叉树为空，结束，否则：

1.后序遍历左子树

2.后序遍历右子树

3.访问根结点

void suc(int k){
    if(k != -1){
        suc(bt[k].lc);                  suc(bt[k].rc);
        visit(k);   //访问子树根结点
    }
}

P1305 新二叉树

题目描述

输入一串完全二叉树，用遍历前序打出。

输入格式：

第一行为二叉树的节点数n(n<=26)。

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用*表示

输出格式：

前序排列的完全二叉树

输入样例：

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

输出样例：

abdicj

怎么存储？

怎么建树？

谁是根节点？怎么找？

#include <cstdio>
const int maxl=60;
struct node{int ll,rr;}a[maxl];
int n;int root;
char ss[5];
int  v[maxl];
void dfs(int k){
    printf("%c",k+'a'-1);
    if(a[k].ll) dfs(a[k].ll);
    if(a[k].rr) dfs(a[k].rr);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){  
        scanf("%s",ss);//cin>>ss;
        v[ss[0]-'a'+1]++;v[ss[1]-'a'+1]++;v[ss[2]-'a'+1]++;
        if(ss[1]!='*'){a[ss[0]-'a'+1].ll=ss[1]-'a'+1;v[ss[1]-'a'+1]++;}
        if(ss[2]!='*'){a[ss[0]-'a'+1].rr=ss[2]-'a'+1;v[ss[1]-'a'+1]++;}
    }
    for(root=1;;root++)
        if(v[root]==1)break;        
    dfs(root); printf("\n");
    }

按层次遍历 ：

先访问根结点，

再依次访问根结点的所有子结点，

然后依次访问根结点的子结点的子结点。

广度优先搜索（基于队列的应用）

树的遍历（普通树）：

先（根）序遍历、后（根）序遍历；

按层次遍历。

P1030 求先序排列

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入格式：

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

输出格式：

1行，表示一棵二叉树的先序。

输入样例：

BADC

BDCA

输出样例：

ABCD

算法分析：

中序：BADC

后序：BDCA

A为根结点，B、DC分别为左右子树的中序序列；

B、DC分别为左右子树的后序序列。

递归处理：中序为B，后序为B的子树；

递归处理：中序为DC，后序为DC的子树；

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int maxl=10;
string mid,post;
void solve(int lmid,int rmid,int lpost,int rpost){  //[left,right)
    printf("%c",post[rpost-1]);
    int p=mid.find(post[rpost-1]);
    if(p>lmid) solve(lmid,p,lpost,lpost+p-lmid);
    if(p+1<rmid) solve(p+1,rmid,lpost+p-lmid,rpost-1);
}
int main(){
    cin>>mid>>post;
    solve(0,mid.size(),0,post.size()); printf("\n");
    return 0;
}

P1087 [NOIP2004 普及组] FBI 树

我们可以把由 0 和 1 组成的字符串分为三类：全 0 串称为 B 串，全 1 串称为 I 串，既含 0 又含 1 的串则称为 F 串。

FBI 树是一种二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。

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

样例输入：

3
10001011

样例输出

IBFBBBFIBFIIIFF

方法一：从上到下建树

方法二：这是一颗满二叉树，从非叶子结点逆序找到根节点。

P1229 遍历问题

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

给出前序和后序，求中序的方案数。

算法分析：

既有左子树，又有右子树，前序+后续是否可以固定左右子树？

木有啦，被翻了！