#include <iostream>
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int width(node *t,int l)
{
if(t==NULL)
return 0;
if(l==1)return 1;
if(l>1)
{
return width(t->left,l-1)+width(t->right,l-1);
}
return 0;
}
int treewidth(node *t)
{
int h=height(t);
int maxwidth=0;
for(int i=1;i<=h;i++)
{
int w=width(t,i);
if(w>maxwidth)
maxwidth=w;
}
return maxwidth;
}
int main()
{
int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
cout<<treewidth(t);
return 0;
}
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>=t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int width(node *t,int l)
{
if(t==NULL)
return 0;
if(l==1)return 1;
if(l>1)
{
return width(t->left,l-1)+width(t->right,l-1);
}
return 0;
}
int treewidth(node *t)
{
int h=height(t);
int maxwidth=0;
for(int i=1;i<=h;i++)
{
int w=width(t,i);
if(w>maxwidth)
maxwidth=w;
}
return maxwidth;
}
int main()
{
int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
cout<<treewidth(t);
return 0;
}
No comments:
Post a Comment