[数据结构]基于二叉树的家谱系统

基于二叉树的家谱系统

采用一棵二叉树来表示一个家谱关系，一个家谱可表示为一颗树，首先将其转换成一颗二叉树表示，如下图为红楼梦家谱的一部分：

（1） 输入一颗二叉树的括号表示法，完成树的构建
（2） 使用后序遍历递归算法遍历二叉树并输出
（3） 使用先序遍历非递归算法遍历二叉树并输出
（4） 指定家谱中的某一成员，输出其所有长辈

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 

#include"model.h"
#include"menu.h"

int main()
{
    tn* b;

    b = (tn*)malloc(sizeof(tn));

    char s[100];
    printf("请输入括号表达式表示的二叉树结构:");
    gets_s(s);

    b = CreatBTnode(b, s);
    PreOrder(b);
    printf("后序遍历递归算法输出：");
    PostOrder(b);
    printf("n");
    findfather(b);
    return 0;
}

#pragma once
//创建一个二叉链
typedef struct node
{
    char data;
    struct node* lchild;
    struct node* rchild;
}tn;   //struct node 取一个别名叫tn

#pragma once
//构建二叉树
tn* CreatBTnode(tn* b, char s[100]);
//后序递归遍历二叉树
void PostOrder(tn* b);
//先序非递归遍历二叉树
void PreOrder(tn* b);
//查找所有长辈
void findfather(tn* b);

#define _CRT_SECURE_NO_WARNINGS
#include
#include

#include"model.h"

//构建二叉树
tn* CreatBTnode(tn* b, char s[100])
{
    tn* st[100], * p = NULL;
    int top = -1, j = 0, k = 0;
    b = NULL;

    while (s[j] != '')
    {
        if (s[j] == '(')
        {
            top++;
            st[top] = p;
            k = 1;
        }
        else if (s[j] == ')')
        {
            top--;
        }
        else if (s[j] == ',')
        {
            k = 2;
        }
        else
        {
            p = (tn*)malloc(sizeof(tn));
            p->data = s[j];
            p->rchild = p->lchild = NULL;
            if (b == NULL)
                b = p;
            else if (k == 1)
                st[top]->lchild = p;
            else
                st[top]->rchild = p;
        }
        j++;
    }

    return b;
}

//后序递归遍历二叉树
void PostOrder(tn* b)
{
    if (b != NULL)
    {
        PostOrder(b->lchild);
        PostOrder(b->rchild);
        printf("%c", b->data);
    }
}

//先序非递归遍历二叉树
void PreOrder(tn* b)
{
    printf("先序遍历非递归算法输出：");
    tn* a[100], * p;
    int i = -1;

    if (b != NULL)
    {
        i++;
        a[i] = b;
        while (i > -1)
        {
            p = a[i];
            i--;
            printf("%c", p->data);
            if (p->rchild != NULL)
            {
                i++;
                a[i] = p->rchild;
            }
            if (p->lchild != NULL)
            {
                i++;
                a[i] = p->lchild;
            }
        }
        printf("n");
    }
}

//查找所有长辈
void findfather(tn* b)
{
    printf("请输入指定人物代号，以查询其所有长辈：");
    char c;
    scanf("%c", &c);
    printf("%c的所有长辈为：", c);

    tn* a[100], * p;
    if (b != NULL)
    {
        int i = 0;
        a[i] = b;
        p = b;
        while (p->data != c)
        {
            i++;
            a[i] = p->lchild;
            p = a[i];
            if (p->lchild == NULL && p->data != c)
            {
                printf("您输入的指令有误n");
                break;
            }
        }
        i = i - 1;
        while (i >= 0)
        {
            p = a[i];
            printf("%c", p->data);
            while (p->rchild != NULL)
            {
                p = p->rchild;
                printf("%c", p->data);
            }
            i--;
        }
    }
    printf("n");
}