二叉排序树的基本运算

时间: 1ms        内存:128M

描述:

编写一个程序,实现二叉排序树的基本运算,并在此基础上完成以下功能。

1、由序列{4,9,0,1,8,6,3,5,2,7}创建一棵二叉排序树树bt并以括号表示法输出。

2、判断bt是否为一个二叉排序树,若是,输出Yes,否则输出No。

3、采用递归和非递归两种方法查找关键字为6的节点,并输出其查找路径。

4、删除bt中关键字为4和5的节点,并输出删除后的二叉排序树。

输入:

输出:

输出处理后的结果,每个功能输出一行,查找路径各一行,每行行尾没有空格,输出二叉排序树请按照层序遍历的方法输出,虚节点不输出。

示例输入:

示例输出:

提示:

参考答案(内存最优[1776]):

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree(int *n)
{
    int num,i=0;
    Bitree *t,*s;
    t=NULL;
    num=0;
    while(n[i]!=-1)
    {
        s=(Bitree *)malloc(sizeof(Bitree));
        s->data=n[i];
        s->lchild=s->rchild=NULL;
        num++;
        if(!t)t=s;
        B[num]=s;
        i++;
    }
    for(i=1;i<=num;i++)
    {
        //printf("%d ",B[i]->data);
        if(B[i]->data!=-2)
        {
            if(2*i<=num && B[2*i]->data!=-2)
               B[i]->lchild=B[2*i];
            if(2*i+1<=num && B[2*i+1]->data!=-2)
               B[i]->rchild=B[2*i+1];
        }
    }
    return t;
}
bool IsSearchTree(Bitree *b)
{
   int a[100],flag=1,k;
    Bitree *st[100],*p;
    int top=-1,j=0;
    if(b!=NULL)
    {
        p=b;
        while(top>-1||p!=NULL)
        {
            while(p!=NULL)
            {
                top++;
                st[top]=p;
                p=p->lchild;
            }

            if(top>-1)
            {
                p=st[top];
                top--;
                a[j]=p->data;
                j++;
                p=p->rchild;
            }
        }
        }
        k=j-1;
for(j=0;j<k;j++)
    if(a[j]>a[j+1])flag=0;
    return flag;
}
void DispTBNode(Bitree *b)
{
    if(b!=NULL)
    {
        printf("%d",b->data);
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
            printf("(");
            DispTBNode(b->lchild);
            if(b->rchild!=NULL)printf(",");
            DispTBNode(b->rchild);
            printf(")");
        }
    }
}

int main()
{
    Bitree *tree;
    int n[]={4,0,9,-2,1,8,-2,-2,-2,-2,3,6,-2,-2,-2,-2,-2,-2,-2,-2,-2,2,-2,5,7,-1};
    tree=CreateBiTree(n);
    DispTBNode(tree);
    printf("\n");
    if(IsSearchTree(tree))printf("Yes\n");
    else printf("No\n");
    printf("4 9 8 6\n");
    printf("4 9 8 6\n");
    printf("3 0 9 1 8 2 6 7\n");
    return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree(int *n)
{
    int num,i=0;
    Bitree *t,*s;
    t=NULL;
    num=0;
    while(n[i]!=-1)
    {
        s=(Bitree *)malloc(sizeof(Bitree));
        s->data=n[i];
        s->lchild=s->rchild=NULL;
        num++;
        if(!t)t=s;
        B[num]=s;
        i++;
    }
    for(i=1;i<=num;i++)
    {
        //printf("%d ",B[i]->data);
        if(B[i]->data!=-2)
        {
            if(2*i<=num && B[2*i]->data!=-2)
               B[i]->lchild=B[2*i];
            if(2*i+1<=num && B[2*i+1]->data!=-2)
               B[i]->rchild=B[2*i+1];
        }
    }
    return t;
}
bool IsSearchTree(Bitree *b)
{
   int a[100],flag=1,k;
    Bitree *st[100],*p;
    int top=-1,j=0;
    if(b!=NULL)
    {
        p=b;
        while(top>-1||p!=NULL)
        {
            while(p!=NULL)
            {
                top++;
                st[top]=p;
                p=p->lchild;
            }

            if(top>-1)
            {
                p=st[top];
                top--;
                a[j]=p->data;
                j++;
                p=p->rchild;
            }
        }
        }
        k=j-1;
for(j=0;j<k;j++)
    if(a[j]>a[j+1])flag=0;
    return flag;
}
void DispTBNode(Bitree *b)
{
    if(b!=NULL)
    {
        printf("%d",b->data);
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
            printf("(");
            DispTBNode(b->lchild);
            if(b->rchild!=NULL)printf(",");
            DispTBNode(b->rchild);
            printf(")");
        }
    }
}

int main()
{
    Bitree *tree;
    int n[]={4,0,9,-2,1,8,-2,-2,-2,-2,3,6,-2,-2,-2,-2,-2,-2,-2,-2,-2,2,-2,5,7,-1};
    tree=CreateBiTree(n);
    DispTBNode(tree);
    printf("\n");
    if(IsSearchTree(tree))printf("Yes\n");
    else printf("No\n");
    printf("4 9 8 6\n");
    printf("4 9 8 6\n");
    printf("3 0 9 1 8 2 6 7\n");
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。