数据结构第六章习题答案.doc

60
120
80
70
90
40
50
30
删除40
120
80
70
90
50
30
60
删除70
60
90
30
80
120
50
删除60
30
50
90
120
80

struct node { int data;
struct node *lchild, *rchild;
};
typedef struct node NODE;
NODE *create_tree(a,i,j)
int a[ ],i,j;
{
NODE *p;
int k;
if(i>j) return(NULL);
k=(i+j)/2;
p=(NODE *)malloc(sizeof(NODE));
p->data=a[k];
p->lchild=create_tree(a,i,k-1);
p->rchild=create_tree(a,k+1,j);
return(p);
}
6. 3
int check(root)
NODE *root;
{
int x;
if(root==NULL)
return(0);
if(root->data<root->rchild->data&&root->data>root->lchild->data)
{
x=check(root->rchild);
if(!x) return(check(root->lchild));
}
return(1);
}
6. 4
int height(root)
NODE *root;
{
int h,k;
if(root==NULL)
return(-1);
else if(root->lchild==NULL&&root->rchild==NULL)
return(0);
else
{
h=height(root->lchild);
k=height(root->rchild);
if(h>k)
return(h+1);
else
return(k+1);
}
}
6. 5
#include “”
int check_beltree(root)
NODE *root;
{
int a;
if(root==NULL)
return(1);
if(check_beltree(root->lchild)==0||check_beltree(root->rchild)==0)
return(0);
a=abs(height(root->rchild)-height(root->lchild)); //上题函数
if(a<=1)
return(1);
}
ki+1
ki
6. 6

A3t+1
ki
ki+1
A1t
A2t
A1t
A3t+1
A2t
ki+2
ki
ki+1
ki
ki+1
A1t
ki+2
A2t
A2t
A4t
A3t-1
A1t
A4t
A3