aq1229 2023-04-17 22:40 采纳率: 37.5%
浏览 75
已结题

关于#c++#的问题,如何解决?

除嵌套括号方式显示二叉排序树以外,增加倒立的树的形式显示。下面的代码已经有嵌套括号方式,求补充“倒立的树的形式显示二叉排序树”代码

#include <math.h>

#include <stdio.h>
#include <stdlib.h>
#include <iostream>    //引用头文件,不需要声明名字空间
#define ENDKEY 0
using namespace std;
typedef int KeyType;

typedef struct  node
{
    KeyType  key ; /*关键字的值*/
    struct node  *lchild,*rchild;/*左右指针*/
}BSTNode, *BSTree;



void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序树中不存在关键字等于key的元素,插入该元素*/
{ 
    BSTree s;
    if (*bst == NULL)/*递归结束条件*/
    {
        s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/
        s-> key=key;
        s->lchild=NULL; 
        s->rchild=NULL;
        *bst=s;
    }
    else 
        if (key < (*bst)->key)
            InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
        else 
            if (key > (*bst)->key)
                InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
}

void  CreateBST(BSTree  *bst)
/*从键盘输入元素的值,创建相应的二叉排序树*/
{ 
    KeyType key;
    *bst=NULL;
    scanf("%d", &key);
    while (key!=ENDKEY)   /*ENDKEY为自定义常量*/
    {
        InsertBST(bst, key);
        scanf("%d", &key);
    }
}

void  PreOrder(BSTree root) 
/*先序遍历二叉树, root为指向二叉树根结点的指针*/
{
    if (root!=NULL)
    {
        printf("%d  ",root->key);  /*输出结点*/
        PreOrder(root->lchild);  /*先序遍历左子树*/
        PreOrder(root->rchild);  /*先序遍历右子树*/
    }
}



//查找的递归算法
BSTNode *SearchBST(BSTree root, int k){
    if(!root){
        printf("查找失败");
    }
    else{
        if(root->key == k){
            //return root;
            printf("%d  ",root->key);
        }
        else if(k < root->key){
            printf("%d  ",root->key);
            SearchBST(root->lchild, k);
        }
        else if(k > root->key){
            printf("%d  ",root->key);
            SearchBST(root->rchild, k);
        }
    }
    
}
/*
//查找的非递归算法            (ps:适用于查找存在于该二叉排序树的结点)
BSTNode *SearchBST(BSTree root, int k){
    BSTNode *p = root;
    while(p!=NULL && p->key!=k){
        printf("%d",p->key);
        if(k < p->key){
            p = p->lchild;
            //printf("%d",p->key);
        }
        else{
            p = p->rchild;
            //printf("%d",p->key);
        }
        
    }
    
    printf("%d",p->key);
}

*/
//计算数的高度
int height(BSTree T)//将左子树和右子树的高度比大小,大的那边子树的高度加1,就是数的高度
{
    int max;
    if(T==NULL)//一定要设置好这样的递归出口
        return 0;
    else
    {
        int left_h=height(T->lchild);
        int right_h=height(T->rchild);
        int max=left_h;
        if(right_h>max)
            max=right_h;
        return max+1;
    }
}

//二叉树的的嵌套括号表示:
void Show(BSTree T)
{
    if(T)
    {
        cout<<T->key;       //为了将c++和c区分开,规定c++的头文件都没有后缀.h,当时用iostream的时候(预定义的对象 cin 和cout是 iostream 类的一个实例),就需要用namespace std来配合,才能使用cin或cout的这种标识符。
        if(T->lchild||T->rchild)
        {
            cout<<"(";
            Show(T->lchild);
            cout<<",";
            Show(T->rchild);
            cout<<")";
        }
    }
}

void Succlength(BSTree T,int &sumlen,int &m,int level) //求查找成功总的比较次数sumlen和情况数m
{
    if (T==NULL) return;    //空树直接返回
    m++;
    sumlen+=level;
    Succlength(T->lchild,sumlen,m,level+1);
    Succlength(T->rchild,sumlen,m,level+1);
    
}
double prSucclength(BSTree T)    //输出查找成功总的比较次数sumlen
{
    int sumlen=0,m=0;
    Succlength(T,sumlen,m,1);
    printf("查找成功的比较次数:%d\n",sumlen);
}
double ASLsucc(BSTree T)    //求查找成功情况下的平均查找长度
{
    int sumlen=0,m=0;
    Succlength(T,sumlen,m,1);
    return sumlen*1.0/m;
}


void Unsucclength(BSTree T,int &sumlen,int &m,int level) //求查找失败总的比较次数sumlen和情况数m
{
    if (T==NULL)        //空指针对应外部节点
    {
        m++;
        sumlen+=level-1;
        return;
    }
    Unsucclength(T->lchild,sumlen,m,level+1);
    Unsucclength(T->rchild,sumlen,m,level+1);
}
double prUnsucclength(BSTree T)    //输出查找失败比较次数 sumlen
{
    int sumlen=0,m=0;
    Unsucclength(T,sumlen,m,1);
    printf("查找失败的比较次数:%d\n",sumlen);
}
double ASLunsucc(BSTree T)    //求查找失败情况下的平均查找长度
{
    int sumlen=0,m=0;
    Unsucclength(T,sumlen,m,1);
    return sumlen*1.0/m;
}


int main()
{
    BSTree T;
    int k;
    BSTree result;
    printf("建立二叉排序树,请输入序列:\n");
    CreateBST(&T);
    printf("先序遍历输出序列为:");
    PreOrder(T);
    printf("\n请输入要查找的元素:");
    fflush(stdin);//fflush (stdin)是一个计算机专业术语,功能是清空输入 缓冲区 ,通常是为了确保不影响后面的数据读取(例如在读完一个 字符串 后紧接着又要读取一个字符,此时应该先执行fflush (stdin);。
    scanf("%d",&k);
    printf("\n递归或非递归实现二叉排序树的查找并给出查找路径:");
    SearchBST(T, k);
    
    printf("\n二叉树的的嵌套括号表示:");
    Show(T);
    
    
    
    int h;
    h=height(T);
    printf("\n该二叉排序树的高度为:%d\n",h);
    
    int sumlen=0,m=0;
    prSucclength(T);
    prUnsucclength(T);
    printf("(3)ASLsucc=%g\n",ASLsucc(T));     //ASL = 1/6 * (1+2+2+3+3+3) = 14/6
    printf("(4)ASLunsucc=%g\n",ASLunsucc(T));
    
    //{45,24,53,12,37,93} 和 {12,24,37,45,53,93}
    
    
    
    
    
    
}


  • 写回答

5条回答 默认 最新

  • 「已注销」 2023-04-17 22:50
    关注

    引用new bing部分回答作答:
    以下是可以实现倒立树形式显示二叉排序树的代码:

    void InvertShow(BSTree T, int level) {
        if (T == NULL) return;
    
        InvertShow(T->rchild, level + 1);
        for (int i = 1; i <= level; ++i) {
            printf("    ");
        }
        printf("%d\n", T->key);
        InvertShow(T->lchild, level + 1);
    }
    
    

    这个函数的功能是将二叉排序树倒过来,并以树形式打印出来。函数的参数T表示二叉排序树的根节点,level表示节点所在的深度,根节点的深度为1,左儿子的深度为父节点深度加1,右儿子的深度也为父节点深度加1。
    函数的实现原理是先遍历右子树,然后在屏幕上打印节点的值,最后遍历左子树。在打印节点的值之前,需要先打印若干个空格,其数量为该节点的深度乘以一个固定的值(例如4)。

    另外,由于本代码使用了printf函数来输出结果,因此需要包含stdio.h头文件。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

问题事件

  • 系统已结题 4月26日
  • 已采纳回答 4月18日
  • 创建了问题 4月17日

悬赏问题

  • ¥15 小贝360-4 配二个 华772S 设置WⅰFi5G 连接
  • ¥15 vs2022的QT报错,好像是缺少winextras
  • ¥15 怎么看 cst中一个面的功率分布图
  • ¥15 c语言数据结构求9999
  • ¥15 Fiddler无法对部分小程序抓包
  • ¥60 Python代码 ip首部检验和计算代码 版本协议 首部长度 源地址 目的地址 存活时间
  • ¥18 微机原理汇编的综合实验
  • ¥15 LD衰减图用R语言对其可视化
  • ¥15 Mermaid语法生成的svg在Axure无法编辑
  • ¥15 Windchill二次开发