欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法与数据结构考研试题精析-第9章算法设计题33

程序员文章站 2022-05-20 10:56:56
...
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef int Status;

typedef struct Node
{
    int data;
    int depth;
    struct Node *llink,*rlink;
}Node,*Tree;

Status SearchBST(Tree T,int key,Tree f,Tree *p);
Status InsertBST(Tree *T,int e);
int Depth_Make(Tree T);
Status TreeBalance(Tree T);

int main()
{
    Tree T;
	T=(Tree)malloc(sizeof(Node));
	T=NULL;
    int e;
    printf("What number you want to search--0 to quit:");
    scanf("%d",&e);
    while(e)
    {
        if(!InsertBST(&T,e))
            printf("Done!");
        else
            printf("It`s been inserted for the first time.");
        printf("\nWhat number you want to search--0 to quit:");
        scanf("%d",&e);
    }
	int h;
	h=0;
	h=Depth_Make(T);
	printf("树的高度为:%d.\n",h);
	if(TreeBalance(T))
        printf("\n是平衡树。\n");
    else
        printf("\n不是平衡树.\n");
    return 0;
}
Status SearchBST(Tree T,int key,Tree f,Tree *p)
{
    if(!T)
    {
        *p=f;
        return FALSE;
    }
    else if(key==T->data)
    {
        *p=T;
        return TRUE;
    }
    else if(key<T->data)
    {
        return SearchBST(T->llink,key,T,p);
    }
    else
        return SearchBST(T->rlink,key,T,p);
}

Status InsertBST(Tree *T,int e)
{
    Tree p;
    p=(Tree)malloc(sizeof(Node));

    if(!SearchBST(*T,e,NULL,&p))
    {
        Tree s;
        s=(Tree)malloc(sizeof(Node));
        s->data=e;
        s->llink=s->rlink=NULL;
        s->depth=1;
        if(!p)
            (*T)=s;
        else if(e<p->data)
            p->llink=s;
        else
            p->rlink=s;
        return TRUE;
    }
    else
        return FALSE;
}
int Depth_Make(Tree T)
{
    if(T)
    {
        int left,right;
		left=right=0;
		if(T->llink)
			left=Depth_Make(T->llink);
        if(T->rlink)
			right=Depth_Make(T->rlink);
        T->depth+=(left>right?left:right);

        return T->depth;
    }
}
Status TreeBalance(Tree T)
{
    if(T->llink ||T->rlink)
    {
        int left,right;
        left=right=0;
        if(T->llink)
            left=T->llink->depth;
        if(T->rlink)
            right=T->rlink->depth;
        if(left-right>1 || right-left>1)
            return FALSE;
        else if(TreeBalance(T->llink) && TreeBalance(T->rlink))
            return TRUE;
        else
            return FALSE;
    }
    else
        return TRUE;
}
相关标签: 平衡二叉树