数据结构c语言习题。编写一个函数以二叉查找树T和两个有序的关键字 k1,

Question

数据结构c语言习题。编写一个函数以二叉查找树T和两个有序的关键字 k1,k2作为输入，打印出树中所有满足k1＜＝Key(X)＜=k2的元素X.(详情见图)

Answer 1

// 创建二叉树的原数组数据: 40 20 60 10 30 50 70
// 前序遍历序列: 40 20 10 30 60 50 70
// 中序遍历序列: 10 20 30 40 50 60 70
// 后序遍历序列: 10 30 20 50 70 60 40
// 输入关键字k1,k2的数值: 30 50
// 打印的结果:
// 40 30 50
//
// 二叉树示意图:
//
//       40
//    /      \
//   20       60
//  /  \     /  \
// 10  30   50   70

#include "stdio.h"
#include "stdlib.h"
struct Tree
{
    int data;
    struct Tree *left;
    struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;

Bitree insertNode(Bitree root,int data) //插入结点
{
    Bitree newnode;
    Bitree current;
    Bitree back;
    newnode=(Bitree)malloc(sizeof(TreeNode));
    if(newnode==NULL)
    {
        printf("\n动态分配内存出错.\n");
        exit(1);
    }
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    if(root==NULL)
    {
        return newnode;
    }
    else
    {
        current=root;
        while(current!=NULL)
        {
            back=current;
            if(current->data > data)
               current=current->left;
            else
               current=current->right;
        }
        if(back->data > data)
            back->left=newnode;
        else
            back->right=newnode;
    }
    return root;
}

Bitree createTree(int *data,int len) //创建二叉树(非递归)
{
    Bitree root=NULL;
    int i;
    for(i=0;i<len;i++)
    {
        root=insertNode(root,data[i]);
    }
    return root;
}


void preOrder(Bitree ptr) //先序遍历(递归法)
{
    if(ptr!=NULL)
    {
        printf("%d ",ptr->data);
        preOrder(ptr->left);
        preOrder(ptr->right);
    }
}

void inOrder(Bitree ptr) //中序遍历(递归法)
{
    if(ptr!=NULL)
    {
        inOrder(ptr->left);
        printf("%d ",ptr->data);
        inOrder(ptr->right);
    }
}

void postOrder(Bitree ptr) //后序遍历(递归法)
{
    if(ptr!=NULL)
    {
        postOrder(ptr->left);
        postOrder(ptr->right);
        printf("%d ",ptr->data);
    }
}
//根据关键字k1和k2,进行区间查找(递归法)
void btreeSearch(Bitree ptr,int k1,int k2)
{
    if(ptr!=NULL)
    {
        if(ptr->data < k1 && ptr->data < k2)
        {
            btreeSearch(ptr->right,k1,k2);
        }
        else if(ptr->data == k1 && ptr->data < k2)
        {
            printf("%d ",ptr->data);
            btreeSearch(ptr->right,k1,k2);
        }
        else if(ptr->data > k1 && ptr->data < k2)
        {
            printf("%d ",ptr->data);
            btreeSearch(ptr->left,k1,ptr->data);
            btreeSearch(ptr->right,ptr->data,k2);
        }
        else if(ptr->data > k1 && ptr->data == k2)
        {
            printf("%d ",ptr->data);
            btreeSearch(ptr->left,k1,k2);
        }
        else if(ptr->data > k1 && ptr->data > k2)
        {
            btreeSearch(ptr->left,k1,k2);
        }
        else if(ptr->data == k1 && ptr->data == k2)
        {
            printf("%d ",ptr->data);
        }
        else
        {
           printf("其它情况,当前节点的数值是%d",ptr->data);
        }
    }
}

int main()
{
    Bitree T=NULL; //T是二叉查找树
    int data[]={40,20,60,10,30,50,70};
    int len;
    int i;
    int k1,k2; //关键字k1,k2
    int tmp;

    len=sizeof(data)/sizeof(int);
    printf("创建二叉树的原数组数据: ");
    for(i=0;i<len;i++)
    {
        printf("%d ",data[i]);
    }

    T=createTree(data,len); //创建二叉树

    printf("\n前序遍历序列: ");
    preOrder(T);
    printf("\n中序遍历序列: ");
    inOrder(T);
    printf("\n后序遍历序列: ");
    postOrder(T);

    printf("\n输入关键字k1,k2的数值: ");
    scanf("%d%d",&k1,&k2);
    if(k1>k2)
    {
        tmp=k1;
        k1=k2;
        k2=tmp;
    }
    //根据关键字k1和k2,进行区间查找(递归法)
    btreeSearch(T,k1,k2);

    printf("\n");
    return 0;
}