论坛 › 数据结构与算法 › 求大佬看看

ZXPoo 发表于 2022-12-23 14:07:51

求大佬看看

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>

typedef char bitreeElemType;
typedef struct BiNode                                        //定义二叉链表
{
        bitreeElemType data;
        struct BiNode* lchild, * rchild;
}BiNode,*BiTree;

int leaf = 0;

BiTree creat(int n, char qian[], char zhong[]);                //先序中序恢复二叉树
void pre_traverse_Bitree(BiTree T);                        //先序遍历
void in_traverse_Bitree(BiTree T);                        //中序遍历
void post_traverse_Bitree(BiTree T);                //后序遍历
int Gethight_Bitree(BiTree T);                                //求高度
int Getleaf_Bitree(BiTree T);                                //求叶子数

BiTree creat(int n, char qian[], char zhong[])
{
        int i;
        BiTree root;
        if (n == 0)
        {
                return NULL;
        }
        root = (BiTree)malloc(sizeof(BiNode));
        root->data = qian;//根节点一定是先序排列的第一个
        for (i = 0; i < n; i++)
        {
                if (zhong == qian)//找到中序序列中与根节点相等的位置
                {
                        break;
                }
        }
        root->lchild = creat(i, qian + 1, zhong);//逐步遍历
        root->rchild = creat(n - i - 1, qian + 1 + i, zhong + 1 + i);
        return root;
}

void pre_traverse_Bitree(BiTree T)
{
        if (!T)
                return;
        printf("%c", T->data);
        pre_traverse_Bitree(T->lchild);
        pre_traverse_Bitree(T->rchild);
}

void in_traverse_Bitree(BiTree T)
{
        if (!T)
                return;
        in_traverse_Bitree(T->lchild);
        printf("%c", T->data);
        in_traverse_Bitree(T->rchild);
}

void post_traverse_Bitree(BiTree T)
{
        if (!T)
                return;
        post_traverse_Bitree(T->lchild);
        post_traverse_Bitree(T->rchild);
        printf("%c", T->data);
}

int Gethight_Bitree(BiTree T)
{
        if (!T)
                return 0;
        return Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild) ? Gethight_Bitree(T->lchild) + 1
                                                                                                                                   : Gethight_Bitree(T->rchild) + 1;
}

int Getleaf_Bitree(BiTree T)
{
        if (!T)
                return 0;
        if (T->lchild == NULL && T->rchild == NULL)
                return ++leaf;
        Getleaf_Bitree(T->lchild);
        Getleaf_Bitree(T->rchild);
}


int main()
{
        int n;
        printf("请输入节点数\n");
        scanf("%d", &n);
        char qian, zhong;
        printf("请输入先序\n");
        for(int i=0;i<n;i++)
        {
                scanf("%c",&qian);
        }
        printf("请输入中序\n");
                for(int i=0;i<n;i++)
        {
                scanf("%c",&zhong);
        }
        BiTree T;
        T = creat(n,qian,zhong);
        printf("先序遍历为： \n");
        pre_traverse_Bitree(T);
        printf("该树高度为： %d\n", Gethight_Bitree(T));
        printf("该树有%d个叶子\n", Getleaf_Bitree(T));

        return 0;
}


先序中序恢复出来的二叉树怎么写才能成为其他函数的参数啊？我的运行结果到把中序敲上去就直接完了。问老师老师一点有用的都不说。求回复

人造人 发表于 2022-12-23 14:16:26

先序中序恢复出来 的二叉树怎么写才能成为其他函数的参数啊？

恢复出来？什么意思？
恢复出来的二叉树？
怎么个恢复出来？

看不懂你的问题，重新组织一下语言，把你的问题说清楚
你的老师不理你，大概是因为他看不懂你在说什么吧

ZXPoo 发表于 2022-12-23 14:23:06

人造人 发表于 2022-12-23 14:16
先序中序恢复出来 的二叉树怎么写才能成为其他函数的参数啊？

恢复出来？什么意思？


题目是让用先序和中序先把二叉树恢复出来，再进行遍历求叶子和高度这些操作。
我问的意思就是用先序和中序恢复出来的二叉树怎么进行遍历那些操作。

人造人 发表于 2022-12-23 14:39:34

ZXPoo 发表于 2022-12-23 14:23
题目是让用先序和中序先把二叉树恢复出来，再进行遍历求叶子和高度这些操作。
我问的意思就是用先序和中 ...

第108行不就是在遍历么？

ZXPoo 发表于 2022-12-23 14:41:05

人造人 发表于 2022-12-23 14:39
第108行不就是在遍历么？

但是运行窗口运行到把中序输入进去就结束了。
不知道是哪没写对。

人造人 发表于 2022-12-23 16:04:36

程序是调试出来的，要调试程序的说

#include <stdio.h>
#include <stdlib.h>

typedef char bitreeElemType;
typedef struct BiNode //定义二叉链表
{
    bitreeElemType data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

//int leaf = 0;

BiTree creat(int n, char qian[], char zhong[]); //先序中序恢复二叉树
void pre_traverse_Bitree(BiTree T);             //先序遍历
void in_traverse_Bitree(BiTree T);            //中序遍历
void post_traverse_Bitree(BiTree T);            //后序遍历
int Gethight_Bitree(BiTree T);                  //求高度
int Getleaf_Bitree(BiTree T);                   //求叶子数

BiTree creat(int n, char qian[], char zhong[]) {
    int i;
    BiTree root;
    if(n == 0) {
      return NULL;
    }
    root = (BiTree)malloc(sizeof(BiNode));
    root->data = qian; //根节点一定是先序排列的第一个
    for(i = 0; i < n; i++) {
      if(zhong == qian) //找到中序序列中与根节点相等的位置
      {
            break;
      }
    }
    root->lchild = creat(i, qian + 1, zhong); //逐步遍历
    root->rchild = creat(n - i - 1, qian + 1 + i, zhong + 1 + i);
    return root;
}

void pre_traverse_Bitree(BiTree T) {
    if(!T)
      return;
    printf("%c", T->data);
    pre_traverse_Bitree(T->lchild);
    pre_traverse_Bitree(T->rchild);
}

void in_traverse_Bitree(BiTree T) {
    if(!T)
      return;
    in_traverse_Bitree(T->lchild);
    printf("%c", T->data);
    in_traverse_Bitree(T->rchild);
}

void post_traverse_Bitree(BiTree T) {
    if(!T)
      return;
    post_traverse_Bitree(T->lchild);
    post_traverse_Bitree(T->rchild);
    printf("%c", T->data);
}

int Gethight_Bitree(BiTree T) {
    if(!T) return 0;
    /*
    return Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
               ? Gethight_Bitree(T->lchild) + 1
               : Gethight_Bitree(T->rchild) + 1;
   */
    return (Gethight_Bitree(T->lchild) > Gethight_Bitree(T->rchild)
         ? Gethight_Bitree(T->lchild)
         : Gethight_Bitree(T->rchild)) + 1;
}

/*
int Getleaf_Bitree(BiTree T) {
    if(!T)
      return 0;
    if(T->lchild == NULL && T->rchild == NULL)
      return ++leaf;
    Getleaf_Bitree(T->lchild);
    Getleaf_Bitree(T->rchild);

    // return ???
}
*/

int Getleaf_Bitree(BiTree T) {
    if(!T) return 0;
    if(T->lchild == NULL && T->rchild == NULL) return 1;
    return Getleaf_Bitree(T->lchild) + Getleaf_Bitree(T->rchild);
}

// 求你们了，释放一下内存吧
// 知道windows为什么连一个月也运行不了吗？
// 就是因为你们写程序，不释放内存
void tree_free(BiTree T) {
    if(!T) return;
    tree_free(T->lchild);
    tree_free(T->rchild);
    free(T);
}

int main() {
    int n;
    printf("请输入节点数\n");
    scanf("%d", &n);
    char qian, zhong;
    printf("请输入先序\n");




    // *************************
    getchar();// '\n'
    // *************************



    for(int i = 0; i < n; i++) {
      scanf("%c", &qian);
    }
    printf("请输入中序\n");




    // *************************
    getchar();// '\n'
    // *************************



    for(int i = 0; i < n; i++) {
      scanf("%c", &zhong);
    }
    BiTree T;
    T = creat(n, qian, zhong);
    printf("先序遍历为： \n");
    pre_traverse_Bitree(T);
    printf("该树高度为： %d\n", Gethight_Bitree(T));
    printf("该树有%d个叶子\n", Getleaf_Bitree(T));

    tree_free(T);

    return 0;
}

人造人 发表于 2022-12-23 16:08:12

参考
https://www.jianshu.com/p/2943a21d2a99

ZXPoo 发表于 2022-12-23 16:28:45

人造人 发表于 2022-12-23 16:04
程序是调试出来的，要调试程序的说

所以之前运行失败是内存的原因吗？
那个tree_free函数是释放内存的吗

人造人 发表于 2022-12-23 16:32:38

ZXPoo 发表于 2022-12-23 16:28
所以之前运行失败是内存的原因吗？
那个tree_free函数是释放内存的吗

还有其他问题，你看代码

ZXPoo 发表于 2022-12-23 16:37:03

人造人 发表于 2022-12-23 16:32
还有其他问题，你看代码

求叶子和高度写错了

人造人 发表于 2022-12-23 16:38:37

ZXPoo 发表于 2022-12-23 16:37
求叶子和高度写错了

什么？

人造人 发表于 2022-12-23 16:40:39

ZXPoo 发表于 2022-12-23 16:37
求叶子和高度写错了

你指的是，你发现了你写的代码中，这两个地方的错误
还是说，我给你改的代码中，这两个地方改错了

说话说清楚

ZXPoo 发表于 2022-12-23 16:40:42

人造人 发表于 2022-12-23 16:38
什么？

求叶子和高度的代码我写错了

人造人 发表于 2022-12-23 16:40:58

ZXPoo 发表于 2022-12-23 16:40
求叶子和高度的代码我写错了

嗯

ZXPoo 发表于 2022-12-23 16:43:05

人造人 发表于 2022-12-23 16:40
嗯

感谢{:5_111:}

查看完整版本: 求大佬看看