无根树的转化及表达式树

树的一些应用

Posted by isheng on July 24, 2016

树是一种重要的数据结构

无根树的转化

一直没找到无根树与有根树的定义,知道的朋友可以在下面评论告诉我,谢谢

说明

将指定的树转化为指定根节点树,算法复杂度为

例子代码

#include <iostream>  
#include <vector>  
#include <algorithm>  
using namespace std;  

/*********************************/  
//* 可以动态变化的邻接矩阵  
//* G[i]表示顶点i的邻接点  
/*********************************/  

const int MAXN=100;  
vector<int> G[MAXN]; //无根树  
int l[MAXN]; //结点层次  
int p[MAXN]; //根树  
int dp[MAXN]; //dp数组  
int sumC[MAXN]; //孩子DP和  
int sumS[MAXN]; //孙子DP和  
int maxL; //最大层次  
int n;  

/*********************************/  
//* 读入无根树,n顶点,n-1边  
/*********************************/  

void readTree()  
{  
    int u,v;  
    cin>>n;  
    for(int i=0;i<n-1;++i)  
    {  
        cin>>u>>v;  
        G[u].push_back(v);  
        G[v].push_back(u);  
    }  
}  

/*********************************/  
/* 以无根树u顶点为根,构造有根树  
* 主函数调用dfs(u,-1);  
* 测试数据:  
    8  
    0 1  
    1 4  
    0 2  
    0 3  
    1 5  
    5 6  
    5 7  
/*********************************/  

void dfs(int u,int fa)  //转换树为以u为根节点的树
{
    int d=G[u].size();  
     l[u]= (fa==-1)? 0: (l[fa]+1);  
     if(l[u]>maxL){  
         maxL=l[u];  
     }  
    for(int i=0;i<d;++i){  
        int v=G[u][i];  //节点u的第i个相邻节点
        if(v!=fa){  //判断条件很重要,没有这个将会引起无限递归
            dfs(v,p[v]=u);  //把v的父节点设置为u,然后递归转化以v为根的子树。
        }  
    }  
}  

int max(int x,int y){//啃爹的VC6.0没有max函数自己写了一个
	return x >  y? x : y;
}

int rootDp(int u)  
{  
    //构造u根树  
    p[u]=-1;  
    maxL=-1;  
    dfs(u,p[u]);  
    for(int i=maxL;i>=0;--i)  
    {  
        for(int j=0;j<n;++j)  
        {  
            if(l[j]==i)  
            {  
                dp[j]=max(sumS[j]+1,sumC[j]);  
                if(i-1>=0)  
                {  
                    sumC[p[j]]+=dp[j];  
                }  
                if(i-2>=0)  
                {  
                    sumS[p[p[j]]]+=dp[j];  
                }  
            }  
        }  
    }  
    return dp[u];  
}  

int main()  
{  
    readTree();  
    int best=-1;  
    //分别以每个顶点为根  
    for(int i=0;i<n;++i)  
    {  
        memset(sumS,0,sizeof(sumS));  
        memset(sumC,0,sizeof(sumC));  
        int tmp;  
        if((tmp=rootDp(i))>best)  
        {  
            best=tmp;  
        }  
    }  
    //打印结果看看  
    cout<<best<<endl;  
    return 0;  
}  

表达式树

用树来表达一个表达式