find-depth_success.cpp

这是一个算法设计与分析相关的连接两棵树并进行压缩存储。结果返回原树深度的算法。 可以参考一下

//Program Find_depth_liangfeng
#include<iostream.h>
int i,j; 
class tree  //tree是一个类，用来记录各节点的属性值
{
public:

int p;      //对应的父节点
int count;  //对应的子树中节点的个数
int weight; //节点对应的weight值
int w;      //对应原父节点的新weight值
} t[10];     //建立10个tree类型的节点，本程序只用到其中的1-9节点

void find1() //由于本程序中的find(i)不进行weight值得计算，而只是返回它的w值，该子程序用来补充计算weight值
{ for (i=1;i<=9;i++) { t[i].weight+=t[i].w;t[i].w=0;}
}
//***************************************
int find(int i)   //查找节点i对应的根节，修改t[i].w的值
{ if (i==t[i].p) t[i].w=0;
  else if(t[i].p!=i)
  {if (t[i].p==t[t[i].p].p) t[i].w=0;
   else
   { t[i].w=t[t[i].p].w+t[t[i].p].weight;
     t[i].p=find(t[i].p);
   }
  }
  return t[i].p;
}
//****************************************
int find_depth(int v,int v1)//用来求某个节点的深度，形参V1用来记录没有进行Link前v的根节点
{  int root,depth;          //此处没有按照书上所介绍的直接求节点v的深度，而是间接的利用
	root=find(v1);          //v的深度=根节点v1的深度+v到v1路经的权和
	find1();                
    depth=t[v1].weight+t[v1].w;
    while(v1!=v) {depth=depth+t[v].weight;v=t[v].p;}//v的深度=根节点v1的深度+v到v1路经的权和
	return depth;
}
//****************************************
void link(int v,int r)  //用来连接两个节点
{
int v1=find(v);
int r1=find(r);
if (v1==r1)  {cout<<"两个节点已经在同一棵树下";return;}
   if (t[r1].count<=t[v1].count)  //若r1的子节点数小于v1的子节点数，执行
   { t[r1].p=v1;
     t[r1].weight=find_depth(v,v1)+1-t[v1].weight+t[r1].weight;
	 t[v1].count+=t[r1].count;
	 find(v);
	 find1();
   }
   else if(t[r1].count>t[v1].count) //若r1的子节点数大于v1的子节点数，执行
   { t[v1].p=r1;
     t[r1].weight=find_depth(v,v1)+1+t[r1].weight;
	 t[v1].weight=t[v1].weight-t[r1].weight;
	 t[r1].count+=t[v1].count;
	 find(v);
	 find1();
   }
}
//****************************************
void main()
{ bool a;
  int c,v1;   
  a=0; 
 for (i=0;i<=9;i++)  //初始化
  {t[i].p=i;
   t[i].weight=0;
   t[i].count=1;
  } 
 while (a!=1) 
 {  cout<<"请选择执行动作  1: 执行 Link(i,j); "; 
    cout<<"2: 执行find_depth(i)"<<endl;  
    cin>>c;
    if(c==1)  //用来标示选择要进行的动作 选择1执行Link(i,j);
	{ cout<<"请输入要执行link的两个节点i,j"<<endl;
	  cin>>i>>j;
	  link(i,j);
	}
	else if(c==2)  // 选择2执行 find_depth(i)
	{ cout<<"请输入要执行find_depth节点"<<endl;
	  cin>>i;
	  v1=find(i);
	  find_depth(i,v1);
	}
	cout<<"ID  "<<"  p   "<<"weight"<<" count"<<endl;
	for (i=1;i<=9;i++)   //输出节点的属性值
	{ cout<<i<<"     ";
	  cout<<t[i].p<<"     ";
	  cout<<t[i].weight<<"     ";
      cout<<t[i].count<<"     "<<endl;
	}
 }
}