数据结构第7章树

1.统计利用先序遍历创建的二叉树的深度
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int heigh(Node *root)
{
int l,r;
if(root==NULL)
return 0;
else
{
l=heigh(root->leftchild);
r=heigh(root->rightchild);
return((l>r)?(l+1):(r+1));
}
}

int main()
{
Node *L;
int n;
precreat(L);
n=heigh(L);
cout<<n;

return 1;
}

2.统计利用先序遍历创建的二叉树叶结点的个数
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int count(Node *root)
{
int l,r;
if(root==NULL)
return 0;
else
{
if((root->leftchild==NULL)&&(root->rightchild==NULL))
return 1;
else
{
l=count(root->leftchild);
r=count(root->rightchild);
return l+r;
}
}
}

int main()
{
Node *L;
int m;
precreat(L);
m=count(L);
cout<<m;

return 1;
}

3.统计利用先序遍历创建的二叉树的度为2的结点个数
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int count(Node *root)
{
int l,r;
if(root==NULL)
return 0;
else
{
if((root->leftchild!=NULL)&&(root->rightchild!=NULL))
return 1;
else
{
l=count(root->leftchild);
r=count(root->rightchild);
return l+r;
}
}
}

int main()
{
Node *L;
int m;
precreat(L);
m=count(L);
cout<<m;

return 1;
}

4.统计利用先序遍历创建的二叉树的度为1的结点个数
int count(Node *root)
{
int t=1,l,r;
if(root==NULL||(root->leftchild!=NULL&&root->rightchild!=NULL)||(root->leftchild==NULL&&root->rightchild==NULL))
return 0;
else
if((root->leftchild!=NULL&&root->rightchild==NULL)||(root->leftchild==NULL&&root->rightchild!=NULL))
{
t++;
count(root->leftchild);
count(root->rightchild);
}
return t;
}

5.统计利用先序遍历创建的二叉树中的空链域个数
#inclu

de<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightc
hild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int nodeTotal(Node *root)
{
if(root==NULL)return 0;
else
{
return 1+nodeTotal(root->leftchild)+nodeTotal(root->rightchild);
}
}

int count1(Node *root)
{
int l,r;
if(root==NULL)
return 0;
else
{
if((root->leftchild==NULL)&&(root->rightchild==NULL))
return 1;
else
{
l=count1(root->leftchild);
r=count1(root->rightchild);
return l+r;
}
}

}

int count2(Node *root)
{
int l,r;
if(root==NULL)
return 0;
else
{
if((root->leftchild!=NULL)&&(root->rightchild!=NULL))
return 1;
else
{
l=count2(root->leftchild);
r=count2(root->rightchild);
return l+r;
}
}

}

int main()
{
Node *L;
int m,n,sum;
precreat(L);
m=count1(L);
n=count2(L);
sum=nodeTotal(L);
cout<<m*2+(sum-m-n);

return 1;
}

6.输出利用先序遍历创建的二叉树的中序遍历序列
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

void inorder(Node *root)
{
if(root!=NULL)
{
inorder(root->leftchild);
cout<<root->data;
inorder(root->rightchild);
}
}

int main()
{
Node *L;
precreat(L);
inorder(L);

return 1;
}

7.输出利用先序遍历创建的二叉树的后序遍历序列
void postorder(Node *root)
{
if(root!=NULL)
{
postorder(root->leftchild);
postorder(root->rightchild);
cout<<root->data;
}
}

8.输出利用先序遍历创建的二叉树的层次遍历序列
void ceng(Node *root)
{
Node *p;
Node *queue[500];
int front,rear;
front=rear=-1;
if(root!=NULL)
{
rear=(rear+1)%500;
queue[rear]=root;
while(rear!=front)
{
front=(front+1)%500;
p=queue[front];
cout<<p->data;
if(p->leftchild!=NULL)
{
rear=(rear+1)%500;
queue[rear]=p->leftchild;
}
if(p->rightchild!=NULL)
{
rear=(rear+1)%500;
queue[rear]=p->rightchild;
}
}
}
}

9.统计先序遍历创建的二叉树的宽度
int BTreeWidth(Node *b)
{
if(b!=NULL)
{
if((b->leftchild==b->rightchild)&&(b->leftchild==NULL))
return 1;
else
return BTreeWidth(b->leftchild) + BTreeWidth(b->rightchild);
}
else
return 0;
}

10.输出用先序遍历创建的二叉树是否为完全二叉树

的判定结果.
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;


void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int compNode(Node *&b)
{
Node *a[50],*p;
int front=0,rear=0;
int cm=1,bj=1;
if(b!=NULL)
{
rear++;
a[rear]=b;
while(front!=rear)
{
front++;
p=a[front];
if(p->leftchild==NULL)
{
bj=0;
if(p->rightchild!=NULL)
cm=0;
}
else
{
if(bj==1)
{
rear++;
a[rear]=p->leftchild;
if(p->rightchild==NULL)
bj=0;
else
{
rear++;
a[rear]=p->rightchild;
}
}
else
cm=0;
}
}
return cm;
}
return 1;
}

int main()
{
Node *L;
precreat(L);
if(compNode(L)==1)
cout<<"Y";
else
cout<<"N";

return 1;

}

11.输出利用先序遍历创建的二叉树中的指定结点的孩子结点
#include<malloc.h>
#include<iostream>
using namespace std;

typedef struct node
{
char data;
node *leftchild,*rightchild;
}Node;

void precreat(Node *&root)
{
char ch;
cin>>ch;
if(ch!='#')
{
root=(Node *)malloc(sizeof(Node));
root->data=ch;
root->leftchild=NULL;
root->rightchild=NULL;

precreat(root->leftchild);
precreat(root->rightchild);
}
}

int find(Node *&b,char x)
{
if(b==NULL)
return 0;
else if(b->data==x)
{
if(b->leftchild!=NULL&&b->rightchild!=NULL)
{
cout<<"L:"<<b->leftchild->data<<",";
cout<<"R:"<<b->rightchild->data;
}
else if(b->leftchild!=NULL&&b->rightchild==NULL)
{
cout<<"L:"<<b->leftchild->data<<",";
cout<<"R:#";
}
else if(b->leftchild==NULL&&b->rightchild!=NULL)
{
cout<<"L:#"<<",";
cout<<"R:"<<b->rightchild->data;
}
else
{
cout<<"L:#"<<",";
cout<<"R:#";
}
}
else
{
find(b->leftchild,x);
find(b->rightchild,x);
}
}

int main()
{
Node *L;
char a;
precreat(L);
cin>>a;
find(L,a);

}

12.输出利用先序遍历创建的二叉树中的指定结点的度
int count(Node *&b,char x)
{
if(b==NULL)
return 0;
else if(b->data==x)
{
if(b->leftchild!=NULL&&b->rightchild!=NULL)
{
cout<<"2";
}
else if(b->leftchild!=NULL&&b->rightchild==NULL)
{
cout<<"1";
}
else if(b->leftchild==NULL&&b->rightchild!=NULL)
{
cout<<"1";
}
else
{
cout<<"0";
}
}
else
{
count(b->leftchild,x);
cou

nt(b->rightchild,x);
}
}

13.输出利用先序遍历创建的二叉树中的指定结点的双亲结点
int findp(Node *&b,char x)
{
if(b==NULL)
return 0;
else if(b->data==x)
{
cout<<"#";
return 0;
}
else if(b->leftchild!=NULL&&b->leftchild->data==x||b->rightchild!=NULL&&b->rightchild->data==x)
{
cout<<b->data;
return 1;
}
else
{
findp(b->leftchild,x);
findp(b->rightchild,x);
}
}

14.统计利用二叉树存
储的森林中树的棵数
int count(Node *&b)
{
int n=1;
while(b->rightchild!=NULL)
{
n++;
b=b->rightchild;
}

return n;
}

15.输出利用二叉树存储的普通树的度
int count(Node *&b)
{
int n=1;
if(b->rightchild!=NULL)
cout<<"ERROR";
else if(b->leftchild!=NULL)
{
b=b->leftchild;
while(b->rightchild!=NULL)
{
n++;
b=b->rightchild;
}
cout<<n;
}
return 1;
}

16.利用二叉树中序及先序遍历确定该二叉树的后序序列
#include<stdio.h>
#include<string.h>
#include<malloc.h>

typedef struct node
{
char c;
struct node *l;
struct node *r;
}Node;

void plrd(Node *root)
{
if (root!=NULL)
{
plrd(root->l);
plrd(root->r);
printf("%c",root->c);
}
}

void fun(Node *&root,char a[],char b[],int n)
{
char c;
char a1[500],b1[500],a2[500],b2[500];
int i,flag;
if(n!=0)
{
root=(Node *)malloc(sizeof(Node));
c=b[0];
root->c=c;
root->l=root->r=NULL;
for(i=0;i<n;i++)
{
if(a[i]==c)
{
flag=i;
break;
}
a1[i]=a[i];
b1[i]=b[i+1];
}
fun(root->l,a1,b1,flag);
for(i=0;i<n-flag-1;i++)
{
a2[i]=a[flag+i+1];
b2[i]=b[flag+i+1];
}
fun(root->r,a2,b2,n-flag-1);
}
}

int main()
{
char a[500],b[500];
int n;
Node *h=NULL;
gets(a);
gets(b);
n=strlen(a);
if(a[n-1]=='\r')
{
a[n-1]='\0';
b[n-1]='\0';
n--;
}
fun(h,a,b,n);
plrd(h);
return 1;
}

17.利用二叉树中序及后序遍历确定该二叉树的先序序列
#include<stdio.h>
#include<string.h>

void fun(char a[],char b[],int n)
{
char c;
char a1[500],b1[500],a2[500],b2[500];
int i,flag;
if(n!=0)
{
c=b[n-1];
printf("%c",c);
for(i=0;i<n;i++)
{
if(a[i]==c)
{
flag=i;
break;
}
a1[i]=a[i];
b1[i]=b[i];
}
fun(a1,b1,flag);
for(i=0;i<n-flag-1;i++)
{
a2[i]=a[flag+i+1];
b2[i]=b[flag+i];
}
fun(a2,b2,n-flag-1);
}
}

int main()
{
char a[500],b[500];
int n;
gets(a);
gets(b);
n=strlen(a);
if(a[n-1]=='\r')
{
a[n-1]='\0';
b[n-1]='\0';
n--;
}
fun(a,b,n);
return 1;
}

18.哈夫曼编码
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<iostream>
using namespace std;

typedef struct node
{
char c;
int w;
int l;
int r;
int p;
int flag;
}Node;


void cr(Node *l,int n)
{
int i,j,min1,min2

;
for(i=0;i<n-1;i++)
{
min2=min1=0;
for(j=0;j<n+i;j++)
{
if(l[j].flag==-1)
{
if(l[min1].flag==0)
min1=j;
if(l[min1].w>l[j].w)
{
min1=j;
}
}
}
l[min1].flag=0;
for(j=0;j<n+i;j++)
{
if(l[min2].flag==0)
min2=j;
if(l[j].flag==-1)
{
if(l[min2].w>l[j].w)
{
min2=j;
}
}
}
l[min2].flag=0;
l[n+i].w=l[min1].w+l[min2].w;
l[min1].p=l[min2].p=n+i;
l[n+i].l=min1;
l[n+i].r=min2;
}
}

void pr(Node *l,int n)
{
int *a;
int i,j,top;
a=(int *)malloc(
(n-1)*sizeof(int));
top=-1;
for(i=0;i<n;i++)
{
j=i;
while(j!=2*n-2)
{
if(l[l[j].p].l==j)
{
a[++top]=0;
}
else
{
a[++top]=1;
}
j=l[j].p;
}
for(;top>-1;top--)
printf("%d",a[top]);
printf("\r\n");
}
}

void init(Node *&l,int a[],int n,char c[])
{
int i;
l=(Node *)malloc((2*n-1)*sizeof(Node));
for(i=0;i<2*n-1;i++)
{
l[i].c=l[i].flag=l[i].l=l[i].p=l[i].r=l[i].w=-1;
}
for(i=0;i<n;i++)
{
l[i].c=c[i];
l[i].w=a[i];
}
}

int main()
{
int n,i;
Node *h;
int *a;
char *c;
scanf("%d",&n);
getchar();
getchar();
c=(char *)malloc((n+1)*sizeof(char));
gets(c);
a=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
scanf("%d",a+i);
}
init(h,a,n,c);
cr(h,n);
// for(i=0;i<2*n-1;i++)
// {
// printf("%c,%d,%d,%d,%d,%d\n",h[i].c,h[i].w,h[i].p,h[i].l,h[i].r,h[i].flag);
// }
pr(h,n);
return 1;
}