【C语言】数据结构C语言版实验7 二叉树

矫情吗；* 2022-12-27 09:14 138阅读 0赞

/*
    编写算法函数void preorder1(bintree t)实现二叉树t的非递归前序遍历。
    */
    #include "bintree.h"
    char *a="ABC##D#E##F##";  /*扩充二叉树序树t的前序序列*/
    /*函数preorder1()的功能是非递归前序遍历二叉树t，请将函数补充完整并调试运行*/
    void preorder1(bintree t)
    {
        seqstack s;//顺序栈s 
        s.top=0;
        while((t) || (s.top!=0)) //当前处理的子树不为空或栈不为空则循环 
        {
            if(t)
            {
                printf("%c ",t->data);
                push(&s,t);
                t=t->lchild;
            }
            else
            {
                t=pop(&s);
                t=t->rchild;
            }
        }
    }
    int main()
    {   bintree t;
        t=creatbintree();   /*建立二叉树t的存储结构*/
        printf("二叉树的前序序列为：\n");
        preorder1(t);       /*前序非递归遍历二叉树*/
        return 0;
    }

/*
    编写算法函数void levelbintree(bintree t)，实现二叉树的层次遍历。
    */
    #include "bintree.h"
    char *a="ABC##D#E##F##";              /*扩充二叉树序树t的前序序列*/
    void levelbintree(bintree t)
    {
        bintree queue[100];
        int f=0,r=1;
        bintree p;
        queue[0]=t;
        while(f<r)
        {
            p=queue[f]; f++; printf("%c",p->data);
            if(p->lchild)
                queue[r++]=p->lchild;
            if(p->rchild)
                queue[r++]=p->rchild;
        }
    }
    int main()
    {   bintree t;
        t=creatbintree();       /*建立二叉树t的存储结构*/
        printf("二叉树的层次序列为：\n");
        levelbintree(t);       /*层次遍历二叉树*/
        return 0;
    }

/*
    编写函数bintree prelist(bintree t)，bintree postfirst(bintree t)，
    分别返回二叉树t在前序遍历下的最后一个结点地址和后序遍历下的第一个结点地址。
    */
    #include "bintree.h"
    char *a="ABC##D##EF#G###";  /*扩充二叉树序树t的前序序列*/
    bintree prelast(bintree t)
    {    //右下叶子结点                                                
        bintree p;
        if(t)
        {
            p=t;
            while(p&&p->lchild||p->rchild)
            {
                if(p->rchild)
                {
                    p=p->rchild;
                }
                else
                {
                    p=p->lchild;
                }
            }
        }
        return p; //返回前序序列最后一个结点G 
    }
    bintree postfirst(bintree t)
    {                //后序遍历是左子树-右子树-根结点 ,二叉树的左下叶子结点是第一个 
        bintree p;
        if(t)
        {
            while(p&&p->lchild||p->rchild)
            {
                if(p->lchild)
                {
                    p=p->lchild;
                }
                else
                {
                    p=p->rchild;
                }
            }
        }
        return p;//返回后序序列第一个结点 C
    }
    int main()
    {   bintree t,p,q;
        t=creatbintree();       /*建立二叉树t的存储结构*/
         p=prelast(t);
        //q=postfirst(t);
        if (t!=NULL)
                { printf("前序遍历最后一个结点为：%c\n",p->data);
                  // printf("后序遍历第一个结点为：%c\n",q->data);
                }
         else    printf("二叉树为空！");
        return 0;
    }

/*
    假设二叉树采用链式方式存储，t为其根结点，编写一个函数int Depth(bintree t, char x)，求值为x的结点在二叉树中的层次。
    */
    #include "bintree.h"
    char *a="ABC##D##EF#G###";          /*扩充二叉树序树t的前序序列*/
    /*
         函数Depth，功能：求结点x所在的层次
    */
    int Depth(bintree t,char x)
    {
        int num1,num2,n;//num1,num2分别记录在左子树，右子树中查找到x的层数,n记录最终返回的结果层数
        if(t==NULL)
        {
            return 0;
        }
        else
        {
            if(t->data==x)
            {
                return 1;
            }
            num1=Depth(t->lchild,x);
            num2=Depth(t->rchild,x);
            n=num1+num2; //num1和num2之中必有一个为0 
            if(num1!=0||num2!=0) //找到了x ，往回数 
            {
                n++;
            }
        }
        return n;
    }
    int main()
    {  bintree root;
       char x;
       int k=0;
       root=creatbintree();
       printf("请输入树中的1个结点值：\n");
       scanf("%c",&x);
       k=Depth(root,x);
       printf("%c结点的层次为%d\n",x,k);
    }

/*
       试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。
    */
    #include "bintree.h"
    char *a="ABC##D##EF#G###";          /*扩充二叉树序树t的前序序列*/
    /*请将本函数补充完整，并进行测试*/
    void change(bintree t)
    {
        bintree p;
        if(t)
        {
            p=t->lchild; //交换 
            t->lchild=t->rchild;
            t->rchild=p;
            change(t->lchild); //继续递归 
            change(t->rchild);
        }
    }
    int main()
    {  bintree root;
       root=creatbintree();
       change(root);
       preorder(root);
    }

/*
    试编写一个递归函数bintree buildBintree(char *pre, char *mid, int length)，
    根据二叉树的前序序列pre、中序序列mid和前序序列长度length，构造二叉树的二叉链表存储结构，
    函数返回二叉树的树根地址。
    */
    #include "bintree.h"
    #include <string.h>
    char *a="";
    /*请将本函数补充完整，并进行测试*/
    bintree buildBintree(char *pre, char *mid,int length)
    {
        bintree t;
        int i=0;
        if(length)
        {
            t=(bintree)malloc(sizeof(binnode)); //生成新结点
            t->data=pre[i];
            while(i<length&&mid[i]!=pre[0])     //在中序遍历中查找根结点的位置
                i++;
            t->lchild=buildBintree(pre+1,mid,i);
            t->rchild=buildBintree(pre+i+1,mid+i+1,length-i-1);
        }
        else
            return NULL;
        return t;
    }
    int main()
    {   bintree root;
        char pre[100],mid[100];
        puts("请输入前序序列：");
        gets(pre);
        puts("请输入中序序列：");
        gets(mid);
        root=buildBintree(pre,mid,strlen(pre));
        puts("后序序列是：");
        postorder(root);
    }

/*bintree.h头文件*/
    #include<stdio.h>
    #include<stdlib.h>
    #define N 100
    extern char *a;
    typedef struct node
    {    
        char data;
        struct node *lchild, *rchild;
    }binnode;
    typedef binnode *bintree;
    /*函数creatbintree(根据扩充二叉树的前序序列(字符a)建立二叉树t的存储结构)*/
    binnode  creatbintree()
    {
        char ch = *a++;
        bintree t;
        if (ch == '#') t = NULL;
        else
        {
            t = (bintree)malloc(sizeof(binnode));
            t->data = ch;
            t->lchild = creatbintree();
            t->rchild = creatbintree();
        }
        return t;
    }